Введение

Теорема о четырёх красках была доказана в 1976 году К. Аппелем и В. Хакеном из Иллинойского университета. Это была первая крупная математическая теорема, доказанная с помощью компьютера. Первым шагом доказательства была демонстрация того, что существует определенный набор из 1936 карт, ни одна из которых не может содержать карту меньшего размера, которая опровергала бы теорему. Аппель и Хакен использовали специальную компьютерную программу чтобы доказать это свойство для каждой из 1936 карт. Изначально доказательство было принято не всеми математиками, поскольку его невозможно было проверить вручную. В дальнейшем оно получило более широкое признание, хотя у некоторых долгое время оставались сомнения [1,2]. Чтобы развеять оставшиеся сомнения, в 1997 году Робертсон, Сандерс, Сеймур и Томас опубликовали более простое доказательство, использующее аналогичные идеи, но по-прежнему проделанное с помощью компьютера. Кроме того, в 2005 году доказательство было проделано Д. Гонтиром с использованием специализированного программного обеспечения (Coq v7.3.1). Таким образом, существование раскраски вершин плоского графа четырьмя красками было обосновано с помощью компьютерного перебора [3].

Однако для полноты картины не хватает строго математического описания механизма раскраски вершин плоского графа, способа описания вычислительных аспектов раскраски плоских графов. Такой механизм имеет и практическое значение. И хотя вычислительные методы раскраски плоских графов мало используются в картографии, с которой эту задачу, как правило, связывают, то в естественных науках и инженерных приложениях она представляет весьма большой интерес. Например, раскраска плоских графов используется при изучении свойств кристаллов [4]. Достаточно рассмотреть свойства кристалла Fe_xTaS₂. Это слоистая структура, принадлежащая к классу дихалькогенидов переходных металлов (TMD), такую структуру можно обнаружить под микроскопом в сплавах металлов и магнитах. Другой пример использования – проектирование плоских конструктивов [5]. Поэтому выявление естественного механизма раскраски и вопрос дедуктивного доказательства данной теоремы представляет практический интерес. Данная работа ставит своей целью произвести дедуктивное доказательство теоремы о четырех красках и описать вычислительный процесс раскраски плоских графов.

1. Максимально плоский граф

Рассмотрим произвольный связный плоский граф G, у которого степень каждой вершины больше двух. В графе G каждую нетреугольную грань путем добавления ребер разобьем на несколько треугольных граней. В итоге получим максимально плоский граф G', все грани которого будут треугольными. И хотя данный процесс неоднозначен, но если граф G' раскрашен, то удаление из него вновь введенных ребер не нарушит его раскраску [6]. Поместим внутри каждой грани s графа G' вершину x⁰. Каждому ребру u графа G' поставим в соответствие ребро u⁰, соединяющее те вершины x⁰_i и x⁰_j, которые соответствуют граням s_i и s_j по обе стороны ребра u. Полученный таким образом топологический граф является плоским, связным и называется или двойственным к G', или однородным графом H степени три, или кубическим графом H.

2. Плоский кубический граф

Понятно, что в плоском кубическом графе вершины соответствуют граням, а грани – вершинам максимально плоского графа. Количество ребер в максимально плоском графе равно количеству ребер двойственного плоского кубического графа. Количество ребер в кубическом графе Н c n вершинами определяется по формуле:

m = 3n/2

(1)

Следовательно, количество ребер в таком графе всегда кратно трем:

m ≡ 0 (mod 3)

(2)

Так как в кубическом графе количество ребер m – целое число, то количество вершин n в однородном кубическом графе должно быть четным числом:

n ≡ 0 (mod 2)

(3)

3. Раскраска плоского кубического графа

С точки зрения раскраски, между максимальным плоским графом G' и двойственным к нему плоским кубическим графом Н существует связь, устанавливаемая следующей теоремой (Тэйта) [7].

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

Теорема Тэйта устанавливает связь между раскраской вершин для максимально плоского графа и раскраской ребер двойственного к нему кубического графа Н. Однако она не утверждает, что любой кубический граф без мостов имеет хроматический класс равный трем. Тэйт высказал предположение, что всякий плоский кубический граф без перешейков имеет гамильтонов цикл. Если бы ему удалось это доказать, то тем самым была бы решена проблема четырех красок, хотя сам Тэйт и не обнаружил этой зависимости. Однако Татт [8,9,10] показал, что это предположение неверно, и привел пример кубического графа с 46 вершинами, не являющегося гамильтоновым (рис. 1).

 

 

Если кубический граф Н имеет хроматический класс равный трем, то его ребра должны быть раскрашены в три цвета. Раскраска предполагает наличие трех разноцветных ребер для каждой вершины графа Н. Кубический граф имеющий хроматический класс равный трем будем называть раскрашенным плоским кубическим графом Н. Например, кубический граф представленный на рис. 2 является раскрашенным кубическим графом Н. Здесь белый цвет будем обозначать буквой W или цифрой 0, а на рисунках графа ребра данного цвета будем представлять штрихпунктирной линией. Красный цвет будем обозначать буквой R или цифрой 1, а на рисунках графа ребра данного цвета будем представлять сплошной линией. Синий цвет, будем обозначать буквой B или цифрой 2, а на рисунках графа ребра данного цвета будем представлять точечной линией. Зеленый цвет будем обозначать буквой G или цифрой 3, а на рисунках графа ребра данного цвета будем представлять пунктирной линией. Согласно теореме Тэйта раскраска ребер индуцирует раскраску граней плоского кубического графа Н, а раскраска граней, в свою очередь, индуцирует раскраску ребер. На рис. 4 представлены 4 способа раскраски граней в зависимости от раскраски ребер.

 

Рис. 3. Обозначение цветных линий

 

Рис. 4. Раскраска граней плоского кубического графа

 

В свою очередь вершине максимального плоского графа может быть поставлена в соответствие грань двойственного плоского кубического графа. Следовательно, нужна математическая структура, одновременно описывающая раскраску и ребер плоского кубического графа без мостов, и граней. Такая математическая структура существует и называется группой Клейна четвертого порядка. Её образует множество цветов при операции преобразования. Таблица преобразования цветов для этой группы имеет вид [11].

(4)

