3.2 Структурные свойства Sn (p r)

Граф S_n (P R) обладает также следующими свойствами, вытекающими из его иерархической структуры и свойств префикс-реверсалов.

6

^{Утверждение 3. В графе S}_n ^{(P R), n ≥ 3, содержится ровно n!}

незави-

^{симых циклов длины шесть, т.е. через любую вершину графа проходит}

ровно один цикл длины шесть.

Доказательство. Без ограничения общности, рассмотрим единичную перестановку I = [123] на трех элементах.Тогда верно следующее:

^→

[123] ^r1

^→

[213] ^r2

^→

[312] ^r1

^→

[132] ^r2

^→

[231] ^r1

^→

[321] ^r2

[123]

6

Таким образом, любой цикл длины шесть C₆ в графе S_n (P R) получается действием префикс-реверсалов на некоторую перестановку π справа сле- дующим образом: C₆ = πr₁ r₂r₁r₂ r₁r₂. Действие r_i , i > 2, позволяет соеди- нить два разных цикла длины шесть по описанному выше иерархическому построению графа. Циклы длины шесть не пересекаются по вершинам и ребрам, т.е. являются независимыми. Таких циклов длины шесть всего будет ^n! .

Определим метрическую сферу радиуса k с центром в вершине u ∈ V (G) как множество S_k (v) = {u ∈ G : d(u, v) = k}. Рассмотрим в графе S_n (P R) метрические сферы S_k (I ), 1 6 k 6 d, где d диаметр графа. Учи-

^{тывая, что граф S}_n ^{(P R) является вершинно-транзитивным, перестановку}

^{I будем опускать и для краткости писать S}_k ^{= S}_k ^{(I ).}

Утверждение 4. В графе S_n (P R), n ≥ 4 имеем |S₃ | = n³ − 5n² + 8n − 5.

Доказательство. Так как в графе S_n (P R) нет циклов C₃, C₄, C₅, а по

^{Утверждению 3 через каждую вершину проходит один цикл C}₆ ^{, то на}

^{третьем слое имеем |S}₃^{| = |S}₂ ^|(|S₁ ^{| − 1) − 1. Поскольку |S}₂ ^{| = |S}₁ ^|(|S₁^{| − 1)}

^{и |S1 | = n − 1, то |S3| = (n − 1)(n − 2)2 − 1 = n3 − 5n2 + 8n − 5.}

^{Введем некоторые обозначения. Определим числа ci (u), bi (u) и ai (u), 2 ≤}

^{i ≤ d, для вершины u ∈ V (G), следующим образом ci (u) = |{v ∈ Si−1 :}

^{d(v, u) = 1}|, bi (u) = |{v ∈ Si+1 : d(v, u) = 1}| и ai (u) = |{v ∈ Si : d(v, u) =}

^{1}|. Запись (ci , ai , bi ), 2 ≤ i ≤ d, будем называть (ci , ai , bi ) – вектором}

^{вершины u.}

3.3 Граф S₄(P R) и его свойства

n!(n−1)

Рассмотрим граф S₄(P R) с числом вершин и ребер |V | = n! = 24, |E| =

₂ ^{= 36, соответственно. Этот граф регулярный, со степенью вершин}

^{∆ = 3.}

3.3.1 Хроматические cвойства S₄(P R)

Утверждение 5. χ(S₄(P R)) = 3.

Доказательство. Заметим, что в данном графе есть цикл C₇, а значит χ(S₄(P R)) = 2. В силу (3.1), χ(S₄ (P R)) ≤ 3, значит существует раскраска графа в три цвета.

Хроматическое число также можно получить, используя оценку через мощ- ность независимого множества S₄(P R). Число независимости α(S₄ (P R)) =

10

^{10. Тогда из оценки (1.1) имеем: d 24 e = 3 ≤ χ(S}4 ^{(P R)) ⇒ χ(S}4^{(P R)) = 3,}

^{в силу оценки (3.1).}

