Граф G называется k - раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета.
Если граф G является k - раскрашиваемым, но не является (k - 1) - раскрашиваемым, то он называется k - хроматическим, а число k называетсяхроматическим числом графа и обозначается c(G).
На рис.4.22 граф G является и 4 - раскрашиваемым и 5 - раскрашиваемым, но 4 - хроматическим.
G c(G) = 4
Рис.4.22. Хроматическое число графа
Таким образом, хроматическое число графа - это минимальное число красок, в которые может быть раскрашен граф.
Для некоторых графов хроматические числа очевидны. Так для любого полного графа из n вершин хроматическое число равно n, c(Kn) = n.
Любой двудольный граф является бихроматическим. Для графа G(X,U),
X = X1 U X2, c(G) = 2.
Действительно, раскрасив вершины из множества X1 в один цвет, а вершины из множества X2 - в другой цвет, получим 2 - раскрашиваемый граф.
