3.08.6. Раскраски планарных графов

Теорема. Для любого планарного графа существует правильная 6–раскраска.

Доказательство. Индукция по числу вершин N.

База индукции: N ≤ 7 – утверждение очевидно.

Индукционный переход. Предположим, что правильная 6–раскраска существует для всякого планарного графа порядка N. Рассмотрим планарный граф порядка N+1. Согласно следствию 6 из формулы Эйлера в нем существует вершина V степени deg V ≤ 5. Удалим эту вершину. И воспользуемся 6–раскраской полученного графа, которая существует в силу индукционного предположения. Раскрасив удаленную вершину V в цвет, отличный от цветов смежных с ней вершин, получим правильную раскраску исходного графа.

Замечание. С помощью более тщательных и тонких рассуждений можно доказать, что всякий планарный граф 5–раскрашиваемый. Кроме того еще в прошлом веке была высказана гипотеза 4-х красок. Сравнительно недавно было получено положительное решение этой гипотезы с использованием ЭВМ. Пример полного графа К4, который является планарным, показывает, что эту величину (4 краски) в общем случае уменьшить нельзя. Однако, известно, что если в плоском графе нет циклов длины 3, то граф 3 – раскрашиваемый (теорема Греча), а если нет циклов нечетной длины, то достаточно 2-х красок (следует из критерия двудольности графа).

< Предыдущая		Следующая >