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

Гіпотеза Хадвігера — одна з нерозв'язаних гіпотез теорії графів . Вона формулюється так: будь-який k-хроматичний граф стягується до повного графу на ${\displaystyle k}$ вершинах.

Інші формулювання

У графі, пофарбованому в 4 кольори, відзначені 4 підграфи, між будь-якими двома з них є ребро

Гіпотезу Хадвігера можна сформулювати інакше: у кожному ${\displaystyle k}$-хроматичному графі обов'язково існує ${\displaystyle k}$ зв'язних підграфів, які не перетинаються і між будь-якими двома з них є ребро.

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