Приведем один из способов покраски S₄(P R) в три цвета, используя слоевую структуру. Число вершин в метрических сферах, в силу Утвер- ждения 4 и 2 определяется как |S₁ | = 3, |S₂| = 6, |S₃| = 11, |S₄ | = 3. Покрасим вершину I = [1234] в цвет 1. Тогда все вершины слоя S₁ мож- но покрасить в цвет 2. В графе, по Утверждению 2, нет циклов C₃, C₄, C₅ , то все вершины слоя S₂ можем покрасить в цвет 1. Вершина [1324] принадлежит шестиугольнику, проходящему через вершину I , покрасим ее в цвет 2. Остальные вершины слоя S₃ можно покрасить в цвет 2 и цвет

3, но с некоторым ограничением, вытекающим из строения вершин слоя

S₄. Так как в графе есть цикл длины семь, проходящий через вершину I , то вершины слоя S₃ не могут быть покрашены только в цвет 2. Осталось распределить цвета в слое S₄. Вершина [4231] имеет (3; 0; 0) – вектор, т.е. смежна с вершинами только из предыдущего слоя и может быть покраше- на в цвет 1. Две оставшиеся вершины [2413], [3142] с (2; 1; 0) – векторами, являются смежными, тогда покрасим одну из вершин в цвет 2 или 3, а вторую в цвет 1. Таким образом, две вершины из S₃, с (1; 1; 1) – вектором, смежные с данными вершинами, должны иметь одинаковый цвет. Напри- мер, можно покрасить вершины [1342], [4132] в цвет 2, что определит (в вершинах [1423], [3241] останется выбор) некоторую правильную раскрас- ку слоя S₃ .

3.3.2 Структурные свойства S₄ (P R)

Лемма 1. В графе S₄(P R) есть четыре независимых доминирующих множества D_i , i = 1, 4. Причем γ(S₄ (P R)) = 6 и любая вершина v ∈ S₄(P R)\D_i смежна ровно с одной вершиной u ∈ D_i , ∀i = 1, 4.

Доказательство. Построим независимое множество D в графе так, что d(u, v) = 3 ∀u, v ∈ D. Данное множество D будет доминирующим, так как оно покрывает все вершины графа. Таких множеств D будет четыре, так как число способов выбрать из четырех щестиугольников три вычисляется

_{как C 3 =} 4! _{= 4.}

⁴ 3!

^{На рис. 3.2 показаны доминирующие множества D}_i ^{, i = 1, 4 графа}

^S₄^{(P R). Вершины множества D}_i ^{обозначаются цифрой i.}

_{1 4}

₃ ^✟✟❍❍ ₂

^{2 ❍}_❍✟^{✟ 3}

¹

₃ ^✟✟❍❍ ₂

2

^{2 ❍}_❍✟^{✟ 3}

⁴

3

_{4 ✟}✟❍_{❍ 1}

^{1 ❍}_❍✟^{✟ 4}

³

_{4 ✟}✟❍_{❍ 1}

^{1 ❍}_❍✟^{✟ 4}

²

Рис. 3.2. Доминирующие множества графа S₄ (P R)

Обозначим некоторое независимое доминирующие множества в графе S₄(P R) как D-множество. Теперь покажем, как граф S₄(P R) можно по- красить в три цвета на основе его D-множеств.

Определение 1. Пусть заданы три цвета {1, 2, 3}. Будем говорить, что вершина имеет двухцветную (k, l)-метку, k, l ∈ {1, 2, 3}, если она может быть покрашена в один из этих цветов.

Лемма 2. Если в цикле C₆ есть произвольная двухцветная метка на всех вершинах, то его можно раскрасить либо в два, либо в три цвета.

3

⁼

2!

Доказательство.Число возможных двухцветных меток C ^{2 3!}

= 3.

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

Утверждение 6. Граф S₄ (P R) будет 3-раскрашиваемым при произволь- ной раскраске вершин любого D-множества.

Доказательство. Вершины любого D-множества являются независи- мыми, значит они могут быть покрашены в любые цвета. Тогда, вер- шины V (S_n (P R))\D, получают некоторые двухцветные метки. Эти вер- шины принадлежат двум независимым циклам C₁₂ и C₆, которые 3-рас- крашиваемые по Лемме 2 (аналогичными рассуждениями утверждение доказывается для цикла C₁₂ ) при любых двухцветных метках.

Следствие. Если вершины некоторого C₆ в S₄ (P R) имеют правильную

^{3-раскраску, то граф S}₄^{(P R) всегда можно покрасить в три цвета.}

