Гипотеза четырех красок

 

 

Гипотеза четырех красок, благодаря попыткам решить ее, служила катализатором для теории графов. Мы здесь представим теоретико-графовое обсуждение этой бесславной проблемы. Раскраской плоской карты G называется такое приписывание цветов областям в G, что никакие две смежные области не получают одинакового цвета. Карта G называется n-раскрашиваемой, если существует ее раскраска, использующая n или менее цветов. Первоначальная формулировка гипотезы, выглядит так: каждая плоская карта 4-раскрашиваема.

Гипотеза четырех красок. Каждый планарный граф 4-раскрашиваем.

Еще раз подчеркиваем, что под раскраской графа всегда понимается раскраска его вершин, в то время как раскраска карты означает, что раскрашиваются именно ее области. Таким образом, предположение, что каждая плоская карта 4-раскрашиваема, на самом деле эквивалентно приведенной только что формулировке гипотезы четырех красок. Чтобы убедиться в этом, предположим, что гипотеза четырех красок справедлива, и возьмем произвольную плоскую карту G. Пусть G*— граф, являющийся основой карты, геометрически двойственной к карте G. Так как две области карты G смежны тогда и только тогда, когда соответствующие им вершины графа G* смежны, то карта G 4-раскрашиваема, поскольку граф G* 4-раскрашиваем.

 

Обратно, предположим, что каждая плоская карта 4-раскрашиваема. Пусть Н — любой планарный граф, а Н*— граф, двойственный к графу Н и нарисованный так, что каждая его область содержит точно одну вершину графа Н. Связный плоский псевдограф Н* можно перевести в плоский граф Н', добавляя две новые вершины на каждую петлю графа Н* и одну новую вершину на каждое ребро из множества кратных ребер. Теперь 4-раскрашиваемость графа Н' означает 4-раскрашиваемость графа Н. Таким образом, эквивалентность обеих формулировок доказана.

Если будет доказана гипотеза четырех красок, то результат будет неулучшаем, поскольку легко привести примеры планарных 4-хроматических графов. Таковы графы К4 и W6, изображенные на рис. В каждом из этих графов не менее четырех треугольников, что является в силу теоремы Грюнбаума необходимым условием 4-хроматичности.

Теорема. Каждый планарный граф, имеющий меньше четырех треугольников, 3-раскрашиваем.

Отсюда немедленно вытекает следующее утверждение, первоначально доказанное Грётшем.

Следствие (а). Каждый планарный граф, не содержащий треугольников, 3-раскрашиваем.

Любая плоская карта, которая для своей раскраски потребует 5 красок, должна обязательно содержать много областей. Так, Ope и Стемпл показали, что все плоские карты, имеющие не более 39 областей, 4-раскрашиваемы, и тем самым увеличили на 4 число областей в более раннем результате такого типа. Все эти примеры подтверждают гипотезу четырех красок. Как мы сейчас увидим, эту гипотезу в ее формулировке для плоских карт можно попробовать доказывать для специального класса плоских карт.

 

Теорема. Гипотеза четырех красок справедлива тогда и только тогда, когда каждая плоская кубическая карта, не имеющая мостов, 4- раскрашиваема.

Другую интересную эквивалентную форму гипотезы четырех красок предложил Уитни.

Теорема. Гипотеза четырех красок справедлива тогда

и только тогда, когда любой гамильтонов планарный граф

4-раскрашиваем.

Наряду с эквивалентами гипотезы четырех красок, в которых говорится о раскраске областей, существует также эквивалент, в котором рассматривается раскраска ребер.

Раскраской ребер графа G называется такое приписывание цветов его ребрам, что никакие два смежных ребра не получают одинакового цвета. Реберной n-раскраской графа G называется раскраска его ребер, использующая точно n цветов. Хроматическим классом xr' (G) называется такое наименьшее число n, что для графа G существует реберная n-раскраска. Очевидно, что для любого графа, не являющегося вполне несвязным, хr'(G)=xr(L(G)). Нижнюю и верхнюю оценки хроматического класса, мало отличающиеся друг от друга, получил Визинг.

Теорема. Для каждого графа G хроматический класс удовлетворяет неравенствам

D<xr'<D+1

На рисунке показаны два возможных значения хr' (G). В общем случае неизвестно, для каких графов хr' = D.

Теорема. Гипотеза четырех красок справедлива тогда и только тогда, когда xr'(G)=3 для любого кубического планарного графа G, не содержащего мостов.

Следствие (а). Гипотеза четырех красок справедлива тогда и только тогда, когда каждый кубический планарный граф, не содержащий мостов, 1 -факторизуем.

В терминах факторизации теорема допускает обобщение.

Теорема. Для того чтобы связная планарная карта G была 4-раскрашиваема, необходимо и достаточно, чтобы граф G можно было представить в виде суммы таких трех подграфов G1, G2, G3, что для любой вершины v числа ребер из каждого подграфа Gi, инцидентных v, были либо все четные, либо все нечетные.

Существует несколько других гипотез о раскрасках, но именно гипотеза четырех красок получила наибольшую известность. Одну из наиболее интересных гипотез о раскрасках сформулировал Хадвигер ; в ней рассматриваются стягивания.

Гипотеза Хадвигера. Каждый связный n-хроматический граф стягиваем к Кn

Теорема Гипотеза Хадвигера для n=5 эквивалентна гипотезе четырех красок