Изменения

Перейти к: навигация, поиск

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

Нет изменений в размере, 22:08, 2 апреля 2014
Раскраска в 5 цветов
Начало доказательства такое же, как в предыдущей теореме, трудность возникает в индукционном переходе. Покажем что для случая с 5-ю цветами всё равно можно вернуть удалённую вершину так, чтобы раскраска осталась правильной.
Обозначим за <tex> u </tex> - возвращаемую вершину, <tex> v^{(k)} </tex> - вершинавершину, покрашенная покрашенную в <tex> k </tex> цвет.
Если среди вершин, смежных <tex> u </tex>, есть две вершины одного цвета, значит остаётся по меньшей мере один свободный цвет, в который мы и покрасим <tex> u </tex>.
Анонимный участник

Навигация