Доказательство. Если C₆ имеет 3-раскраску, то все вершины D-множес- тва получат двухцветную метку, и по Утверждению 6 граф S₄(P R) всегда можно покрасить в три цвета.

3.3.3 Число раскрасок S₄(P R)

Рассмотрим различные способы покраски S₄ (P R). При подсчете числа раскрасок, будем учитывать, что все вершины графа помечены, так как они соответствуют различным перестановкам.

Лемма 3. Число раскрасок S₄ (P R) в три цвета так, чтобы два его ше- стиугольника были раскрашены в два одинаковых цвета, равно 648.

3

Доказательство. Зафиксируем раскраску двух шестиугольников. То- гда раскраска третьего выбирается шестью, а четвертого тремя спо- собами. Учитывая, что цвета двух шестиугольников можно выбрать A² способами, а также выбор шестиугольников 6 способами, число раскрасок

_{вычисляется следующим образом: A2 · 6 · 6 · 3 =} 3! _{· 6 · 6 · 3 = 648.}

³ 1!

Лемма 4. Число раскрасок S₄(P R) в три цвета так, чтобы два шести- угольника были раскрашены в два разных цвета, равно 4968.

3

Доказательство. Зафиксируем раскраску первого шестиугольника. То- гда раскраска второго выбирается тремя способами. Для третьего и чет- вертого шестиугольника, при фиксированной раскраске двух первых име- ем 36 вариантов раскраски. Учитывая, что число раскрасок первого ше- стиугольника также можно выбрать A² способами, а также выбор шести- угольников 6 способами, имеем следующее число раскрасок:

_{A2 3!}

3 ^{· 6 · 3 · 46 =} _1! ^{· 6 · 3 · 46 = 4968.}

Лемма 5. Число 3-раскрасок графа S₄(P R) равно 113760.

Доказательство. Для определения количества способов раскраски гра- фа в x цветов можно составить хроматический полином P (G, x). Значение хроматического полинома на графе S₄ (P R) равно P (S₄ (P R), 3) = 113760.

Определение 2. Раскраску S₄(P R) в три цвета, в которой каждый ше- стиугольник графа имеет по две вершины каждого цвета, назовем регу- лярной 3-раскраской.

6

Утверждение 7. Число регулярных 3-раскрасок, в которых вершины до- минирующего множества, в каждом цикле C ⁱ , i = 1, 3 имеют один и

тот же цвет, равно 216.

6

6

Введем нумерацию шестиугольников C ⁱ в P R_j (4), 1 ≤ j ≤ 4 и нумерацию вершин в каждом из C ⁱ , 1 ≤ i ≤ 4, как показано на рис. 3.3.

6

6

Доказательство.Пусть для доминирующего множества D₁ имеем рас- пределение цветов, в котором цикл C ⁱ , i = 1, 2, 3, покрашен в цвет i. Тогда на все вершины графа передается двухцветная метка, причем в каждом цикле C ⁱ это метка {1, 2, 3}\i. Тогда на множестве вершин V (S_n (P R))\D₁

^{определим независимое множество B. Для вершин из B можно опреде-}

6

лить четыре типа покраски в каждом из циклов C ⁱ , i = 1, 2, 3. Остальные вершины графа раскрасятся однозначно.Чтобы не было противоречий в

_{вершинах множества C = V (Sn (P R))\(D1} ^S _{B), рассмотрим возможные}

6

6

_{варианты выбора цветов множества B для C} ⁱ

_{и C} ^j _{, 1 ≤ i < j ≤ 3. Тогда}

_{C i j}

^{чтобы покрасить}

₆ ^{и C}₆ ^{, 1 ≤ i < j ≤ 3, вместе, возможно 9 случаев вы-}

^{бора пар раскрасок вершин из множества B. Если взять пересечение этих}

6

случаев, получим то весь граф красится 9·2 = 18 способами. Осталось рас- смотреть C ⁴. Чтобы в цикле встречались все цвета два раза возможно по-

красить только двумя способами: так как при выборе раскраски двух неза- висимых вершин (это 4 способа), только 2 дадут однозначную правильную раскраску цикла. Учитывая что мы можем выбирать цвета в каждом из

^{3 циклов, это 3 · 2 = 6 вариантов, имеем: N}3 ^(S4 ^{(P R)) = 6 · 18 · 2 = 216.}

