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

Материал из WikiGrapp
Версия от 15:23, 6 октября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Гипотеза Хадвигера''' (''Conjecture of Hadwiger'') - каждый связный <math>n</math>-хроматичес...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Гипотеза Хадвигера (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] следует гипотеза четырех красок; обратное было установлено К. Вагнером.

Литература

[Харари],

[Лекции]