3.08.1. Раскраски графов. Хроматическое число графа

Раскраска вершин графа G называется правильной, если любые две смежные вершины окрашены в разные цвета. Правильная раскраска графа G, при которой использовано K различных цветов, называется K-раскраской, а граф G , для которого существует K-раскраска, называется K-раскрашиваемым. Наименьшее значение K, для которого существует правильная K-раскраска графа G , называется Хроматическим числом графа G и обозначается χ(G)

Так, например, для простой цепи Рn хроматическое число равно 2. Хроматическое число простого цикла Сn в случае четного N также равно 2, а для нечетных N – равно 3. В полном графе Кn , очевидно, окраска вершин будет правильной только в случае, если все вершины раскрашены в разные цвета. Поэтому χ(Кn) = n.

К поиску правильной окраски графа и его хроматического числа сводится решение многих классических задач.

< Предыдущая		Следующая >