^{Возможные варианты раскраски представлены на рис. 3.4.}

_{1 1}

₆ ^✟✟❍❍ ₂

^C

^C

1

⁶

^{5 ❍}_❍✟^{✟ 3}

⁴

₆ ^✟✟❍❍ ₂

2

⁶

^{5 ❍}_❍✟^{✟ 3}

⁴

_{1 1}

₆ ^✟✟❍❍ ₂

^C

3

⁶

^{5 ❍}_❍✟^{✟ 3}

⁴

₆ ^✟✟❍❍ ₂

^C

4

⁶

^{5 ❍}_❍✟^{✟ 3}

⁴

Рис. 3.3. Нумерация шестиугольников в S₄ (P R)

^✟✈❍_❍✈

_✟✈ ^✟❍✈ _❍✈

_✟✈ ^✟❍✈ _❍✈

_✟✈ ^✟ _❍✈

_❍^✈_✟^✟✈

_❍✟^{✈ ✟✈}

_❍✟^{✈ ✟✈}

_❍✟^{✈ ✟✈}

^✟✈❍_❍✈

_✟✈ ^✟❍✈ _❍✈

_✟✈ ^✟❍✈ _❍✈

_✟✈ ^✟ _❍✈

_❍^✈_✟^✟✈

а)

_❍✟^{✈ ✟✈}

_❍✟^{✈ ✟✈}

б)

_❍✟^{✈ ✟✈}

_✈✟^✟✈❍_❍✈

❍^✈✟^✟✈

^✟✈❍_❍✈

❍✟^{✈ ✟✈}

_✟✈ ^✟ _❍✈

_{❍ ✟}✈

^✟✈❍_❍✈

_{❍ ✟}✈

_✈✟^✟✈❍_❍✈

^✟✈❍_❍✈

_✟✈ ^✟ _❍✈

^✟✈❍_❍✈

^❍✈ _❍^✈_✟^✟✈

в)

_❍✟^{✈ ✟✈}

_❍✟^{✈ ✟✈}

г)

_❍ ^✟✈

Рис. 3.4. Число регулярных раскрасок

(а) - 9 вариантов; б),в) - 4 варианта; г) - 1 вариант)

3.4 Граф S₅(P R) и его свойства

^{Рассмотрим граф S}_n ^{(P R), при n = 5 с числом вершин и ребер |V | =}

2

⁼

^{5! = 120, |E| = n!(n−1)}

120· 4

₂

= 240, соответственно. Этот граф регуляр-

^{ный, степень регулярности ∆ = 4. Данный граф составлен из пяти копий}

S₄(P R) и ребрами между ними. Будем обозначать копии графа S₄ (P R) как P R_i (4), i = 1, 5, причем множество вершин V (P R_i (4)) копии i имеет вид [π₁π₂π₃ π₄| i ], где π_j ∈ {1, .., 5}\i, j = 1, 4. Две вершины, имеющие r₄-ребра в S₅(P R), будем называть r₄-смежными.

3.4.1 Структурные свойства S₅ (P R)

Лемма 6. Вершины любого D_k -множества, k = 1, 4, в P R_j (4), j = 1, 5, являются r₄-смежными c вершинами другого D_n -множества, n = 1, 4, в P R_i (4), i = 1, 5, i = j.

Доказательство. Утверждение эквивалентно тому, что для любого мно- жества D_k , состоящего из шести перестановок группы S₅, находящихся на расстоянии три, после действия на них префикс-реверсалом r₄ расстояние

между вершинами из множества (D_k )r₄ = {πr₄, π ∈ D_k } останется равным трем. Элементы множества (D_k )r₄ будут иметь вид: [i | . . . j], и принад- лежать некоторому P R_j (4), j = 1, 5, j = i, в котором действуют только

префикс-реверсалы r_l , l = 1, 3. Таким образом, чтобы из некоторой пере- становки [i | i₁ i₂ i₃ i₄] получить [i | j₁ j₂ j₃ j₄], используя префикс-реверсалы r_l , l = 1, 3, нужно по крайней мере три операции, что и доказывает лемму.

Приведем в табл. 3.1 соответствие между доминирующими множества- ми P R_i (4), i = 1, 5.

Таблица 3.1. Соответствие между доминирующими множествами

	^P^R1	^P^R2	^P^R3	^P^R4	^P^R5
