Некоторые оценки хроматического числа
Уже отмечалось, что χ(Кn) = n. Поэтому если граф G содержит полный подграф порядка r, то χ(G) ≥ r. В целом, чем меньше ребер в графе и чем меньше степени его вершин, тем меньше хроматическое число.
Теорема. Пусть r – минимальная степень вершин графа G, тогда существует правильная (r+1)–раскраска графа G.
Доказательство. Индукция по числу вершин n графа G.
База индукции: n = 2 -- утверждение очевидно.
Индукционный переход. Предположим, что существует правильная
(r+1)–раскраска для всех графов порядка n, у которых степени вершин не превосходят
r. Рассмотрим граф порядка n+1 с максимальной степенью вершин, равной r. Удалим
произвольную вершину 
. Для полученного графа порядка n существует согласно индукционному
предположению правильная (r+1) – раскраска. Воспользуемся такой раскраской.
Удаленная вершина имеет не более r смежных, для окраски которых использовано
не более r цветов. Окрасим вершину в цвет, отличный от цвета смежных вершин (так как цветов
больше, чем r, то такой цвет найдется). Получим правильную (r+1)–раскраску
исходного графа.
Теорема (Брукс). Пусть G – связный граф, не являющийся полный, и степени
всех вершин которого не превосходят r, где r ≥ 3. Тогда χ(G) ≤
r.
Замечание. Оценка хроматического числа в теореме Брукса достижима (см. рисунок) и, значит, не может быть в общем случае (без дополнительных предположений) улучшена. Однако, оценка весьма грубая. При выполнении условий теоремы хроматическое число может быть значительно меньше максимальной степени вершин. Например, звездный граф К1,n , и с максимальной степенью вершин n имеет хроматическое число 2. Для колеса W2n по теореме Брукса χ(W2n) ≤ 2n. В действительности χ(W2n) = 3.