Поставим в соответствие границе грани цикл из базиса квазициклов плоского кубического графа. Квазициклом будем называть цикл с четной валентностью вершин. Гамильтоновым квазициклом будем называть квазицикл с валентностью вершин равной двум, проходящий по всем вершинам графа [12]. Пусть G = (X,U) – граф с пронумерованным множеством ребер U = {u₁, u₂,...,u_m}, a L_G – множество всех суграфов этого графа. Относительно операции сложения (будем называть ее кольцевой суммой) множество L_G образует абелеву группу [13].

(X, U₁) ⊕ (X, U₂) = (X,(U₁ ∪ U₂)\(U₁∩ U₂))

(5)

Действительно, L_G заведомо является группоидом. Относя каждому суграфу G = (X, U) строку чисел (α₁,α₂,...,α_i,...,α_m), в которой i = (1,2,...,m), и определяя сложение строк как покомпонентное по модулю 2, мы получим изоморфный L_G группоид, элементами которого служат все возможные строки длины m из нулей и единиц и который уже представляет собой абелеву группу.

αi =

В дальнейшем группу L_G удобно рассматривать как линейное пространство над полем коэффициентов GF(2) = {0,1}, называемое пространством суграфов данного графа G. Размерность этого пространства dim L_G = m, ибо множество элементов (1,0,....0), (0.1.....0),....(0.0....,1), представляющих однореберные суграфы, образует базис.

С другой стороны, каждый гамильтонов квазицикл есть 2-фактор графа, так как n-фактор – это регулярный суграф степени n. Тогда имеет место следующая теорема для кубических графов (теорема Петерсена) [14].

 

Рис. 5. Кубический граф Петерсена

 

Теорема 2. (Петерсен). Любой кубический граф, не содержащий мостов, можно представить в виде суммы 1-фактора и 2-фактора.

В свою очередь, гамильтонов квазицикл (2-фактор) может состоять из нескольких простых циклов (см. рис. 5,в). Каждый такой простой цикл четной длины будем называть цветным диском. На рис. 6г показаны два диска одного цвета: один проходит по ребрам {u₂,u₃,u₈,u₉,u₁₂,u₁₅}, а другой – по ребрам {u₄,u₅,u₇,u₁₃}. Гамильтонов квазицикл, состоящий из цветных дисков, будем называть цветным гамильтоновым квазициклом или цветным 2-фактором. В раскрашенном кубическом графе обязательно существует цветная конфигурация, состоящая из цветных 2-факторов имеющих диски только четной длины и цветных 1-факторов. Любой цветной гамильтонов квазицикл состоит из дисков. Если цветной диск один, то такой гамильтонов квазицикл – гамильтонов цикл.

4. Свойства раскрашенных плоских кубических графов

Раскрашенные плоские кубические графы обладают следующими свойствами:

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

Свойство 2. Любой цветной гамильтонов квазицикл (2-фактор) порождает два других цветных гамильтоновых квазицикла и производит раскраску графа Н. Если задан цветной гамильтонов квазицикл, то ребра графа этого 2-фактора можно раскрасить в два цвета отличных от его цвета, а нераскрашенные ребра – в цвет самого гамильтонова квазицикла (2-фактора). Таким образом, кубический граф будет раскрашен, а раскраска ребер, в свою очередь, порождает три цветных гамильтоновых квазицикла (2-фактора).

Свойство 3. Сумма по модулю 2 трех цветных гамильтоновых квазициклов (2-факторов), порожденных раскраской кубического графа Н, есть пустое множество. Так как по каждому ребру проходит два цветных гамильтоновых квазицикла и каждое ребро в сумме появляется дважды, что при сложении по модулю 2 тождественно равно ∅, то сумма цветных гамильтоновых квазициклов, порожденных правильной раскраской кубического графа Н, есть пустое множество.

 

Рис. 6. Цветные 2-факторы (гамильтоновы квазициклы)

 

На базисе подпространства циклов графа G можно определить функционал Мак Лейна принимающий нулевое значение, если граф планарен [15]:

F(С) =		=		.

(6)

Здесь S_i – количество изометрических циклов [16] проходящих по ребру i.

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

R_c ⊕ G_c ⊕ B_c = ∅;

(7)

R_f ⊕ G_f ⊕ B_f = H;

(8)

R_f ⊕ R_c = H;

(9)

G_f ⊕ G_c = H;

(10)

B_f ⊕ B_c = H.

(11)

Здесь индекс с обозначает множество ребер, принадлежащих 2-фактору (гамильтонову квазициклу), индекс f обозначает множество ребер, принадлежащих 1-фактору, а Н – множество ребер исходного плоского кубического графа. Кроме того, в раскрашенном кубическом графе любой цветной 2-фактор образуется как конечная кольцевая сумма базисных циклов [13]: R_c – сумма базисных циклов образующих красный 2-фактор; B_c – сумма базисных циклов образующих синий 2-фактор; G_c – сумма базисных х циклов образующих зеленый 2-фактор; W_c – сумма базисных циклов не вошедших ни в красный, ни в синий и ни в зеленый 2-факторы. Проявление свойства двойственности построения цветных 2-факторов описывается следующими выражениями:

R_c = R_c , B_c = B_c , G_c = G_c ,

(12)

где , , являются соответственными дополнениями базисных циклов R_c, B_c, G_c до полного базиса плоского графа и обода графа Н. То есть:

R_c ⊕ R_c = B_c ⊕ B_c = G_c ⊕ G_c = ∅

(13)

5. Раскраска граней плоского кубического графа Н

Будем называть гранью клетку ограниченную базисным циклом. Три цветных 2-фактора порождают (индуцируют) раскраску граней плоского кубического графа Н. В свою очередь, раскраска граней порождает раскраску базисных циклов в цвет грани, так как границей грани служит базисный цикл. Для раскрашенных плоских кубических графов кольцевая сумма базисных циклов и обода согласно теореме Мак Лейна [15] равна

	= ∅.

(14)

С другой стороны, кольцевая сумма трех цветных гамильтоновых квазициклов

R_c ⊕ B_c ⊕ G_c = ∅,

(15)

согласно выражению (2).

Следующее равенство связывает условие планарности Мак Лейна, записанное в виде суммы базисных циклов и обода, с кольцевой суммой трех цветных 2-факторов для плоского кубического графа H

	= Rc ⊕ Gc ⊕ Bc = Rc ⊕ Bc ⊕ Gc = Rc ⊕ Bc ⊕ Gc = Rc ⊕ Bc ⊕ Gc =
= Rc ⊕ Bc ⊕ Gc = Rc ⊕ Bc ⊕ Gc = Rc ⊕ Bc ⊕ Gc = Rc ⊕ Bc ⊕ Gc = ∅.