^P^R1		^D4 ^−^D4	^D3 ^−^D3	^D2 ^−^D2	^D1 ^−^D1
^P^R2	^D4 ^−^D4		^D3 ^−^D4	^D2 ^−^D3	^D1 ^−^D2
^P^R3	^D3 ^−^D3	^D4 ^−^D3		^D2 ^−^D4	^D1 ^−^D3
^P^R4	^D2 ^−^D2	^D3 ^−^D2	^D4 ^−^D2		^D1 ^−^D4
^P^R5	^D1 ^−^D1	^D2 ^−^D1	^D3 ^−^D1	^D4 ^−^D1

3.4.2 Хроматические свойства S₅(P R)

24

Пусть N₄(S_n (P R)) есть число способов покрасить граф S_n (P R), n = 4, 5 в четыре цвета так, что вершины любого множества D_i , i = 1, 4, в некоторой копии P R_j (4), j = 1, ^n! , имеют один и тот же цвет c ∈ {1, . . . , 4}, и цвета доминирующих множеств не совпадают: c(D_i ) = c(D_j ), j, i = 1, 4. Тогда справедливы следующие утверждения.

Лемма 7. N₄ (S₄(P R)) = 24.

Доказательство. Так, как в графе всего четыре минимальных домини- рующих множества, то число способов покрасить 4 множества в разные цвета равно 4 · 3 · 2 · 1 = 4! = 24.

Лемма 8. N₄ (S₅(P R)) = 23760.

Доказательство. Рассмотрим первую копию графа P R₁(4). Из Леммы 7 следует что, N₄(P R₁(4)) = 4!. Тогда для следующих копий, вычитая из общего числа способов ограничения из предыдущих копий, получим:

1 N₄(P R₂(4)) = 4! − 6 = 18.

2 N₄(P R₃(4)) = 4! − 6 · 2 + 2 = 14.

3 N₄(P R₄(4)) = 4! − 6 · 3 + 2 · 3 − 1 = 11.

4 N₄(P R₅(4)) = 4! − 6 · 4 + 2 · 4 − 1 · 4 + 1 = 5.

Тогда N₄(S₅(P R)) = 24 · 18 · 14 · 11 · 5 = 23760. Заметим, что таким образом можно получить подходящую 4-раскраску S₅ (P R) и 4-раскраска некото- рых копий P R_i (4) может совпадать.

Будем обозначать c(D_i ) = c, если все вершины из D_i , i = 1, 4 имеют один и тот же цвет c.

Теорема 3. χ(S₅(P R)) = 3.

Доказательство. Пусть S₅ (P R) покрашен в четыре цвета c₁ , c₂ , c₃, c₄, по Лемме 8 это всегда можно сделать. Рассмотрим одну из правильных 4- раскрасок S₅(P R), при которой c(D_i ) = i, ∀i = 1, 4, в P R₁(4), и в которой

^{4-раскраска D}_i ^{-множеств, i = 1, 4, в P R}₂^{(4) и P R}₅^{(4) совпадает. Опреде-}

^{лим её следующим образом: c(D}₁^{) = c}₄^{, c(D}₄^{) = c}₁^{, c(D}_i ^{) = c}_i ^{, i = 2, 3. То-}

^{гда в P R}₃ ^{(4) имеем c(D}_i ^{) = c}_i+1 ^{(mod 4), i = 1, 4, а в P R}₄^{(4) цвета распреде-}

^{ляются следующим образом: c(D}₁^{) =c}₂^{, c(D}₂^{) =c}₄^{, c(D}₃ ^{) =c}₃ ^{, c(D}₄^{) =c}₁^{. В}

^{целом, распределение цветов в D}_i ^{-множествах, i = 1, 4, P R}_j ^{(4), j = 1, 5 ис-}

^{ходного графа S}₅^{(P R) представлено в табл. 3.2. Эта 4-раскраска является}

правильной, поскольку учитывает соответствие между доминирующими

множествами, см. табл. 3.1.

Используя эту правильную 4-раскраску S₅(P R), покажем, как на её ос- нове получить правильную 3-раскраску S₅(P R). Рассмотрим граф P R₁(4) и осуществим в нем замену цветов следующим образом. Обозначим че- рез c˜(x) приобретенный цвет вершины x. Тогда в P R₁ (4) цвет вершин u

