Полный график

В теории графов переполненный граф — это граф которого , размер больше, чем произведение его максимальной степени и половины его порядка нижнего , т.е. $|E|>\Delta (G)\lfloor |V|/2\rfloor$ где $|E|$ размер G , $\displaystyle \Delta (G)$ - максимальная степень G , а $|V|$ заказ Г. это Сразу следует понятие переполненного подграфа , переполненного графа, который является подграфом . Альтернативное, более строгое определение переполненного подграфа S графа G требует $\displaystyle \Delta (G)=\Delta (S)$.

Примеры

Любой нечетный граф циклов длины пять и более переполнен. Произведение его степени (двух) на половину его длины (округленное вниз) на единицу меньше количества ребер в цикле. В более общем смысле, каждый регулярный граф с нечетным числом $n$ вершин переполнено, потому что его количество ребер, $\Delta n/2$ (где $\Delta$ — его степень), больше, чем $\Delta \lfloor n/2\rfloor$.

Характеристики

Несколько свойств переполненных графов:

1. Переполненные графы имеют нечетный порядок.
2. Переполненные графики относятся к классу 2 . То есть для них требуется не менее Δ+1 цвета в любой раскраске ребер .
3. Граф G с переполненным подграфом S такой, что $\displaystyle \Delta (G)=\Delta (S)$, имеет класс 2.

Гипотеза о чрезмерной полноте

В 1986 году Аманда Четвинд и Энтони Хилтон выдвинули следующую гипотезу , которая теперь известна как гипотеза переполнения .

Граф G с $\Delta (G)>n/3$ является классом 2 тогда и только тогда, когда он имеет переполненный подграф S такой, что $\displaystyle \Delta (G)=\Delta (S)$.

Эта гипотеза, если она верна, будет иметь многочисленные последствия в теории графов, включая гипотезу об 1-факторизации .

Алгоритмы

Для графиков, в которых $\Delta \geq n/3$, существует не более трех индуцированных переполненных подграфов, и найти переполненный подграф можно за полиномиальное время . Когда $\Delta \geq n/2$, существует не более одного индуцированного переполнения подграфа, и его можно найти за линейное время .