Хроматическое число графа

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

Иначе говоря, p- раскраска графа G =(V, U) ¾ это такое разбиение множества V на p непустых подмножеств V ₁,..., V_p, что всякое ребро из U соединяет вершины из разных множеств разбиения.

Например, граф, изображенный на рис. 5.30, является
3- раскрашиваемым и 4- раскрашиваемым, но не является
2- раскрашиваемым.

Рис. 5.30