2.2. Верхние оценки для .

Нижние оценки хроматического числа безусловно более интересны, чем верхние, поскольку (если они достаточно близки к истинному значению) они могут быть использованы в процедуре вычисления , включающей дерево поиска. В то же время верхние оценки хроматического числа подобного применения не находят. Тем не менее в литературе приводится формулы для вычисления верхних оценок хроматического числа; так Бруксом предложена следующая легко вычисляемая оценка:

(3)