Хроматическое число. Хроматический класс Хроматическое число

Рис. 140

Например, хроматический класс графа на рис. 139 равен 5: необходимо 5 цветов для требуемой раскраски.

Вычисление хроматического класса графа  сводится к задаче нахождения хроматического числа графа  вершинами которого служат ребра  если смежные ребра в 

Рис. 141.

Рис. 142.

На рис. 140 показано, как получить  (изображенный пунктиром) из  и тем самым раскраску всех ребер  цветами.

Пусть

где

На рис. 141 и 142 изображены булевы матрицы графов  соответственно.