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

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

Лемма:

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

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

[math]\triangleright[/math]

Предположим это не так. Для любой вершины [math] u_i [/math] графа [math] G [/math] верно [math] deg [/math] [math] 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 цветов. Вернём удалённую вершину и покрасим её в цвет, не встречающийся среди смежных ей вершин. Индукционный переход доказан

[math]\triangleleft[/math]

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

Теорема:

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

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

[math]\triangleright[/math]

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

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

Источники

1. http://matica.org.ua/lektsii-po-diskretnoy-matematike/3-08-6-raskraski-planarnich-grafov