Гипотеза Хадвигера (теория графов)

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

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

Другие формулировкиПравить

 

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

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

Если ввести для графа число Хадвигера^[⇨] $h(G)$$h(G)$  — максимальное $k$$k$  такое, что $G$$G$  стягиваем к полному графу на $k$$k$  вершинах, то гипотеза формулируется в виде неравенства $\mathrm{\chi <!--\; \chi \; -->}(G)⩽<!--\; ⩽\; -->h(G)$$\chi(G) \leqslant h(G)$ , где $\mathrm{\chi <!--\; \chi \; -->}(G)$$\chi (G)$  — хроматическое число графа.

Частные случаиПравить

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

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

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

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

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

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

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

См. такжеПравить

• Гипотеза Хадвигера (комбинаторная геометрия)