Раскраска графов

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

Хроматическое число пустого графа равно 1.
Хроматическое число .
Хроматическое число .

Алгоритм нахождения раскраски (хроматического числа)

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

Пример