Гипотеза Хадвигера

Не следует путать с проблемой Нелсона — Эрдеша — Хадвигера.

Гипотеза Хадвигера — одна из неразрешённых гипотез теории графов. Она формулируется следующим образом: всякий k-хроматический граф стягиваем к полному графу на $k$ вершинах.

Другие формулировки

В графе, раскрашенном в 4 цвета, отмечены 4 подграфа, между любыми двумя из них есть ребро

Гипотезу Хадвигера можно сформулировать иначе: в каждом $k$-хроматическом графе обязательно существует $k$ непересекающихся связных подграфов таких, что между любыми двумя из них есть ребро.

Если ввести для графа число Хадвигера $h(G)$ — максимальное $k$ такое, что $G$ стягиваем к полному графу на $k$ вершинах, то гипотеза формулируется в виде неравенства $\chi(G) \leqslant h(G)$, где $\chi (G)$ — хроматическое число графа.

Частные случаи

Случаи $k = 2$ и $k = 3$ очевидны: в первом случае граф содержит хотя бы одно ребро, которое и является полным графом $K_2$, во втором случае граф не является двудольным и содержит цикл, стягиваемый к $K_3$.

Доказательство в случае $k = 4$ было опубликовано самим Хадвигером в той же работе, в которой была поставлена гипотеза.

Из гипотезы Хадвигера в случае $k = 5$ следует справедливость проблемы четырёх красок (ныне доказаной): операция стягивания сохраняет планарность, и, если бы существовал планарный 5-хроматический граф, то существовало бы вложение графа $K_5$ в плоскость, несуществование которого следует из формулы Эйлера. В 1937 году Клаус Вагнер доказал равносильность проблемы четырёх красок и гипотезы Хадвигера при $k = 5$, таким образом, этот случай также доказан.

В 1993 году Н. Робертсон, П. Сеймур и Р. Томас доказали гипотезу для $k = 6$, используя проблему четырёх красок.^[1] Это доказательство получило премию Фалкерсона в 1994 году.

Для $k = 7$ известно, что если граф не удовлетворяет гипотезе, то он стягиваем и к $K_{4,4}$, и к $K_{3,5}$ — полным двудольным графам на 4 и 4 и 3 и 5 вершинах соответственно.

Число Хадвигера

Можно определить отображение $h(G)$, сопоставляющее графу $G$ максимальное $k$ такое, что $G$ стягиваем к полному графу на $k$ вершинах. Вычисление числа Хадвигера данного графа — NP-полная задача. В любом графе $G$ таком, что $h(G) = k$ существует вершина степени не более $O(k \sqrt{\log k})$.^[2] Применяя жадный алгоритм для раскраски графа, из этого утверждения можно вывести, что $\chi (G) = O(h(G) \sqrt {\log h(G)})$.

Примечания

1. ↑ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), «Hadwiger’s conjecture for K6-free graphs»
2. ↑ Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree"