Переполненный граф

Переполненный граф (англ. overfull graph) — это такой простой граф $G$ (без кратных ребер и петель), размер которого $|E|$ больше произведения максимальной степени его вершин $\displaystyle \Delta (G)$ на округлённую вниз половину его порядка $|V|$

$|E|>\Delta (G)\lfloor |V|/2\rfloor$.

Если граф $G$ имеет переполненный подграф $S$ и $\displaystyle \Delta (S)$ = $\displaystyle \Delta (G)$ то $G$ - называется графом с переполненным подграфом (англ. subgraph-overfull graph).

Понятие переполненный граф было введено при рассмотрении задач о раскраске ребер графа, а именно при решении вопроса о принадлежности графа к Классу 1 или Классу 2. Как следует из Теоремы Визинга, хроматический индекс графа может быть либо $\chi ^{\prime }(G)=\Delta (G)$, и тогда граф принадлежит к Классу 1, либо $\chi ^{\prime }(G)=\Delta (G)+1$ и тогда граф принадлежит к Классу 2.

Свойства

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

• Из теоремы, которая гласит, что если граф $G$ обладает размером $|E|$, таким что $|E|>\beta _{1}(G)\Delta (G)$, где $\beta _{1}(G)$ есть реберное число независимости, а $\Delta (G)$ есть максимальная степень его вершин , то граф $G$ принадлежит Классу 2, и условия, что если граф порядка $|V|$, то его реберное число независимости $\beta _{1}(G)=\lfloor |V|/2\rfloor$, вытекает свойство:

Переполненный граф является графом Класса 2

• Доказывается как теорема:

Если у графа есть переполненный подграф, то сам граф - переполненный

• Доказывается как теорема.

Порядок переполненного графа - нечётное число

Гипотеза о переполнении

Четуинд и Хилтон в 1986 г. выдвинули гипотезу, известную сейчас как гипотеза о переполнении (англ. Overfull Graph Conjecture)

Если для максимальной степени вершин графа выполняется условие $3\Delta (G)\geqslant |V|$, где $|V|$ есть порядок графа, то граф $G$ принадлежит к Классу 2 тогда и только тогда, когда он является графом с переполненным подграфом.

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

Алгоритмы

В работе приводится алгоритм, которые позволяет найти для графа $G$ у которого $|V(S)|>|V(G)|-\Delta (G)$ все порожденные переполненные подграфы $S$ за время $O(n\log(n)+m)$, где $n=|V(G)|$ и $m=|E(G)|$.

Вариант этого алгоритма позволяет для графа $G$, у которого $2\Delta (G)\geq |V(G)|$ найти все порожденные переполненные подграфы за линейное время $O(n+m)$.

Также в работе приводится второй алгоритм, работающий с использованием первого алгоритма, который позволяет найти все порожденные переполненные подграфы графа $G$, у которого $3\Delta (G)\geq |V(G)|$ в общем случае за полиномиальное время $O(n^{5/3}m)$, а для регулярного графа $G$ за время $O(n^{3})$.