Определение: Вершины (ребра) графа G правильно раскрашены, если каждая вершина (ребро) графа G окрашено некоторой краской, причем всякие две смежные вершины (ребра) имеют различную окраску.

Замечание: Всякий подграф правильно раскрашенного графа также правильно раскрашен.

Определение: Граф G к-раскрашиваем, если его можно правильно раскрасить не более, чем к цветами.

Определение: Хроматическое число графа G есть наименьшее число χ(G) красок, с помощью которых можно правильно раскрасить вершины графа G. Хроматическое класс графа G – есть наименьшее число χ’(G) красок, с помощью которых можно правильно раскрасить ребра графа G.

Комментарии запрещены.