^{из D}1 ^{-множества останется неизменным, таким образом, c˜(u) = c(u), u ∈}

^D₁^{(P R}₁ ^{(4)), по Утверждению 6, остальные вершины будут покрашены в}

^{два цвета, так как S}₄^{(P R) всегда можно покрасить в три цвета, зная толь-}

^{ко цвета одного из доминирующих множеств. Вершины y из D}₄ ^{-множества}

^{в P R}₁^{(4) будут покрашены так, что:}

6

1 c˜(y) = c₂, если y ∈ C ².

6

2 c˜(y) = c₃, если y ∈ C ³.

6

3 c˜(y¹) = c₂ и c˜(y⁴ ) = c₃, если y¹, y⁴ ∈ C ⁴ .

Вершины v из D₂-множества в P R₁(4) получат следующие цвета:

6

1 c˜(v) = c₃ , если v ∈ C ¹.

6

2 c˜(v) = c₂ , если v ∈ C ³.

6

3 c˜(v²) = c₃ и c˜(v⁵ ) = c₂ , если v² , v⁵ ∈ C ⁴.

А вершины x из D₃-множества в P R₁ (4) получат следующие цвета:

6

1 c˜(x) = c₂, если x ∈ C ¹.

6

2 c˜(x) = c₃, если x ∈ C ².

6

3 c˜(x³) = c₂ и c˜(x⁶ ) = c₃, если x³, x⁶ ∈ C ⁴ .

Таким образом, вершины D₁-множества в P R₁(4) имеют цвет c₁, а на остальных вершинах цвета c₂ и c₃ чередуются в двух независимых цик- лах C₆ и C₁₂ .После смены цветов вершин в P R₁(4) исходная 4-раскраска вершин во всех P R_i (4), i = 2, 5, осталась также правильной. Действи- тельно, в P R₂(4) не возникло никаких противоречий в раскраске, так как по Лемме 6 вершины D₄-множества из P R₁(4), имеющие теперь цвета c₂ и c₃, являются r₄-смежными с вершинами D₄-множества из P R₂(4), цвет которых в P R₂(4) был c₁. В P R₅(4) раскраска вершин осталась правиль- ной, т.к. r₄-смежными вершинами между P R₁(4) и P R₅(4) являются по Лемме 6 вершины D₁-множеств, а цвет вершин D₁ -множества в P R₁(4) не изменился, следовательно, 4-раскраска в P R₅ (4) тоже не изменилась. Так- же, в силу Леммы 6, по которой r₄ -смежными вершинами между P R₁(4) и P R₃(4), P R₁(4) и P R₄(4), являются, соответственно, вершины D₃ - и D₂ - множеств, цвет которых c₄, следовательно, правильная раскраска сохра- няется и здесь. Таким образом, имеем 3-раскраску в P R₁ (4) и 4-раскраску

^{в P R}i ^{(4), 2 ≤ i ≤ 5.}

^{Рассмотрим P R}₅ ^{(4), в котором вершины D}₁^{-множества являются r}₄ ^-

^{смежными c вершинами D}₁ ^{-множества графа P R}₁^{(4). В P R}₅^{(4) верши-}

^{нам D}₁^{-множества присвоем один из цветов c}₂ ^{или c}₃^{. Мы всегда можем}

^{это сделать, так как все вершины D}₁^{-множества в P R}₅^{(4) являются r}₄^-

^{смежными с вершинами D}₁ ^{-множества в P R}₁^{(4), которые, в свою очередь,}

уже покрашены в цвет c₁ . Для определенности, пусть c˜(u) = c₂ для всех вершин u ∈ D₁ (P R₅(4)). Тогда вершины y из D₄-множества в P R₅(4) будут покрашены так, что:

6

1 c˜(y) = c₃, если y ∈ C ².

6

2 c˜(y) = c₁, если y ∈ C ³.

6

3 c˜(y¹) = c₃ и c˜(y⁴ ) = c₁, если y¹, y⁴ ∈ C ⁴ .

При этом вершины v из D₂ -множества в P R₅(4) получат следующие цвета:

6

1 c˜(v) = c₁ , если v ∈ C ¹.

6

2 c˜(v) = c₃ , если v ∈ C ³.

6

