9.4. Вершинная раскраска и хроматическое число

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

Не нарушая общности, мы можем допустить, что графы, рассматриваемые в этом разделе, простые.

Хроматическим числом графа G называется минимальное число 6, для которого G вершинно -раскрашиваемый. Граф Сказывается -хроматическим, если Например, на рис. 9.5 хроматическое число графа равно 3.

Далее вместо «правильная вершинная -раскраска» будем говорить просто «-раскраска». Аналогично «вершинно -раскрашивае-мый» будем заменять на «-раскрашиваемый».

Заметим, что -раскраска графа порождает разбиение множества V, где каждое У — подмножество вершин, которым присвоен цвет i и поэтому является независимым множеством. Аналогично каждое разбиение множества V на 6 независимых множеств соответствует -раскраске графа

Рис. 9.5. Правильная вершинная -раскраска.

В предыдущем разделе (теорема 9.7) мы доказали, что для правильной раскраски ребер простого графа требуется, самое большее, цветов. Докажем аналогичный результат для вершинной раскраски.

Теорема 9.8. Простой граф -раскрашиваемый.

Доказательство. Даны различных цветов, получим (-раскраску графа G следующим образом.

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

Очевидно, что для полных графов и циклов нечетной длины. Очень интересно то, что для всех остальных графов Этот результат получен Бруксом [9.7] и доказывается ниже. Приводимое здесь доказательство предложили Мельников и Визинг [9.8]. Другое доказательство можно найти в работе [9.9].

Теорема 9.9 (Брукс). Пусть G — связный простой граф. Если он не цикл нечетной длины и не полный граф, то

Доказательство. Теорема очевидна для .

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

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

Свойство 1. В любой -раскраске графа G вершины, смежные с вершиной раскрашиваются по-разному

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

значим через порожденный подграф G на вершинах, которым присвоены цвета I и

Свойство 2. Вершины и у находятся в одной компоненте связности

В противном случае, заменяя цвета в компоненте, содержащей мы получим новую -раскраску графа G, в которой - и и у присвоен одинаковый цвет, что противоречит свойству 1.

Пусть компонента содержащая вершины

Свойство путь от вершины - к вершине и у.

Предположим, что степень - в больше 1. Тогда смежна не менее чем с двумя вершинами цвета Поскольку в графе G, мы можем перекрасить в цвет так что в получившейся новой раскраске вершины имеют одинаковый цвет, что противоречит свойству 1.

Аналогично можно показать, что степень и у в равна 1.

Степень всех остальных вершин равна 2. Допустим противное. Пусть и — первая вершина степени (в ) больше 2 на пути от вершины к вершине и у. Если и раскрашена в цвет i, то она смежна по крайней мере с тремя вершинами цвета Поскольку можно перекрасить и в цвет поэтому в новой раскраске вершины - и будут в разных компонентах, что противоречит свойству 2.

Таким образом, является путем из вершины - в вершину

Свойство не имеют общих вершин, за исключением

Пусть общая вершина Тогда и раскрашена в цвет i и смежна по крайней мере с двумя вершинами цвета и двумя вершинами цвета k. Так как существует цвет в который можно перекрасить . Но это разделит вершины что противоречит свойству 2.

Продолжим доказательство теоремы. Установим теперь противоречие со свойством 4.

Поскольку G — не полный граф на вершине, существуют две несмежные вершины, например их и Путь содержит вершину смежную с вершиной Допустим, что мы поменяли местами цвета 1 и 3 в пути (который присутствует, поскольку ДЗ), в результате чего в новой раскраске G вершина получает цвет 3, а вершина — цвет 1. Но тогда новые компоненты содержат общую вершину что противоречит свойству 4.

Это завершает доказательство теоремы.