Гипотеза Хадвигера: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Гипотеза Хадвигера''' (''Conjecture of Hadwiger'') - каждый связный <math>n</math>-хроматичес...)
(нет различий)

Версия от 15:23, 6 октября 2009

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

Литература

[Харари],

[Лекции]