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