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

Материал из Викиконспекты
Версия от 10:52, 5 декабря 2014; Martoon (обсуждение | вклад) (Раскраска в 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)} ... 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 3.png Planar chromatic number 4.png Planar chromatic number 5.png

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

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

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

Источники