(16)

Если в раскрашенном плоском кубическом графе Н кольцевую сумму базисных циклов, описывающих границы всех граней красного цвета, обозначить как , кольцевую сумму базисных циклов, описывающих границы граней синего цвета – как , кольцевую сумму базисных циклов, описывающих границы граней зеленого цвета – как , а кольцевую сумму всех базисных циклов, описывающих границы граней белого цвета – как , то с учетом обода можно записать следующие выражения:

G_c =;

(17)

B_c =;

(18)

R_c =.

(19)

В свою очередь, три цветных 2-фактора индуцируют раскраску П граней, где границы граней суть базисные циклы и обод плоского графа Н, а раскраска граней описывается соответствием Г = {П, С, К}. Здесь П – множество пар кортежей <c_i, a_i,1 ✕ 1 + a_i,2 ✕ 2 + a_i,3 ✕ 3 + a_i,4 ✕ 0>, C – множество базисных циклов и обода плоского кубического графа Н, а К – множество четырех цветов. Множество П характеризует раскраску граней плоского кубического графа Н и представляет собой произведение элементов множества С и элементов множества К, а его элементы – это кортежи записанные в виде:

{<c₁, a_1,1 ✕ 1 + a_1,2 ✕ 2 + a_1,3 ✕ 3 + a_1,4 ✕ 0>,

<c₂, a_2,1 ✕ 1 + a_2,2 ✕ 2 + a_2,3 ✕ 3 + a_2,4 ✕ 0>,

……………………….……………………

(20)

<c_m-n+1, a_m-n+1,1 ✕1 + a _m-n+1,2 ✕ 2 + a _m-n+1,3 ✕ 3 + a _m-n+1,4 ✕ 0>,

<c₀, a_m-n+2,1 ✕ 1 + a _m-n+2,2 ✕ 2 + a _m-n+2,3 ✕ 3 + a _m-n+2,4 ✕ 0>}.

Здесь a_i,j {0,1}; i =(1,2,…,m-n+2); j = (1,2,3,4). Коэффициенты a_i,j при базисных циклах определяют принадлежность описывающего границу грани базисного цикла соответствующему цветному 2-фактору. Сложение выполняется по законам операции преобразования группы Клейна, а умножение – по обычным правилам арифметики. Множество базисных циклов и обода С = {c₁,c₂,…,c_m-n+1,c₀}. Множество цветов К = {1,2,3,0}. Следующие пары трех цветных 2-факторов индуцируют разную раскраску граней:

(R_c ⊕ B_c ⊕ G_c ) ∨ (R_c ⊕ B_c ⊕ G_c) индуцирует раскраску Г₁ = {П₁, С, К},

(21)

(R_c ⊕ B_c ⊕ G_c) ∨ (R_c ⊕ B_c ⊕ G_c) индуцирует раскраску Г₂ = {П₂, С, К},

(22)

(R_c ⊕ B_c ⊕ G_c) ∨ (R_c ⊕ B_c ⊕ G_c) индуцирует раскраску Г₃ = {П₃, С, К},

(23)

(R_c ⊕ B_c ⊕ G_c) ∨ (R_c ⊕B_c ⊕ G_c) индуцирует раскраску Г₄ = {П₄, С, К}.

(24)

6. Принцип построения плоских кубических графов

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

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

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

 

 

Плоский кубический граф без мостов с количеством вершин n-2 до введения нового ребра будем называть предыдущим, полученный после введения нового ребра c количеством вершин n – последующим. Ребра, на которых находятся вершины вновь вводимого ребра для предыдущего графа, будем называть сцепленными. Для получения последующего плоского кубического графа сцепленные ребра должны принадлежать базисному циклу. Минимальным графом для первоначального построения является кубический граф с двумя вершинами и тремя ребрами (см. рис. 9).

Заметим, что цвет вновь вводимого ребра соответствует цвету гамильтонового диска (диска 2-фактора), на котором находятся концы вновь вводимого ребра. Действительно, вновь введенное ребро увеличивает количество вершин диска ровно на 2, что не влияет на цвет диска. Это относится также и к удаленным ребрам, не принадлежащим ободу, т. к. удаление ребра уменьшает количество вершин в диске ровно на 2. Если ребро введено или удалено с учетом последнего факта, то в результате получим раскраску нового плоского кубического графа. С учетом описанного, раскраску любого плоского кубического графа можно свести к последовательному рекурсивному процессу:

• удаление ребер из исходного плоского кубического графа без мостов, с целью получения плоского кубического графа, раскраска которого известна;

• определение сцепленных ребер для введения ребра из множества удаленных;

• поиск цветного диска проходящего по сцепленным ребрам;

• раскраска введенного ребра в цвет диска, проходящего по сцепленным ребрам;

• перекраска ребер диска, проходящего по сцепленным ребрам после ввода ребра.

Так как по каждому из сцепленных ребер проходит два разных цветных диска, то обязательно имеется один цветной 2-фактор, принадлежащий обоим сцепленным ребрам. И тогда возможны следующие комбинации: сцепленные ребра принадлежат одному цветному диску соответствующего цветного 2-фактора (1); сцепленные ребра принадлежат двум разным дискам соответствующего цветного 2-фактора (2).

Если сцепленные ребра одного цвета, то выбор цветного 2-фактора из двух других цветных 2-факторов тривиален, если различного – то общий цветной 2-фактор будет третьего цвета. В 1-ом случае (тривиальный случай) вновь введенное ребро может быть легко раскрашено. Покажем, что оно может быть раскрашено и во втором случае.

7. Теорема о существовании цветного диска, проходящего по сцепленным ребрам

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

Лемма 1. Если в предыдущем раскрашенном кубическом графе без мостов G_pr существует цветной диск, проходящий по двум сцепленным ребрам, то последующий кубический граф G_su раскрашен.

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

Лемма 2. Если в предыдущем раскрашенном кубическом графе без мостов G_pr не существует цветного диска, проходящего по двум сцепленным рёбрам, то последующий кубический граф G_su без мостов не плоский и не раскрашиваемый.

Доказательство. Предположим, что в предыдущем раскрашенном кубическом графе G_pr не существует цветного диска, проходящего по сцепленным рёбрам. Тогда существует два одинаково раскрашенных цветных диска, проходящих по сцепленным ребрам. После введения нового ребра в последующий граф G_su, в соответствующем диске какое-то рядом стоящее ребро должно быть окрашено в белый цвет для соответствия правилам раскраски. Так как в этом случае каждый диск, проходящий по вершине нового ребра, увеличится в длину на одну единицу и станет диском нечетной длины (рис. 10). Но тогда ребро, окрашенное в белый цвет, должно индуцироваться тремя разноцветными базисными циклами для удовлетворения группового преобразования Клейна:

