Теорема Визинга

Материал из WikiGrapp
Версия от 14:40, 2 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Теорема Визинга''' (''В.Г.Визинг, 1964'') ''Каков бы ни был граф <math>G</math>, его хром...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Теорема Визинга (В.Г.Визинг, 1964) Каков бы ни был граф [math]\displaystyle{ G }[/math], его хроматический индекс [math]\displaystyle{ \chi'(G) }[/math] удовлетворяет неравенствам

[math]\displaystyle{ \Delta(G) \leq \chi'(G) \leq \Delta(G) + 1. }[/math]

Литература

[Лекции],

[Зыков/69],

[Berge],

[Bondy-Murty]