Теорема Визинга: различия между версиями

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Теорема Визинга''' (''В.Г.Визинг, 1964'') ''Каков бы ни был граф <math>G</math>, его хром...)
 
Нет описания правки
Строка 1: Строка 1:
'''Теорема Визинга''' (''В.Г.Визинг, 1964'')
'''Теорема Визинга''' (''[[В.Г.Визинг, 1964]]'')
''Каков бы ни был граф <math>G</math>, его хроматический индекс <math>\chi'(G)</math> удовлетворяет неравенствам''
''Каков бы ни был [[граф]] <math>G</math>, его [[хроматический индекс]] <math>\chi'(G)</math> удовлетворяет неравенствам''


<math>\Delta(G) \leq \chi'(G)  \leq \Delta(G) + 1.</math>
<math>\Delta(G) \leq \chi'(G)  \leq \Delta(G) + 1.</math>

Версия от 12:37, 4 февраля 2010

Теорема Визинга (В.Г.Визинг, 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]