W = (R + B + G).

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

 

 

Рассмотрим случай, когда белое ребро может быть индуцировано двумя разноцветными базисными циклами (гранями) имеющими одно общее ребро для удовлетворения группового преобразования Клейна:

W = (R + R)  (B + B)  (G + G)  (W + W),

В этом случае возникает противоречие в раскраске циклов (граней) смежных с раскрашенными циклами (гранями). Эти циклы должны со стороны одного ребра быть раскрашены в один цвет, а со стороны другого ребра – в другой цвет (эти циклы на рис. 11 обозначены знаком вопроса). То есть, циклы должны быть раскрашены двумя цветами одновременно, что невозможно. Мы пришли к противоречию. Следовательно, полученный граф не раскрашиваем. Лемма доказана.

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

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

Доказательство. Если вновь введенное ребро принадлежит базисному циклу предыдущего раскрашенного плоского кубического графа, то последующий кубический граф G_su является плоским по построению. Но тогда в плоском графе не возможно существование белого ребра, т.к. по теореме Маклейна невозможно существование трех циклов проходящих по ребру графа. Следовательно, ребра графа могут быть раскрашены только в три цвета. А это значит, что в предыдущем плоском раскрашенном кубическом графе без мостов G_pr существует цветной диск, проходящий по сцепленным ребрам. Понятие предыдущего раскрашенного плоского кубического графа можно распространить на все множество раскрашенных плоских кубических графов. Теорема доказана.

8. Теорема о реберной раскраске плоского кубического графа

Теорема 4. Хроматический класс произвольного плоского кубического графа без мостов равен трем.

Доказательство проведем методом математической индукции.

а) очевидно, что ребра минимального плоского кубического графа всегда можно раскрасить тремя цветами (см. рис. 9);

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

Следствие 4.1. В плоском кубическом графе без мостов существует цветной 2-фактор с дисками четной длины.

Теорема 5. (Визинг) [17,18]. Рёбра любого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин графа.

По меньшей мере,  цветов необходимо всегда, так что неориентированные графы можно разбить на два класса – графы "первого класса", для которых  цветов достаточно, и "второго класса", для которых необходимо  цветов. Из доказанной теоремы 4 следует, что плоские кубические графы без мостов следует отнести к "первому классу".

9. Теорема о четырех красках

Теперь можно доказать теорему о четырех красках.

Теорема 6. Хроматическое число максимально плоского графа равно четырем.

Это следует из теорем 1 (Тэйта) и 4, а также того факта, что базисные циклы и обод плоского кубического графа Н дуальны вершинам максимально плоского графа G.

10. Ротация цветных дисков

Для поиска диска проходящего по сцепленным ребрам нам понадобится операция перекраски ребер.

 

 

Для перекраски ребер введем операцию ротации. Под ротацией цветного гамильтонова диска будем понимать изменение последовательности раскраски ребер данного диска. Ротация диска приводит к изменению других цветных гамильтоновых квазициклов. На рис. 12 представлен синий диск до ротации, а на рис. 13 – после ротации. Операция ротации дисков может быть описана как перестановка двух ребер в других цветных 2-факторах. Например, для графа, представленного на рис. 6, цветные 2-факторы до ротации синего диска имеют вид:

синий 2-фактор – {e₁,e₃,e₅,e₆,e₇,e₈,e₁₀,e₁₁,e₁₃,e₁₄},

красный 2-фактор – {e₁,e₂,e₄,e₆,e₉,e₁₀,e₁₁,e₁₂,e₁₃,e₁₅},

зеленый 2-фактор – {e₂,e₃,e₄,e₅,e₇,e₈,e₉,e₁₂,e₁₄,e₁₅}.

 

 

После ротации синего диска:

синий 2-фактор – {e₁,e₃,e₅,e₆,e₇,e₈,e₁₀,e₁₁,e₁₃,e₁₄},

красный 2-фактор – {e₁,e₂,e₄,e₇,e₈,e₉,e₁₁,e₁₂,e₁₄,e₁₅},

зеленый 2-фактор – {e₂,e₃,e₄,e₅,e₆,e₉,e₁₀,e₁₂,e₁₃,e₁₅}.

В красном и зеленом 2-факторах произошла перестановка следующих пар ребер (e₆ «e₇), (e₈ «e₁₀), (e₁₃ «e₁₄).

 

Рассмотрим пример, когда для раскраски нового ребра необходимо применить операцию ротации дисков.

Пример 1. На рисунке 16 представлена раскраска кубического графа, где концы вновь введенного ребра принадлежат двум дискам синего цвета и двум дискам зеленого цвета [19,20]. Рассмотрим способы раскраски в этом особом случае. Для данного кубического графа Н (см. рис. 17) выберем базисные циклы:

c₁ = {e₂,e₃, e₈, e₁₀}, c₂ = {e₁, e₂, e₄, e₆}, c₃ = {e₉, e₁₀, e₁₁, e₁₃}, c₄ = {e₄, e₅, e₇, e₁₈},

c₅ = {e₁₁, e₁₂, e₁₄, e₂₃}, c₆ = {e₆, e₇, e₈, e₉, e₁₂, e₁₅, e₁₇, e₂₄}, c₇ = {e₁₆, e₁₇, e₂₀, e₂₂},

c₈ = {e₁₅, e₁₆, e₁₈, e₁₉}, c₉ = {e₂₁, e₂₂, e₂₃, e₂₄}.

Формируем обод, c₀ = {e₁, e₃, e₅, e₁₃, e₁₄, e₁₉, e₂₀, e₂₁}.

 

 

Тогда цветные 2-факторы можно записать в виде:

R_c = (c₂ ⊕ c₄ ⊕ c₈) ⊕ (c₃ ⊕ c₅ ⊕ c₉) = ({e₁, e₂, e₄, e₆} ⊕ {e₄, e₅, e₇, e₁₈} ⊕ {e₁₅, e₁₆, e₁₈, e₁₉}) ⊕ ({e₉, e₁₀, e₁₁, e₁₃} ⊕ {e₁₁, e₁₂, e₁₄, e₂₃} ⊕ {e₂₁, e₂₂, e₂₃, e₂₄}) = {e₁, e₂, e₅, e₆, e₇, e₉, e₁₀, e₁₂, e₁₃, e₁₄, e₁₅, e₁₆, e₁₉, e₂₁, e₂₂, e₂₄};

