Открыть главное меню

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

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

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

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

Если ввести для графа число Хадвигера[⇨]   — максимальное   такое, что   стягиваем к полному графу на   вершинах, то гипотеза формулируется в виде неравенства  , где   — хроматическое число графа.

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

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

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

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

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

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

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

Можно определить отображение  , сопоставляющее графу   максимальное   такое, что   стягиваем к полному графу на   вершинах. Нахождение числа Хадвигера данного графа — NP-трудная задача. В любом графе  , для которого  , существует вершина степени  .[2] Применяя жадный алгоритм для раскраски графа, из этого утверждения можно вывести, что  .

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

ПримечанияПравить

  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"