308
правок
Изменения
→Раскраска в 5 цветов
Пусть граф <tex>G</tex> - планарный. Тогда <tex> \chi (G) \le 6</tex>
|proof=
Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex> - вершина, покрашенная в <tex> k </tex> цвет.
Иначе, уложим полученный после шага 2 граф на плоскость и пронумеруем цвета в порядке обхода смежных вершин по часовой стрелке.
Попробуем покрасить <tex> u </tex> в цвет 1. Чтобы раскраска осталась правильной, перекрасим смежную ей вершину цвета <tex>v_1^{(1 )}</tex> в цвет 3. Если среди смежных ей вершин найдётся вершина есть вершины <tex> v_2 </tex> цвета 3, покрасим её их в цвет 1, и так далее. Если этот процесс прекратится, то требуемая раскраска получена. В противном случае могут наступить 2 варианта: #мы дойдём до уже однажды перекрашенной вершины (возможно не однажды). В таком случае раскраска останется правильной, поскольку мы меняли цвета вершин по схеме 1 <tex>\rightarrow</tex> 3, и неправильность полученной раскраски означала бы неправильность исходной. #дойдём до вершины, смежной <tex> u</tex>, исходно имеющей имевшей цвет 3, которую перекрасить в 1 нельзя (<tex> u </tex> уже перекрашена в цвет 1). Если в соответствии со 2-ым вариантом перекраска не удалась, это означает , что есть цикл <tex> u v_1^{(1)} v_2^{(3)} v_3^{(1)} ... v_{k-1}^{(1)} v_k^{(3)} u </tex>.
Таким же образом попытаемся перекрасить <tex> u </tex> в цвет 2, а смежную ей <tex>w_1^{(2)}</tex> в цвет 4 (со последующими перекрасками). Если удастся - раскраска получена.
}}
Заметим что нельзя составить подобное доказательство для раскраски в 4 цвета, поскольку наличие двух вершин одного цвета среди смежных <tex> u </tex> не исключает того, что все они раскрашены в разные цвета
== Раскраска в 4 цвета ==