B_c = (c₁ ⊕ c₂ ⊕ c₃) ⊕ (c₇ ⊕ c₈ ⊕ c₉)  = ({e₂, e₃, e₈, e₁₀} ⊕ {e₁, e₂, e₄, e₆} ⊕ {e₉, e₁₀, e₁₁, e₁₃}) ⊕ ({e₁₆, e₁₇, e₂₀, e₂₂} ⊕ {e₁₅, e₁₆, e₁₈, e₁₉} ⊕ {e₂₁, e₂₂, e₂₃, e₂₄}) = {e₁, e₃, e₄, e₆, e₈, e₉, e₁₁, e₁₃, e₁₅, e₁₇, e₁₈, e₁₉, e₂₀, e₂₁, e₂₃, e₂₄};

G_c = c₁ ⊕ c₄ ⊕ c₅ ⊕ c₇  = {e₂, e₃, e₈, e₁₀} ⊕ {e₄, e₅, e₇, e₁₈} ⊕ {e₁₁, e₁₂, e₁₄, e₂₃} ⊕ {e₁₆, e₁₇, e₂₀, e₂₂} = {e₂, e₃, e₄, e₅, e₇, e₈, e₁₀, e₁₁, e₁₂, e₁₄, e₁₆, e₁₇, e₁₈, e₂₀, e₂₂, e₂₃};

W_c = c₆ ⊕ c₀ = {e₆, e₇, e₈,e₉, e₁₂, e₁₅, e₁₇, e₂₄} ⊕ {e₁, e₃, e₅, e₁₃, e₁₄, e₁₉, e₂₀, e₂₁} = {e₁, e₃, e₅, e₆, e₇, e₈, e₉, e₁₂, e₁₃, e₁₄, e₁₅, e₁₇, e₁₉, e₂₀, e₂₁, e₂₄};

 = c₁ ⊕ c₆ ⊕ c₇  ⊕ c₀ = {e₂, e₃, e₈, e₁₀} ⊕ {e₆, e₇, e₈, e₉, e₁₂, e₁₅, e₁₇, e₂₄} ⊕ {e₁₆, e₁₇, e₂₀, e₂₂} ⊕ {e₁, e₃, e₅, e₁₃, e₁₄, e₁₉, e₂₀, e₂₁} = {e₁, e₂, e₅, e₆, e₇, e₉, e₁₀, e₁₂, e₁₃, e₁₄, e₁₅, e₁₆, e₁₉, e₂₁, e₂₂, e₂₄};

 = c₄ ⊕ c₅ ⊕ c₆ ⊕ c₀= {e₄, e₅, e₇, e₁₈} ⊕ {e₁₁, e₁₂, e₁₄, e₂₃} ⊕ {e₆, e₇, e₈, e₉, e₁₂, e₁₅, e₁₇, e₂₄} ⊕ {e₁, e₃, e₅, e₁₃, e₁₄, e₁₉, e₂₀, e₂₁} = {e₁, e₃, e₄, e₆, e₈, e₉, e₁₁, e₁₃,e₁₅, e₁₇, e₁₈, e₁₉, e₂₀, e₂₁, e₂₃, e₂₄};

= c₂ ⊕ c₃ ⊕ c₆ ⊕ c₈ ⊕ c₀ = {e₁, e₂, e₄, e₆} ⊕ {e₉, e₁₀, e₁₁, e₁₃} ⊕ {e₆, e₇, e₈, e₉, e₁₂, e₁₅, e₁₇, e₂₄} ⊕ {e₁₅, e₁₆, e₁₈, e₁₉} ⊕ {e₁, e₃, e₅, e₁₃, e₁₄, e₁₉, e₂₀, e₂₁} = {e₂, e₃, e₄, e₅, e₇, e₈, e₁₀, e₁₁, e₁₂, e₁₄, e₁₆, e₁₇, e₁₈, e₂₀, e₂₂, e₂₃}.

Осуществим операцию ротации дисков. Будем вращать два единичных диска зеленого цвета с₁ = {e₂, e₃, e₈, e₁₀} и c₇ = {e₁₆, e₁₇, e₂₀, e₂₂}.

Новая раскраска характеризуется другим набором цветных 2-факторов и 1-факторов и позволяет раскрасить вновь введенное ребро красным цветом.

R_c = c₁ ⊕ c₂ ⊕ c₃ ⊕ c₄ ⊕ c₅ ⊕ c₇ ⊕ c₈ ⊕ c₉ = {e₂, e₃, e₈, e₁₀} ⊕ {e₁, e₂, e₄, e₆} ⊕ {e₉, e₁₀, e₁₁, e₁₃} ⊕ {e₄, e₅, e₇, e₁₈} ⊕ {e₁₁, e₁₂, e₁₄, e₂₃} ⊕ {e₁₆, e₁₇, e₂₀, e₂₂} ⊕ {e₁₅, e₁₆, e₁₈, e₁₉} ⊕ {e₂₁, e₂₂, e₂₃, e₂₄} =  {e₁, e₃, e₅, e₆, e₇, e₈, e₉, e₁₂, e₁₃, e₁₄, e₁₅, e₁₇, e₁₉, e₂₀, e₂₁, e₂₄};

 

 

B_c = c₂ ⊕ c₃ ⊕ c₈ ⊕ c₉  = {e₁, e₂, e₄, e₆} ⊕ {e₉, e₁₀, e₁₁, e₁₃} ⊕ {e₁₅, e₁₆, e₁₈, e₁₉} ⊕ {e₂₁, e₂₂, e₂₃, e₂₄}) = {e₁, e₂, e₄, e₆, e₉, e₁₀, e₁₁, e₁₃, e₁₅, E₁₆, E₁₈, E₁₉, E₂₁, E₂₂, E₂₃, E₂₄};

G_c = c₁ ⊕ c₄ ⊕ c₅ ⊕ c₇  = {e₂, e₃, e₈, e₁₀} ⊕ {e₄, e₅, e₇, e₁₈} ⊕ {e₁₁, e₁₂, e₁₄, e₂₃} ⊕ {e₁₆, e₁₇, e₂₀, e₂₂} = {e₂, e₃, e₄, e₅, e₇, e₈, e₁₀, e₁₁, e₁₂, e₁₄, e₁₆, e₁₇, e₁₈, e₂₀, e₂₂, e₂₃}.

