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

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

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

Лемма:

В любом планарном графе [math] G [/math] существует вершина степени не больше [math]5[/math].

Доказательство:

[math]\triangleright[/math]

Предположим это не так. Для любой вершины [math] u_i [/math] графа [math] G [/math] верно [math] \mathrm{deg} \; u_i \geqslant 6 [/math]. Если сложить это неравенство для всех [math] i [/math], получим [math] 2E \geqslant 6V [/math]. Но по следствию из теоремы Эйлера [math] E \leqslant 3V-6 [/math]. Пришли к противоречию.

[math]\triangleleft[/math]

Теорема:

Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \leqslant 6.[/math]

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

Теорема (Хивуд):

Пусть граф [math]G[/math] — планарный. Тогда [math] \chi (G) \leqslant 5.[/math]

Доказательство:

[math]\triangleright[/math]

[math]u[/math] и смежные ей вершины Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с [math]5[/math]-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной. Обозначим за [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] в цвет [math]1[/math]. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину [math]v_1^{(1)}[/math] в цвет [math]3[/math]. Если среди смежных ей вершин есть вершины [math] v_i^{(3)} [/math], покрасим их в цвет [math]1[/math], и так далее. Рассмотрим две необычные ситуации, которые могут наступить во время обхода: мы дойдём до уже однажды перекрашенной вершины (и хотим перекрасить её обратно, что не получится сделать). Видно что такая ситуация невозможна, поскольку мы меняли цвета вершин по схеме [math]1[/math] [math]\leftrightarrow[/math] [math]3[/math], и если по завершении обхода мы получили две смежные вершины одного цвета, значит и до перекрасок в этом месте были две вершины одинакового цвета, а по предположению граф без [math] u [/math] был раскрашен правильно. дойдём до вершины, смежной [math] u [/math], исходно имевшей цвет [math]3[/math], которую перекрасить в [math]1[/math] нельзя ([math] u [/math] теперь имеет цвет [math]1[/math]). Если этот процесс был успешно завершён, то получили правильную раскраску. Если же в соответствии со вторым вариантом перекраска не удалась, это означает, что в графе есть цикл [math] u v_1^{(1)} v_2^{(3)} v_3^{(1)} \ldots v_{k-1}^{(1)} v_k^{(3)} u [/math]. Тогда попытаемся таким же образом перекрасить [math] u [/math] в цвет [math]2[/math], а смежную ей [math]w_1^{(2)}[/math] в цвет [math]4[/math] (со последующими перекрасками). Если удастся — раскраска получена. Если нет, то получили ещё один цикл [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, перекрасить не удаётся

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

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

Теорема (Проблема четырех красок):

Теорема о четырёх красках — утверждение о том, что всякую расположенную на сфере карту можно раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. При этом области могут быть как односвязными, так и многосвязными (в них могут присутствовать «дырки»), а под общим участком границы понимается часть линии, то есть стыки нескольких областей в одной точке общей границей для них не считаются.

Теорема о четырёх красках была доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу, чтобы доказать это свойство для каждой из 1936 карт. Доказательство этого факта заняло сотни страниц. После этого Аппель и Хакен пришли к выводу, что не существует наименьшего контрпримера к теореме, потому что иначе он должен бы содержать, хотя не содержит, какую-нибудь из этих 1936 карт. Это противоречие говорит о том, что вообще не существует контрпримера. Изначально доказательство не было принято всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения.

Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Джорджсом Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1)

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

• matica.org — Раскраска планарного графа
• Википедия — Проблема четырёх красок
• Wikipedia — Four color theorem