Хроматическое число планарного графа

Материал из Викиконспекты
Версия от 14:19, 30 декабря 2015; 5.18.224.209 (обсуждение) (Раскраска в 5 цветов)
Перейти к: навигация, поиск

Для планарного графа можно дать оценку сверху на хроматическое число.

Раскраска в 6 цветов

Лемма:
В любом графе [math] G [/math] существует вершина степени не больше 5.
Доказательство:
[math]\triangleright[/math]
Предположим это не так. Для любой вершины [math] u_i [/math] графа [math] G [/math] верно [math] \mathrm{deg} \; u_i \ge 6 [/math]. Если сложить это неравенство для всех [math] i [/math], получим [math] 2E \ge 6V [/math]. Но по следствию из теоремы Эйлера [math] E \le 3V-6 [/math]. Пришли к противоречию.
[math]\triangleleft[/math]
Теорема:
Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \le 6.[/math]
Доказательство:
[math]\triangleright[/math]

Докажем по индукции.

  • База
    Если граф содержит не более 6 вершин, то утверждение очевидно.
  • Переход
    Предположим, что для планарного графа с [math]N[/math] вершинами существует раскраска в 6 цветов. Докажем то же для графа с [math] N+1 [/math] вершиной.
    По только что доказанной лемме в [math] G [/math] найдётся вершина степени не больше 5. Удалим её; по предположению индукции получившийся граф можно раскрасить в 6 цветов.
    Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин (ведь "занято" максимум 5 цветов). Индукционный переход доказан.
[math]\triangleleft[/math]

Раскраска в 5 цветов

Теорема:
Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \le 5.[/math]
Доказательство:
[math]\triangleright[/math]
u и смежные ей вершины

Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.

Обозначим за [math] u [/math] — возвращаемую вершину, [math] v^{(k)} [/math] — вершину, покрашенную в [math] k [/math] цвет.

Если среди вершин, смежных [math] u [/math], есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим [math] u [/math].

Иначе, уложим полученный после удаления [math] u [/math] граф на плоскость, вернём вершину [math] u [/math] (пока бесцветную) и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.

Попробуем покрасить [math] u [/math] в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину [math]v_1^{(1)}[/math] в цвет 3. Если среди смежных ей вершин есть вершины [math] v_i^{(3)} [/math], покрасим их в цвет 1, и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода:

  1. мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме 1 [math]\leftrightarrow[/math] 3, и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без [math] u [/math] был раскрашен правильно.
  2. дойдём до вершины, смежной [math] u [/math], исходно имевшей цвет 3, которую перекрасить в 1 нельзя ([math] u [/math] теперь имеет цвет 1).

Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со 2-ым вариантом перекраска не удалась, это означает, что в графе есть цикл [math] u v_1^{(1)} v_2^{(3)} v_3^{(1)} \ldots v_{k-1}^{(1)} v_k^{(3)} u [/math].

Тогда попытаемся таким же образом перекрасить [math] u [/math] в цвет 2, а смежную ей [math]w_1^{(2)}[/math] в цвет 4 (со последующими перекрасками). Если удастся — раскраска получена.

Если нет, то получили ещё один цикл [math] u w_1^{(2)} w_2^{(4)} w_3^{(2)} ... w_{k-1}^{(2)} w_k^{(4)} u [/math]. Но граф планарный, значит два полученных цикла пересекаются помимо вершины [math] u [/math] по крайней мере ещё в одной, что невозможно, ведь вершины [math] v_i [/math] первого цикла и [math] w_j [/math] второго — разных цветов. Значит такой случай наступить не мог.
[math]\triangleleft[/math]
Успешное перекрашивание Цикл 1—3, перекрасить не удаётся
Planar chromatic number 2.png Planar chromatic number 4.png
Planar chromatic number 3.png Planar chromatic number 5.png

Заметим, что не удаётся составить подобное доказательство для раскраски в 4 цвета, поскольку здесь наличие двух вершин одного цвета среди смежных [math] u [/math] не исключает того, что при их (смежных вершин) раскраске использовались все возможные цвета.

Раскраска в 4 цвета

Данная теорема была доказана Кеннетом Аппелем и Вольфгангом Хакеном. Их доказательство сводилось к рассмотрению порядка 2000 графов, 4-раскрашиваемость которых была проверена при помощи компьютера. Подробнее см. здесь.

Источники информации