Применение операции ротации двух зеленых дисков изменяет цвета базисных циклов с красного на синий (см. рис. 18), и тогда вновь вводимое ребро можно окрасить в красный цвет (см. рис. 19).

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

Пример 2. Рассмотрим раскраску ребер для плоского кубического негамильтонового графа G₄₄ (см. рис. 20).

 

Рис. 20. Плоский кубический негамильтонов граф G44.

 

Рис. 21. Удаление ребер в плоском кубическом негамильтоновом графе G44.

 

С целью получения совокупности циклов четной длины (дисков) удаляем из графа ребра (v2,v7),(v24,v25),(v35,v39).

 

Рис. 22. Раскраска ребер в выделенных дисках (пусть диски будут зеленые).

 

Рис. 23. Определение цветного диска для введения ребра (v₂₄,v₂₅).

 

Визуально, находим цветной диск для введения ребра (v₂₄, v₂₅). Это диск <v₅, v₁₃,v₂₂, v₂₃,v₂₉, v₂₇,v₂₈, v₉,v₈, v₂₆,v₂₁, v₆>.

 

Рис. 24. Введение и раскраска ребра (v₂₄,v₂₅).

 

Введение и раскраска ребра (v₂₄, v₂₅) представлена на рис. 24. Осуществляется перекраска ребер цветного диска <v₅, v₁₃, v₂₂, v₂₃, v₂₅, v₂₉, v₂₇, v₂₈, v₉, v₈, v₂₆, v₂₄, v₂₁, v₆>.

 

Рис. 25. Определение цветного диска для введения ребра (v35,v39).

 

Визуально определяем диск <v16, v17, v20, v19, v40, v41, v42, v37, v38, v36, v34, v18> (см. рис. 25) для введения ребра (v35, v39).

 

Рис. 26. Введение и раскраска ребра (v₃₅,v₃₉).

 

Вводим и раскрашиваем ребро (v₃₅,v₃₉), перекрашиваем ребра в цветном диске (см. рис. 26) <v16,v17,v20,v19,v39,v40,v41,v42,v37,v38,v36,v35,v34,v18>.

 

Рис. 27. Определение ротации цветного диска для введения ребра (v₂,v₇).

 

Осуществляем ротацию цветного диска <v₁₅,v₁, v₃,v₄₄> с целью введения ребра (v₂, v₇).

 

Рис. 28. Нахождение цветного диска для введения ребра (v₂,v₇) после ротации.

 

Находим цветной диск <v1, v3, v10, v9, v28, v30, v31, v43, v44, v15, v14, v11, v12, v13, v22, v21, v24, v25, v23, v33, v32, v29, v27, v26, v8, v6, v5, v4> для введения ребра (v2, v7). Окончательная раскраска негамильтонового графа G44 представлена на рис. 29.

 

Рис. 29. Окончательная раскраска негамильтонового графа G₄₄.

 

Пример 3. Произведем раскраску ребер в негамильтоновом графе G₄₆.

 

Рис. 30. Кубический негамильтонов граф G₄₆.

 

Рис. 31. Удаление ребер с целью получения дисков четной длины.

 

Удаляем из графа ребра (v₉,v₃₃), (v₃,v₁₈), (v₃₀,v₄₆), (v₆,v₂₆), (v₃₈,v₄₄) с целью получения дисков четной длины.

 

Рис. 32. Диски четной длины.

 

Рис. 33. Раскраска дисков четной длины.

 

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

 

Рис. 34. Введение ребра (v₃₀, v₄₆).

 

Рис. 35. Поиск диска для введения ребра (v₃₀,v₄₆).

 

Осуществляем поиск цветного диска для введения ребра (v₃₀, v₄₆). Это синий диск <v₄₅,v₃₂, v₃₁,v₂₉, v₂₇,v₂₈>.

 

Рис. 36. Введение ребра (v₃₀, v₄₆) и перекраска ребер диска.

 

Вводим ребро (v₃₀, v₄₆) и осуществляем перекраску ребер диска <v₄₅,v₃₂, v₃₁,v₃₀, v₂₉,v₂₇, v₂₈,v₄₆>. Определяем цветной диск <v₂₇, v₂₈, v₇, v₅, v₂₅, v₂₃, v₂₀, v₄, v₂, v₁₂, v₁₁, v₁₀, v₁, v₈, v₄₅, v₄₆, v₃₀, v₂₉, v₄₂, v₄₃, v₃₁, v₃₂, v₁₃, v₁₄, v₁₅, v₁₆, v₁₇, v₁₉, v₂₁, v₂₂, v₃₇, v₂₄> с сцепленными ребрами для введения ребра (v₆, v₂₆))

 

Рис. 37. Введение ребра (v₆, v₂₆) и перекраска ребер диска.

 

Рис. 38. Поиск цветного диска для введения ребра (v₉,v₃₃).

 

Осуществляем поиск диска для введения ребра (v₉, v₃₃). Это диск <v₁₇, v₁₉,v₂₁, v₂₂,v₃₇, v₂₄,v₂₆, v₂₇,v₂₈, v₇,v₆, v₅,v₂₅, v₂₃,v₂₀, v₄,v₂, v₁₂,v₁₁, v₁₀,v₁, v₉,v₈, v₄₅,v₄₆, v₃₀,v₂₉, v₄₂,v₄₃, v₃₁,v₃₂,v₃₃, v₁₃,v₁₄, v₁₅,v₁₆>.

 

Рис. 39. Введение ребра (v₉, v₃₃) и перекраска ребер цветного диска.

 

Введение ребра (v₉,v₃₃) и перекраска ребер цветного диска. Определение диска для введения ребра (v₃,v₁₈).

Рис. 40. Введение ребра (v₃, v₁₈) и перекраска ребер цветного диска.

 

Рис. 41. Определение местоположения для введения ребра (v₃₈,v₄₄).

 

Нахождение цветного диска <v₃₄,v₃₅, v₃₆,v₃₉, v₄₀,v₄₁> для введения ребра (v₃₈, v₄₄).

 

Рис. 42. Окончательная раскраска кубического негамильтонового графа G₄₆.

 

Пример 4. Раскрасим кубический негамильтонов граф G₄₂.

 

Рис. 43. Кубический негамильтонов граф G₄₂.

 

Рис. 44. Удаление ребер для получения дисков четной длины.

 

