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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Гипотеза Хадвигера — одна из неразрешённых гипотез теории графов. Она формулируется следующим образом: всякий 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 вершинах является последовательно-параллельным графом и их подграфом. Каждый граф такого типа имеет вершину с не более чем двумя ребрами. Можно окрасить граф в три цвета, любой такой граф при удалении одной такой вершины, раскрашивает оставшийся граф рекуррентно, а затем добавляет и окрашивает удаленную ранее вершину. Так как удаленная вершина имеет два ребра, один из трех цветов всегда будет доступен для окраски когда вершина добавлена назад.

Из гипотезы Хадвигера в случае 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"