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

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

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

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

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

Свойства

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

• Из теоремы^[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})}$.