Теорема

Хроматический полином. Р(G,) графа G на вершинах имеет степень n с главным членом

и const.=0 Все коэффициенты целые и чередуются …….

Пусть граф G с n вершинами и m рёбрами. е – ребро G .Тогда G- е -граф на n вершинах с m-1 рёбрами , а G* е - граф на n-1 вершинах с m-1 или менее рёбрами.

 

 

Оценки:

Нижние:

Верхние оценки:

Алгоритм раскраски

Пусть множество вершин упорядочено и -я вершина этого множества

1. окрасить в цвет 1
2. Каждую из оставшихся вершин окрасить : в цвет с наименьшим возможным номером ( не используя при окраске вершин смежной с .

 

 

 

Если граф G –К –раскрашиваемый , но не является (К-1)раскрашиваемым , а число К- хроматическое число графа G, обозначим Х(G)

4-хроматический граф, цвета ()