Оценки хроматического числа

Теорема 2. Если максимальная степень вершин графа G равна , то

Теорема 3. Граф G с максимальной степенью вершин является s - раскрашиваемым, за исключением двух случаев:

1. при граф содержит компоненту , являющуюся полным графом плотности

2. при граф G содержит компоненту, являющуюся циклом нечетной длины.

Оценки, полученные с помощью этих теорем, дают хорошее приближение лишь тогда, когда степени всех вершин графа имеют близкие значения. В противном случае оценка может быть значительно завышена.

Теорема 4. Для любого графа

где вершинное число независимости графа.