748
правок
Изменения
Нет описания правки
{{Лемма
|about = оценка хроматического числа длиной максимального нечётного цикла
|statement= Пусть <tex>G(V,E)</tex> {{- --}} произвольный связный неориентированный граф и <tex>\Delta(G)</tex> {{--- }} длина максимального простого цикла графа <tex>G</tex>, <tex>\Delta \geqslant 3</tex>. Тогда, <tex>\chi(G) \leqslant\Delta(G) + 1</tex>.
|proof=
Опишем на графе следующий алгоритм раскраски:
{{Лемма
|about = нижняя оценка
|statement= Пусть <tex>G(V,E)</tex> {{- --}} произвольный связный неориентированный граф с <tex>n</tex> вершинами .Тогда, <tex>n/\alpha \leqslant \chi(G)</tex>.
|proof=
Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>.Каждое из <tex>V_i</tex> {{---}} независимое множество (поскольку вершины множества покрашены в один цвет при правильной покраски графа <tex>G</tex>, следовательно, они попарно не смежны внутри множества ).
{{Лемма
|about = верхняя оценка
|statement= Пусть <tex>G(V,E)</tex> {{- --}} произвольный связный неориентированный граф с <tex>m</tex> ребрами.Тогда, <tex>\chi(G) \leqslant \frac{1}{2} +\sqrt{2m + \frac{1}{4}}</tex>.
|proof=
Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>. Заметим, что между любыми двумя различными множествами существует хотя бы одно ребро (в противном случаи эти множества можно было бы покрасить в один цвет).
{{Лемма
|about = нижняя оценка Геллера
|statement= Пусть <tex>G(V,E)</tex> {{- --}} произвольный связный неориентированный граф с <tex>n</tex> вершинами и <tex>m</tex> ребрами .Тогда, <tex>\frac{n^2}{n^2 - 2m} \leqslant \chi(G) </tex>.
|proof=
Пусть, <tex>V_1,V_2...V_\chi</tex> множеств вершин окрашенных в соответствующие цвета при правильно покраски графа <tex>G</tex>.
