________________________________________________________________

Граф называется вершинно-К-раскрашенным, если его вершины можно раскрасить К-красками так, чтобы никакие две вершины не имели бы одинаковый цвет. Минимальное число К, при котором граф G является вершинно-К-раскрашенным называется хроматическим числом графа.

Раскрасить граф можно используя следущий алгоритм:

1. Найти число связей всех вершин графа.

2. Рассматривать вершины в порядке не возрастания числа связей.

3. Начинаем раскрашивание в цвет №1. Рассматриваем вершины последовательно и если рассматриваемая вершина не раскрашена, а также не имеет связей с вершинами раскрашеными в этот цвет, то раскрашиваем её в этот цвет.

4. Если все вершины просмотрены, но не раскрашены, то повторяем пункт 3, с цветом на единицу больше, пока все вершины не раскрашены. Число цветов это и есть хроматическое число.

Пример: