9.6. Проблема четырех красок
При изготовлении карт в целях различения отдельных областей необходимо их раскрашивать таким образом, чтобы никакие две смежные области не были раскрашены одинаково. Эта задача правильной раскраски областей планарного графа равносильна задаче правильной раскраски вершин двойственного графа. Легко привести пример, показывающий, что трех цветов в общем случае недостаточно для правильной раскраски планарного графа. В следующей теореме, известной под названием теоремы о пяти красках, мы показываем, что пяти цветов достаточно.
Теорема 9.12. Любой планарный граф 
-раскрашиваемый.
Доказательство. Допустим, что теорема верна для всех планарных графов порядка менее 
, покажем, что она верна также для планарного графа 
порядка 
.
Согласно следствию 7.3.5, в графе G существует вершина 
степени не более 
. Пусть G — порожденный подграф графа G на 
Раскрасим подграф G в пять цветов: 
(Это возможно в силу индуктивного предположения.)
Рис. 9.8.
Очевидно, что если 
то вершине 
в правильной 
-раскраске графа G можно присвоить один из этих цветов. В противном случае всем S вершинам 
смежным с вершиной 
можно присвоить различные цвета.
Допустим, что вершине 
присвоен цвет 
Кроме того, пусть вершины 
располагаются по часовой стрелке относительно вершины 
как показано на рис. 9.8.
Пусть 
— подграф графа G на вершинах, которым присвоены цвета 
или 
Компонента 
содержащая вершину 
должна содержать 
-вершину 
в противном случае цвета 
в этой компоненте можно было бы поменять местами и раскрасить вершину 
в цвет 
Аналогично компонента 
содержащая вершину 
должна содержать и вершину 
(рис. 9.8).
Тогда в 
вершины 
не будут соединены путем. Поэтому если в компоненте 
содержащей вершину 
поменять местами цвета 
и 
то вершину 
можно будет раскрасить в цвет 
Таким образом, граф G — 
-раскрашиваемый.
Этот результат был получен Хивудом [9.10].
Возникает вопрос: можно ли улучшить теорему о пяти красках? Предполагалось, что любой планарный граф 4-раскрашиваемый. Эта гипотеза известна как гипотеза четырех красок. Она оставалась неразрешенной более 100 лет и была предметом экстенсивных исследований. Недавно Аппель и Хакен [9.11] доказали справедливость гипотезы. Этот результат формулируется в следующей теореме:
Теорема 9.13 (теорема о четырех красках). Каждый планарный граф 4-раскрашиваемый.
Имеется очень обширная литература, касающаяся проблемы четырех красок. Обзор проблемы с историческими подробностями можно найти в работах [9.12-9.14]. См. также работу [9.15].
