9.5. Хроматические полиномы

В этом разделе мы обсуждаем вопрос подсчета различных правильных -раскрасок графа.

Если граф -раскрашиваемый, то его можно раскрасить в X цветов более чем одним способом. Две раскраски графа считаются различными, если хотя бы одной вершине графа присваиваются разные цвета.

Хроматический полином имеет значение для каждого целого К, равное числу различных правильных -раскрасок графа

Рассмотрим, например, граф, представленный на рис. 9.6. Среди данных X цветов мы можем выбрать любой для раскраски вершины а. Вершину b можно раскрасить в один из оставшихся цветов. Для каждой раскраски вершины b существует различных способов раскраски вершины с. Таким образом, граф на рис. 9.6 можно раскрасить различными способами. Другими

словами, хроматический полином графа равен к Мы можем повторить эти рассуждения, чтобы показать, что хроматический полином пути на вершинах равен к

В качестве другого примера рассмотрим полный граф на вершинах При наличии к цветов вершину можно раскрасить в любой из них, вершину — в любой из оставшихся цветов, а вершину — в любой из оставшихся цветов и т. д.

Рис. 9.6.

Таким образом, Теперь выведем формулу для определения хроматического полинома графа

Теорема 9.10. Пусть — несмежные вершины простого графа G. Пусть — простой граф, полученный из графа G замыканием вершин и и и и заменой получившегося множества параллельных ребер на одно ребро, — граф, полученный добавлением к графу G ребра , то .

Доказательство. Любая -раскраска графа G, в которой вершинам и и v присваиваются различные цвета, соответствует -раскраске графа и наоборот. Аналогично любая -раскраска графа G, в которой вершинам и и v присвоен один цвет, соответствует -раскраске графа и наоборот. Следовательно, .

Этот результат можно сформулировать в другой форме.

Следствие 9.10.1. Если — ребро простого графа G, то , где получается из графа G удалением ребра определяется из теоремы 9.10.

Если мы повторно применим формулу, приведенную в теореме 9.10, к графу G, то процесс закончится на полных графах, например поэтому .

С другой стороны, если мы используем формулу, приведенную в следствии 9.10.1, процесс закончится на пустых графах (т. е. графах, не имеющих ребер), поэтому хроматический полином есть линейная комбинация хроматических полиномов пустых графов.

Обе процедуры иллюстрируются рис. 9.7.

Теорема 9.11. Хроматический полином графа на вершинах имеет степень с главным членом и константой, равной 0. Кроме того, все коэффициенты целые и чередуются по знаку.

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

Допустим, что теорема верна для всех графов, имеющих менее ребер. Рассмотрим граф G на вершинах с ребрами. Пусть — ребро графа G. Тогда граф на вершинах с ребрами, граф на вершинах с или менее ребрами.

(см. скан)

Рис. 9.7. Вычисление хроматического полинома графа G. а - с использованием теоремы 9.10; б — с использованием следствия 9.10.1;

Из индуктивного предположения следует, что существуют такие неотрица тельные целые коэффициенты что Р Согласно следствию Таким образом граф G также удовлетворяет теореме.