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