ОПРЕДЕЛЕНИЕ. Хроматическим числом графа G называется такое минимальное число k, для которого существует k-раскраска этого графа

Хроматическим числом графа G называется такое минимальное число k, для которого существует k -раскраска этого графа.

Хроматическое число определено для всякого неориентированного графа G, не имеющего петель, и обозначается как c (G).

Упражнение. Определить хроматическое число полного графа с n вершинами.

Нетрудно видеть, что если граф G содержит подграф, являющийся полным графом с n вершинами, то c (G) n.

Обратное свойство не имеет места, т.е. произвольный граф G с (G) = n не обязательно содержит полный подграф с n вершинами.

Например, для графа, изображенного на рис. 5.31, значение c (G) = 4. Однако в G не содержит полных подграфов с четырьмя вершинами.

Рис. 5.31