3 c˜(v²) = c₁ и c˜(v⁵ ) = c₃ , если v² , v⁵ ∈ C ⁴.

И вершины x из D₃-множества в P R₅ (4) получают следующие цвета:

6

1 c˜(x) = c₃, если x ∈ C ¹.

6

2 c˜(x) = c₁, если x ∈ C ².

6

3 c˜(x³) = c₃ и c˜(x⁶ ) = c₁, если x³, x⁶ ∈ C ⁴ .

Таким образом, вершины D₁-множества в P R₅(4) имеют цвет c₂ , а на остальных вершинах цвета чередуются в двух независимых циклах C₆ и C₁₂ .После того, как в P R₁ (4) и P R₅ (4) задана 3-раскраска вершин, исход- ная 4-раскраска в графе S₅(P R) не нарушается, что показывается рассуж- дениями на основе Лемм 6 и 8, как это было сделано ранее после покраски P R₁(4) в три цвета. Таким образом, в графе S₅(P R) имеется 3-раскраска P R₁(4) и P R₅(4), которая определяет распределение цветов c₁ , c₂, c₃ в

^{графах P R}i ^{(4), 2 ≤ i ≤ 4. Одновременно покрасим P R}i ^{(4), 2 ≤ i ≤ 4, и}

^{покажем, что полученный граф будет иметь 3-раскраску.}

При покраске P R₂(4) в три цвета, учитывается, что вершины D₄-мно- жества в P R₁(4) имеют цвета c₂ и c₃, а также по Лемме 6, являются r₄ - смежными с вершинами из D₄-множества в P R₂(4), следовательно, эти вершины могут иметь метки (c₁,c₂) и (c₁,c₃), причем в равных количествах. Кроме этого, вершины D₂-множества в P R₅(4), покрашенные в цвета c₁ и c₃ , являются r₄-смежными с вершинами D₁-множества в P R₂ (4), следо- вательно, эти вершины получат цвета c₁, c₂ , c₃, как и D₂ -, D₃-множества, причем в D₁-множестве распределение цветов будет равномерным. Пусть kⁱ обозначает количество i вершин цвета k, тогда в P R₂(4) в D₄-множестве

_{распределение цветов между вершинами будет выглядеть, как c3 − c3; в}

_{c2 1}

2 3

3 1 2

1

^{D1-множестве как c3 −} 2

_c2 2

^{− c}₃^{; в D2 -множестве как c}₁

^{− c}₂

^{− c}₃ ^{, а в}

1

^{D3-множестве c2 −}

^{2 − c3}

, в табл. 3.3 указаны все распределения цветов

^{в доминирующих множествах.}

В целом, в P R₂(4) цвета вершин D_i -множеств, i = 1, 4, определяются по следующим правилам. Вершины u из D₁-множества в P R₂(4) получают следующие цвета:

6

1 c˜(u¹) = c₃ и c˜(u⁴) = c₁, если u¹, u⁴ ∈ C ¹.

6

2 c˜(u) = c₁, если u ∈ C ² .

6

3 c˜(u) = c₂, если u ∈ C ³ .

Для вершин y из D₄ -множества имеем:

6

1 c˜(y) = c₂, если y ∈ C ².

6

2 c˜(y) = c₃, если y ∈ C ³.

6

3 c˜(y¹) = c₂ и c˜(y⁴ ) = c₃, если y¹, y⁴ ∈ C ⁴ .

Тогда цвета вершин v из D₂-множества определяются так, что:

6

1 c˜(v²) = c₁ и c˜(v⁵ ) = c₃ , если v² , v⁵ ∈ C ¹.

6

2 c˜(v) = c₁ , если v ∈ C ³.

6

3 c˜(v²) = c₃ и c˜(v⁵ ) = c₂ , если v² , v⁵ ∈ C ⁴.

А цвета вершин x из D₃-множества определяются так, что:

6

1 c˜(x) = c₂, если x ∈ C ¹.

6

2 c˜(x) = c₃, если x ∈ C ².

6

3 c˜(x) = c₁, если x ∈ C ⁴.

^{При покраске P R}₃^{(4) учитываются цвета r}₄ ^{-смежных вершин в P R}₁^(4),

_{P R2(4) и P R5 (4), при этом равномерное распределение цветов c}2 _{− c}2 ₋

1 2

_c2