§ 60. Другие подходы к раскраске графов

В 1943 г. Г. Хадвигер выдвинул гипотезу, тесно свя­занную с проблемой четырех красок.

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

Для п ≤ 4 гипотеза подтверждается. В самом деле, при п = 1 утверждение тривиально. При п = 2 каждый связный граф стягивается к ребру, а при п = 3 — содер­жит цикл и потому стягивается к К₃ . Следующая теоре­ма доказывает гипотезу для п = 4.

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

Пусть G — связный 4-хроматический граф. Если в G есть точки сочленения, то некоторый его блок дол­жен быть 4-хроматическим, иначе из теоремы 53.3 сле­довало бы, что χ(G) < 4. Стянем G к этому блоку. По той же причине блок останется 4-хроматическим после стя­гивания ребер, инцидентных вершине степени 2. Таким образом, не теряя общности, можно считать G блоком со степенями вершин не менее трех.

Пусть C = ( v₁, v₂ ,… , v_p , v₁)— простой цикл макси­мальной длины р в G. Очевидно, что р ≥ 4. Простую цепь, связывающую две несоседние вершины цикла С и не содержащую других вершин этого цикла, назовем С-хордой. Покажем, что для любой вершины v₁ цикла С существует С-хорда, которой принадлежит эта вершина. Так как deg v₁ ≥ 3, то имеется ребро е = v₁u, не принад­лежащее С. Если и € VC, то ребро е является С-хордой. Пусть u ¢ VC. Тогда по теореме 34.1 существует простой цикл Ci=( v₁, u₂ ,… , v₂ ,…, v₁) ,содержащий ребро е и

вершину v₂. Цепь L = (v₁, и, ..., v₂) должна иметь неко­торую вершину v_i отличную от v₂ и принадлежащую циклу С, иначе С не был бы простым циклом макси­мальной длины. Часть цепи L от v₁ до первой вершины, принадлежащей циклу С, и будет искомой С-хордой.

Предположим, что существуют две С-хорды Т1 = (v_i, ..., v_j) и T2=(v_k , ...,v_l ) с общей вершиной t вне С. Тогда часть графа, состоящая из С, Т1 и T2, стя­гивается к К4. Один из вариантов стягивания изображен на рис. 60.1, а.

Теперь рассмотрим случай, когда не существует пе­ресекающихся С-хорд. Любая С-хорда делит цикл С на две простые цепи. Выберем такую С-хорду Т1, чтобы одна из этих цепей С’=( v_i , ...,v_j ) была кратчайшей, и возьмем вершину v_h на этой цепи (такая вершина су­ществует, поскольку С-хорда соединяет две несоседние вершины цикла). Рассмотрим некоторую С-хорду Т2 = (v_k, ..., v_i). Если при этом вершина v_i будет располо­жена на С’, то цепь (v_k, ..., v_i), принадлежащая циклу С, будет короче, чем С’. Следовательно, v_i не лежит на цепи С В этом случае часть графа, состоящая из С, Т1 и Т2, стягивается к К4. Один из вариантов стягивания показан на рис. 60.1, б.

После того как будет получен граф К4 оставшуюся часть исходного графа стянем к К4.

Известно, что утверждение гипотезы Хадвигера при n=5 эквивалентно гипотезе четырех красок. А именно, верна следующая

Теорема 60.2. Следующие два утверждения экви­валентны:

1) гипотеза четырех красок верна;

2) любой связный 5-хроматический граф стягива­ем к К5.

В заключение этого параграфа рассмотрим один алге­браический подход к проблеме раскраски плоских гра­фов. Детально об этом см. [14].

ПустьG — плоский граф, и ψ: VG-> А (где А = {0, а, b, а + b}=(а)+(b) — прямая сумма двух цикли­ческих групп второго порядка) — его раскраска. Тогда условием правильности выбранной раскраски окажется следующее условие: y_ij =ψ(v_i)+ψ(v_j) ≠ 0 для любого реб­ра v_iv_j графа G. Поэтому для произвольного цикла С = (v₁, v₂ , v_n ,.., v_n+1), v_n+1= v₁ должны выполняться условия

Пусть теперь G — произвольный связный граф, каж­дому ребру v_iv_j которого поставлена в соответствие пере­менная y_ij. Получим систему уравнений S(G), записав зоотношения вида (1) для каждого цикла графа G, и си-угему S(G)—для каждого цикла из некоторого фикси­рованного базиса циклов.

Лемма 60.3. Каждому решению системы S(G) при фиксированной окраске ψ(v₀) некоторой вершины v₀ од­нозначно соответствует правильная раскраска графа G четырьмя цветами.

Для заданной вершины v_α € VG рассмотрим произвольную цепь P_a — (v₀ , v₁ , …, v_α) и примем

где y_ij составляют решение системы S(G).

В силу (1) значение ψ{v_α) не зависит от выбора цепи Р_α, поэтому оно определяет цвет вершины v_α. Так как y_ij ≠ 0 для v_iv_j € EG, то любые смежные вершины смеют различные цвета. Таким образом, раскраска, задаваемая формулой (2), правильная.

Так как граф может содержать большое число цик­лов, то перейдем от системы уравнений S(G) к систе­ме S(G).

Теорема 60.4. Каждому решению системы S(G) при фиксированной окраске ψ(v₀) некоторой вершины v₀ однозначно соответству­ет правильная раскраска графа G четырьмя цве­тами.

В силу леммы 60.3 достаточно показать, что решение системы S(G) является и решением си­стемы S(G). Для этого вначале рассмотрим произвольный простой цикл

не принадлежащий базису циклов С’ графа G. Известно (§ 21), что С можно представить в виде суммы по мо­дулю 2 нескольких циклов из С. Пусть С = С1+ С2, С1,С2 € С’

Аналогичные рассуждения можно привести и в том слу­чае, когда цикл С является суммой не двух, а большего числа циклов из базиса циклов С’. Значит, соотношение (1) выполняется для любого простого цикла. Если же цикл С не простой, то необходимо представить его в ви­де объединения нескольких простых циклов, для каждо­го из которых выполняется (1).