Пусть 
- некоторый граф и 
- разбиение 
на 
внутренне устойчивых множеств (разбиение означает, что 
и 
, если 
). В этом случае говорят, что вершины графа допускают раскраску в цветов (цвета по номерам 
). Хроматическое число 
- минимальное значение , которое допускает раскраску графа.
Хроматическое число пустого графа равно 1.
Хроматическое число 
.
Хроматическое число 
.
Алгоритм нахождения раскраски (хроматического числа)
1) Выделить все пустые подграфы графа.
2) Построить таблицу покрытий вершин графа пустыми подграфами.
3) Найти минимальное покрытие вершин графа пустыми подграфами (мощность минимального покрытия – это , а само покрытие определяет раскраску).
Пример
