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

Гипотеза Хадвигера (Conjecture of Hadwiger) - каждый связный [math]\displaystyle{ n }[/math]-хроматический граф стягиваем к полному [math]\displaystyle{ n }[/math]-вершиннику [math]\displaystyle{ K_{n} }[/math]

Гипотеза верна для [math]\displaystyle{ n \leq 4 }[/math] (Г. Дирак, 1952). Из нее при [math]\displaystyle{ n = 5 }[/math] следует гипотеза четырех красок; обратное было установлено К. Вагнером.

Литература

[Харари],

[Лекции]