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

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

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

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

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

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

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

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

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

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

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

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

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

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