Удаляем из графа ребра (v₃,v₁₁),(v₁₈,v₂₂),(v₇,v₂₈),(v₃₅,v₃₉),(v₄₁,v₄₂) с целью получения дисков четной длины.

 

Рис. 45. Построение дисков четной длины.

 

Рис. 46. Раскраска дисков четной длины (синий цвет).

 

Производим раскраску дисков четной длины в синий цвет и производим раскраска соответствующего 1-фактора также в синий цвет.

 

Рис. 47. Ротация цветного диска для введения ребра (v₄₁,v₄₂).

 

Осуществляем ротацию цветного диска <v₂₁,v₁₆, v₁₇,v₁₄, v₁₀,v₉, v₂,v₁, v₈,v₃₀, v₂₉,v₃₂, v₃₆,v₃₇, v₄₀,v₂₄> для введения ребра (v₄₁, v₄₂).

 

Рис. 48. Перекраска ребер в процессе ротации цветного диска.

 

После проведения ротации, определяем цветной диск <v₂₅, v₃₈,v₄₀, v₂₄>для проведения ребра (v₄₁,v₄₂).

 

Рис. 49. Введение ребра (v₄₁, v₄₂) и перекраска ребер цветного диска.

 

После введения ребра (v₄₁,v₄₂) осуществляем ротацию цветных дисков <v₂₁, v₂₃,v₂₅, v₂₄> и <v₁₄, v₁₅,v₁₉, v₁₇> для введения ребра (х₁₈,х₂₂).

 

Рис. 50. Раскраска ребер цветного диска после введения ребра (v₁₈,v₂₂).

 

После введения ребра (v₁₈,v₂₂) перекрашиваем ребра цветного диска <v₁₆, v₁₇,v₁₈, v₁₉,v₂₀, v₂₃,v₂₂, v₂₁>. Далее производим ротацию диска <v₂₁,v₂₄, v₂₅,v₂₃, v₂₀,v₁₃, v₄,v₂, v₉,v₁₆, v₁₇,v₁₄, v₁₀,v₁₂, v₁₅,v₁₉, v₁₈,v₂₂> для введения ребра (v₃, v₁₁).

 

Рис. 51. Введение ребра (v₃, v₁₁) и перекраска ребер в цветном диске.

 

Для введения ребра (v₃₅,v₃₉) производим ротацию цветного диска <v₃₁, v₃₂,v₃₆, v₃₄>.

 

Рис. 52. Перекраска ребер после операции ротации цветного диска.

 

Производим перекраску ребер цветного диска <v₃₁, v₃₂,v₃₆, v₃₄>.

 

Рис. 53. Введение ребра (v₃₅, v₃₉) и перекраска ребер цветного диска.

 

Вводим ребро (v₃₅,v₃₉) и перекрашиваем ребра цветного диска <v₃₃, v₃₄,v₃₅, v₃₆,v₃₇, v₄₀,v₃₉, v₃₈>

 

Рис. 54. Определение цветного диска для введения ребра (v₇,v₂₈).

 

Осуществляем ротацию диска <v₆,v₈, v₃₀,v₃₇, v₄₀,v₄₂, v₂₄,v₂₁, v₁₆,v₁₇, v₁₈,v₂₂, v₂₃,v₂₅, v₄₁,v₃₈, v₃₉,v₃₅, v₃₆,v₃₂, v₂₉,v₂₇, v₃₁,v₃₄, v₃₃,v₂₆> для введения ребра (v₇, v₂₈). Введение ребра (v₇,v₂₈) и окончательная раскраска негамильтонового графа G₄₂:

 

Рис. 55. Окончательная раскраска негамильтонового графа G₄₂.

11. Визуальный алгоритм раскраски ребер

шаг 0. [Инициализация]. Удаляем ребра из графа для получения цветных дисков.

шаг 1. [Раскраска выбранных дисков]. Раскрашиваем ребра выбранных дисков двумя цветами. Ребра цветного 1-фактора раскрашиваем третьим цветом.

шаг 2. [Поиск цветного диска для сцепленных ребер]. Выбираем вводимое ребро. Визуально осуществляем поиск цветного диска для сцепленных ребер выбранного вводимого ребра. Если такого цикла не найдено, идем на шаг 3. Иначе на шаг 4.

шаг 3. [Осуществляем ротацию цветных дисков]. Осуществляем ротацию цветных дисков для получения цветного диска, проходящего по сцепленным ребрам.

шаг 4. [Проверка подключения ребра]. Проверяем подключение ребер. Если не все ребра подключены, то идем на шаг 2. Иначе конец работы алгоритма.

Выводы

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

Для проведения вычислительного процесса раскраски и перекраски ребер плоского кубического графа в три цвета введена операция ротации цветных дисков. Вычислительную сложность алгоритма можно определить в зависимости от количества удаленных ребер графа как О(m).

Список литературы

1.                          K. Appel. The solution of the four-color-map problem // SciAm, Oct. 1977. P. 108–121.

2.                          K. Appel, W. Haken. Every Planar Map Is Four Colorable // Contemporary Mathematics. Providence (R.I.): Amer. Math Soc., 1989. Vol. 98. 308 р.

3.                          В.В. Родионов. Методы четырехцветной раскраски вершин плоских графов / В.В. Родионов - М.: КомКнига, 2005. – 48с.

4.                          Y. Horibe, J. Yang, Y.-H. Cho et al. Color Theorems, Chiral Domain Topology, and Magnetic Properties of FexTaS2 // J. Am. Chem. Soc., 2014, 136 (23), pp 8368–8373.

5.                          С.В. Курапов, М.В. Давидовский. Топологический подход к проведению соединений в плоских конструктивах // Компоненты и технологии. 2015. № 11. С. 127–130;

6.                          Ф. Харари. Теория графов. – Пер. с англ. Козырева В.П. / под ред. Гаврилова В.Г. / Ф. Харари – М.: Мир. – 1973. – 300 с.;

7.                          P.G. Tait. Remarks on the Colourings of Maps // Proc. R. Soc. Edinburgh 10: 729, 1880.

8.                          W.T. Tutte. Non-Hamiltonian Planar Maps // Graph Theory and Computing, ed. R. Read. Academic Press, New York, 1972, pp. 295–301.

9.                          W.T. Tutte. On Hamiltonian Circuit // J. London Math. Soc. 21 (1946) 98–101.

