Русская Википедия:Гипотеза Хадвигера (теория графов)
Шаблон:Не путать Шаблон:Значения
Гипотеза Хадвигера (теория графов) — одна из неразрешённых гипотез теории графов. Она формулируется следующим образом: всякий <math>k</math>-хроматический граф стягиваем к полному графу на <math>k</math> вершинах.
Другие формулировки
Гипотезу Хадвигера можно сформулировать иначе: в каждом <math>k</math>-хроматическом графе обязательно существует <math>k</math> непересекающихся связных подграфов таких, что между любыми двумя из них есть ребро.
Если ввести для графа число ХадвигераШаблон:Переход <math>h(G)</math> — максимальное <math>k</math> такое, что <math>G</math> стягиваем к полному графу на <math>k</math> вершинах, то гипотеза формулируется в виде неравенства <math>\chi(G) \leqslant h(G)</math>, где <math>\chi (G)</math> — хроматическое число графа.
Частные случаи
Случаи <math>k = 2</math> и <math>k = 3</math> очевидны: в первом случае граф содержит хотя бы одно ребро, которое и является полным графом <math>K_2</math>, во втором случае граф не является двудольным и содержит цикл, стягиваемый к <math>K_3</math>.
Доказательство в случае <math>k = 4</math> было опубликовано самим Хадвигером в той же работе, в которой была поставлена гипотеза.
Из гипотезы Хадвигера в случае <math>k = 5</math> следует справедливость проблемы четырёх красок (ныне доказанной): операция стягивания сохраняет планарность, и, если бы существовал планарный 5-хроматический граф, то существовало бы вложение графа <math>K_5</math> в плоскость, несуществование которого следует из формулы Эйлера. В 1937 году Клаус Вагнер доказал равносильность проблемы четырёх красок и гипотезы Хадвигера при <math>k = 5</math>, таким образом, этот случай также доказан.
В 1993 году Н. Робертсон, П. Сеймур и Робин Томас доказали гипотезу для <math>k = 6</math>, используя проблему четырёх красок.[1] Это доказательство получило премию Фалкерсона в 1994 году.
Для <math>k = 7</math> известно, что если граф не удовлетворяет гипотезе, то он стягиваем и к <math>K_{4,4}</math>, и к <math>K_{3,5}</math> — полным двудольным графам с долями мощности 4 и 4 и мощности 3 и 5 соответственно.
Число Хадвигера
Можно определить отображение <math>h(G)</math>, сопоставляющее графу <math>G</math> максимальное <math>k</math> такое, что <math>G</math> стягиваем к полному графу на <math>k</math> вершинах. Нахождение числа Хадвигера данного графа — NP-трудная задача. В любом графе <math>G</math>, для которого <math>h(G) = k</math>, существует вершина степени <math>O(k \sqrt{\log k})</math>.[2] Применяя жадный алгоритм для раскраски графа, из этого утверждения можно вывести, что <math>\chi (G) = O(h(G) \sqrt {\log h(G)})</math>. Шаблон:Math-stub
См. также
Примечания
- ↑ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), «Hadwiger’s conjecture for K6-free graphs» Шаблон:Wayback
- ↑ Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree"
