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

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

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

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

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

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