10.                      Н.З. Шор, Г.А. Донец. Алгебраический подход к проблеме раскраски плоских графов / Г.А. Донец, Н.З. Шор - Київ: Наук.думка. - 1982. - 144с.

11.                      И. Гроссман. Группы и их графы / Гроссман, И., Магнус В. – М.: Мир, 1971, - 238с.

12.                      А.А. Зыков. Основы теории графов. / Зыков А.А. - М.: Наука, ГРФМЛ, 1987, - 384с.

13.                      М. Свами. Графы, сети и алгоритмы. М.: Мир. – 1984. – 455 с.;

14.                      Ф. Харари. Теория графов. – Пер. с англ. Козырева В.П. / под ред. Гаврилова В.Г. / Ф. Харари – М.: Мир. – 1973. – 300 с.;

15.                      С. Мак Лейн. Комбинаторное условие для плоских графов / С. Мак-Лейн // В кн.: Кибернетический сборник. Новая серия. – 1970. Вып. 7. – С.133–144.;

16.                      T. Kavitha et. al. Cycle bases in graphs: characterization, algorithms, complexity, and applications // Computer Science Review, 3 (2009), 199-243.

17.                      Э. Рейнгольд. Комбинаторные алгоритмы, теория и практика. / Э. Рейнгольд, Ю. Нивергельт, Н. Део - М.: Мир.- 1980. – 480 с;

18.                      В.Г. Визинг. Об оценке хроматического класса р-графа // сб. Дискретный анализ. – Новосибирск: Институт математики СО АН СССР, 1964. – Т. 3. – С. 25–30.

19.                      В.Г. Визинг. Критические графы с данным хроматическим классом // сб. Дискретный анализ. – Новосибирск: Институт математики СО АН СССР, 1965. – Т. 5. – С. 9–17.

20.                      С.В. Курапов, М.В. Давидовский. Раскраска плоских графов. Теория, методы, алгоритмы. / Издательский Дом: LAP LAMBERT Academic Publishing, 2015, 142 c. IBSN 3659811246

---

Visual algorithm for coloring planar graphs

Authors: S.V. Kurapov^1,A, M.V. Davidovsky^2,A, A.V. Tolok^3,B

^A Zaporozhye National University, Ukraine

^B Moscow State Technological University «STANKIN», Russia

¹ ORCID: 0000-0003-4563-7227, lilili5050@rambler.ru

² ORCID: 0000-0002-9472-3351, m.davidovsky@gmail.com

³ ORCID: 0000-0002-7257-9029, a.tolok@stankin.ru

 

Abstract

This article addresses a plane graph coloring problem. The authors propose a new visual algorithm for coloring planar graphs and present a deductive proof of the four-color theorem which is based on the properties of the Klein four-group. It is shown that an arbitrary colored cubic graph has three colored 2-factors and the addition of colors is done according to the laws of the Klein four-group transformation. The properties of colored plane cubic graphs are considered. Two theorems about the existence of a colored disk passing through linked edges and about edge coloring of a plane cubic graph are formulated and proved in the article. Moreover, it is shown that the four-color theorem can be obtained as a consequence of these proved theorems. In order to allow edge recoloring in a colored plane cubic graph the authors introduce a new operation – the rotation of a colored disk. The article provides examples of solving the problem of planar graphs coloring.

 

Keywords: graph, graph coloring, maximal planar graph, isometric cycles, Klein four-group, graph factors.

References

               

1.                          K. Appel. The solution of the four-color-map problem // SciAm, Oct. 1977. P. 108–121.

2.                          K. Appel, W. Haken. Every Planar Map Is Four Colorable // Contemporary Mathematics. Providence (R.I.): Amer. Math Soc., 1989. Vol. 98. 308 р.

3.                          V.V. Rodionov. Metody chetyrekhtsvetnoi raskraski vershin ploskikh grafov. – M.: KomKniga, 2005. – 48s.

4.                          Y. Horibe, J. Yang, Y.-H. Cho et al. Color Theorems, Chiral Domain Topology, and Magnetic Properties of FexTaS2 // J. Am. Chem. Soc., 2014, 136 (23), pp 8368–8373.

5.                          S.V. Kurapov, M.V. Davidovskii. Topologicheskij podhod k provedeniyu soedinenij v ploskih konstruktivah // Komponenty i tekhnologii. 2015. № 11. S. 127–130;

6.                          F. Harary. Graph Theory, Reading: Addison-Wesley. – 1969.

7.                          P.G. Tait. Remarks on the Colourings of Maps // Proc. R. Soc. Edinburgh 10: 729, 1880.

8.                          W.T. Tutte. Non-Hamiltonian Planar Maps // Graph Theory and Computing, ed. R. Read. Academic Press, New York, 1972, pp. 295–301.

9.                          W.T. Tutte. On Hamiltonian Circuit // J. London Math. Soc. 21 (1946) 98–101.

10.                      N. Z. Shor, G. A. Donets. Algebraic Approach to the Plane Graph Coloring. Naukova Dumka, 1982, English translation published by Springer-Verlag, Berlin, 1985.

11.                      I. Grossman. Gruppy i ikh grafy / Grossman, I., Magnus, V. – M.: Mir, 1971, - 238s.

12.                      A.A. Zykov. Osnovy teorii grafov. / Zykov A.A. - M.: Nauka, 1987, - 384s.

13.                      M.N. S. Swamy, K. Thulasiraman. Graphs, networks, and algorithms. – J. Wiley & Sons, 1981.

14.                      F. Harary. Graph Theory, Reading: Addison-Wesley. – 1969.

15.                      S. Mac Lane. A combinatorial condition for planar graphs // Fund. Math., 28. – 1937. – P. 22–32.

16.                      T. Kavitha et. al. Cycle bases in graphs: characterization, algorithms, complexity, and applications // Computer Science Review, 3 (2009), 199-243.

17.                      E.M. Reingold, J. Nievergelt, N. Deo. Combinatorial Algorithms: Theory and Practice. Englewood Cliffs: Prentice-Hall, 1977.

18.                      V.G. Vizing. On an estimate of the chromatic class of a p-graph // Diskret. Analiz., 3: 25–30.

19.                      V.G. Vizing. Critical graphs with given chromatic class // Metody Diskret. Analiz., 5: 9–17.

20.                      S.V. Kurapov, M.V. Davidovsky. Raskraska ploskikh grafov. Teoriia, metody, algoritmy. LAP LAMBERT Academic Publishing, 2015, 142 c. IBSN 3659811246