Оценка хроматического числа плоского графа.

1. Теорема о пяти красках. Теорема утверждает, что любой граф, обладающий плоской реализацией, может быть правильно раскрашен пятью красками. Вспоминая задачу, сформулированную в начале этой главы, видим, что из этой теоремы следует возможность раскрашивания любой карты пятью цветами.

Вопрос о том, достаточно ли для любой карты четырех красок, до сих пор не решен. Это так называемая проблема четырех цветов. Примеры плоских графов, не раскрашивающихся тремя цветами, строятся очень легко и будут приведены ниже.

Теорема 1: Любой плоский граф 5-хроматичен.

Прежде чем доказывать теорему 1, докажем лемму, которая имеет чисто технический характер и будет использоваться при доказательстве теоремы.

Лемма 1: В любом простом связном плоском графе без тупиков и перешейков существует вершина степени меньшей или равной пяти.

Доказательство: Предположим, что степень любой вершины графа больше пяти. Из этого предположения вытекает следующая оценка для числа ребер графа : .

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

Подставим теперь оценки: в выражение для эйлеровой характеристики графа :

.

Это противоречит тому, что (по теореме 1 §5).

Доказательство теоремы 1: Рассмотрим следующие операции над графом:

1) удаление тупика (вместе с вершиной);

2) склеивание двух ребер, инцидентных одной и той же паре вершин , ;

3) удаление перешейка.

Очевидно, что если после проведения любой из указанных операций над графом его хроматическое число стало равным , то хроматическое число исходного графа есть . Кроме того, после применения некоторого количества операций 1) - 3) получается простой граф, состоящий из конечного числа связных компонент, в каждой из которых нет тупиков и перешейков. Если хроматические числа этих компонент есть , то хроматическое число графа есть . Из этих рассуждений видно, что достаточно доказать следующее утверждение: хроматическое число любого простого связного плоского графа без тупиков и перешейков меньше или равно пяти, т. е. такой граф всегда 5-хроматичен.

Докажем это утверждение. Оно будет доказываться индукцией по числу ребер графа . При этом будет использована лемма 1.

Базис индукции. При теорема верна, так как единственным связным графом без тупиков и перешейков с является треугольник. Треугольник 3-хроматичен, а, следовательно, и 5-хроматичен.

Индукционный шаг. Пусть теорема верна для любого графа с количеством ребер . Рассмотрим (простой плоский без тупиков и перешейков) граф с . По лемме 1 в этом графе существует, по меньшей мере, одна вершина степени меньшей или равной пяти. Зафиксируем одну из таких вершин . Будем различать три случая.

Случай 1. Пусть . Рассмотрим граф , полученный из графа удалением вершины и инцидентных ей ребер. Число ребер такого графа, очевидно, меньше . Применим индукционное предположение, согласно которому этот граф 5-хроматичен. Рассмотрим какую-либо правильную раскраску с помощью пяти красок.

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

Случай 2. Пусть , и не все соседние ребра, выходящие из вершины , образуют треугольники (рис. 19).

Рис. 19

 

Склеим две вершины, смежные с вершиной , инцидентные двум соседним ребрам и не соединенные между собой ребром (на рисунке и ). Применяя преобразование 2), получим из получившегося графа простой граф, в котором число ребер меньше или равно . Рассмотрим существующую по предположению индукции правильную раскраску полученного графа. Она индуцирует некоторую раскраску графа, в которой вершины, ранее склеенные (и ) имеют одинаковую окраску. Полученная раскраска будет правильной, так как эти вершины в графе непосредственно не связаны ребром, и в предположениях случая 2 индукционный шаг также завершен.

Рис. 20

Случай 3. Если и вершина есть центр пятиугольника (рис. 20а). В этом случае обязательно должны существовать две вершины, не соединенные непосредственно ребром, из числа пяти, окружающих (на рисунке это вершины и ), так как в противном случае эти пять вершин образовывали бы второй из графов, упомянутых в теореме 1 §5, и, следовательно, граф не был бы плоским. Удалим вершину с инцидентными ей ребрами (рис. 20б) и склеим и (рис. 20в). Число ребер полученного графа меньше . Рассмотрим его правильную раскраску с помощью пяти красок. Она индуцирует правильную (так как и не соединены ребром непосредственно) раскраску графа , в которой не раскрашена вершина . Заметив, что из пяти вершин, соединенных с вершиной непосредственно, две (и ) раскрашены одинаково. Выводим отсюда, что эта раскраска может быть дополнена до правильной раскраски графа . В предположениях случая 3 индукционный шаг завершен.

Приведем теперь пример плоского графа, для правильной раскраски которого недостаточно трех красок. Такой граф изображен на рис. 21.

Рис. 21

Доказательство того, что для его раскраски недостаточно трех красок, вполне тривиально и предоставляется читателю.

2. Необходимые и достаточные условия 1-й 2-хроматичности. Необходимые и достаточные условия даются следующей теоремой.

Теорема 2: Граф 1-хроматичен тогда и только тогда, когда он не содержит ни одного ребра. Граф 2-хроматичен тогда и только тогда, когда он не содержит циклов нечетной длины.

Доказательство: Первое утверждение теоремы вполне очевидно. Для доказательства второго, очевидно, можно ограничиться случаем связного графа .

Рассмотрим связный граф и рассмотрим частичное дерево этого графа, полученное удалением из него ребер . Очевидно, что оно может быть раскрашено двумя красками. Если в начальном графе был некоторый цикл нечетной длины, то концы того из ребер , которое участвует в этом цикле, окажутся раскрашенными одинаково, ибо путь по дереву, соединяющий эти две вершины, состоит из четного количества ребер. Таким образом, если бы граф мог быть правильно раскрашен двумя красками, то эта раскраска была бы правильной и для частичного дерева; но тогда концы ребра были бы раскрашены одинаково, что невозможно.

Обратно, если граф не содержит циклов нечетной длины, то для любой правильной раскраски частичного дерева концы любого из ребер закрашены по-разному, а, следовательно, индуцированная раскраска графа правильна.