3 Присутствует в d2 -множестве. В целом, распределение цветов в Di -

^{множествах, i = 1, 4, см. в табл. 3.3. Более того, в P R}₃^{(4) цвета вершин}

^D_i ^{-множеств, i = 1, 4, задаются по следующим правилам:}

6

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

6

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

6

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

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

6

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

6

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

6

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

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

6

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

6

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

6

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

Цвета вершин y из D₄-множества задаются так, что:

6

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

6

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

6

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

При покраске P R₄(4) в три цвета учитываются цвета r₄ -смежных вер- шин в P R_i (4), i = 1, 3, i = 5. (Распределение цветов в D_i -множествах, i = 1, 4 в P R₄(4) см. в табл. 3.3). Правила покраски определяются следу- ющим образом. Цвета вершин v из D₁-множества определяются как:

6

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

6

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

6

3 c˜(u) = c₂, если u ∈ 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₂ и c˜(x⁶ ) = c₁, если x³, x⁶ ∈ C ¹ .

6

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

6

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

Цвета вершин y из D₄-множества задаются так, что:

6

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

6

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

6

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

Таким образом, в S₅(P R) задана 3-раскраска, при которой каждый из P R_i (4), i = 1, 5, имеет правильную 3-раскраску, все r₄-смежные верши- ны имеют правильную 3-раскраску, и следовательно, 3-раскраска S₅ (P R) является правильной.

Таблица 3.2. Раскраска доминирующих множеств в S₅(P R) в четыре цвета

	^P^R1 ^(4)	^P^R2 ^(4)	^P^R3 ^(4)	^P^R4 ^(4)	^P^R5 ^(4)
^D1	^c1	^c4	^c2	^c2	^c4
^D2	^c2	^c2	^c3	^c4	^c2
^D3	^c3	^c3	^c4	^c3	^c3
^D4	^c4	^c1	^c1	^c1	^c1

Таблица 3.3. Распределение цветов в доминирующих множествах после покраски S₅(P R) в три цвета

	1		1	2	3	1	2	3	1		2		3		2
2		3	1	2	3	1	2	3		1		2		1		3
2		3	1	2	3	1	2	3	1		2		3	1		3

	^P^R1^(4)	^P^R2^(4)	^P^R3 ^(4)	^P^R4^(4)	^P^R5 ^(4)
^D1	c^6	^c^3^−^c^2^−^c^1	^c^1^−^c^4^−^c^1	^c^1^−^c^4^−^c^1	c^6
^D2	^c^3^−^c^3	^c^3^−^c^1^−^c^2	^c^2^−^c^2^−^c^2	^c^4^−^c^2	^c^3^−^c^3
^D3	^c^3^−^c^3	^c^2^−^c^2^−^c^2	^c^3^−^c^1^−^c^2	^c^1^−^c^2^−^c^3	^c^3^−^c^3
^D4	c^3^3	^3^3	^3^2^1	^2^1^3	^3^3

₂ ^{− c}₃ ^c₂ ^{− c}₃ ^c₁ ^{− c}₂ ^{− c}₃ ^c₁ ^{− c}₂ ^{− c}₃ ^c₁ ^{− c}₃

Приведем пример 3-раскраски S₅(P R). Положим c₁ = 1, c₂ = 2, c₃ = 3

и на рис. 3.5 и 3.6 покажем 4- и 3-раскраску.

₁

₁₃ ^{✈✟✟✈❍❍✈} ₈

₂₁

_✟❍^✈

¹⁷

❍✈₁₀

⁷ _❍^✈_✟^✟✈14

2

⁹ ❍✟^✈

22

_✟^✈18

₁₅

₁₉ ^{✈✟✟✈❍❍✈} ₄

₁₁

_✟❍^✈

²³

❍✈₆

^{3 ❍✈}_❍

_✟^✈20

⁵ _❍ ^✟✈24

₁

₃₁ ^{✈✟✟✈❍❍✈}₂₆

₃₉

_✟❍^✈

³⁵

16

❍✈₂₈

P R₁(4)

¹² ₂₆

₄₉ ^{✟✈✟❍✈❍✈}₄₄

₂₄

₅₃ ^{✈✟✟✈❍❍✈}₄₆

²⁵ _❍^✈_✟^✟✈32

5

27 _❍✟✈

40

_✟^✈36

^{43 ✈❍}_❍✟^✈✟✈50

30

⁴⁵ _❍^✈_✟^✟✈54

19

₃₃

₃₇ ^{✈✟✟✈❍❍✈} ₆

₂₉

_✟❍^✈

⁴¹

❍✈₄

₅₁

₂₂ ^{✟✈✟❍✈❍✈}₂₉

₄₇

₂₀ ^{✈✟✟✈❍❍✈}₂₈

³ _❍^✈_✟^✟✈38

² _❍ ^✟✈42

^{27 ✈❍}_❍✟^✈✟✈23

²⁵ _❍^✈_✟^✟✈21

³⁴ P R₅(4) ³⁰

_{39 56}

⁵² P R₂(4) ⁴⁸

_{31 50}

₄₃ ^{✈✟✟❍✈❍✈}₁₀

₄₈ ^{✟❍✈❍✈}₈

₁₆ ^{✟❍✈❍✈}₅₆

₁₄ ^{✈✟✟❍✈❍✈}₅₈

⁷ _❍✟^✈✟✈46

38

^{12 ✈❍}_❍✟^✈✟✈44

60

^{55 ✈❍}_❍✟^✈✟✈17

36

57 _❍✈✟

51

_✟^✈15

₄₅

₅₈ ^{✟✈✟❍✈❍✈}₃₇

₁₁

₅₉ ^{✟❍✈❍✈}₄₁

₁₈

_✟❍^✈

⁵⁴

❍✈₃₅

₅₉

₅₂ ^{✈✟✟✈❍}

❍✈₃₃

⁴² _❍✟^✈✟✈55

^{40 ✈❍}_❍✟^✈✟✈57

^{34 ✈❍}_❍

_✟^✈49

³² _❍^✈_✟^✟✈53

⁴⁷ P R₄(4) ⁹

¹³ P R₃ (4) ⁶⁰

Рис. 3.5. 4-раскраска S₅(P R)

(вершины имеющие одинаковые номера являются r₄ -смежными)

₁

₁₃ ^{✈✟✟✈❍❍✈} ₈

₂₁

_✟❍^✈

¹⁷

❍✈₁₀

⁷ _❍^✈_✟^✟✈14

2

⁹ ❍✟^✈

22

_✟^✈18

₁₅

₁₉ ^{✈✟✟✈❍❍✈} ₄

₁₁

_✟❍^✈

²³

❍✈₆

^{3 ❍✈}_❍

_✟^✈20

⁵ _❍ ^✟✈24

₁

₃₁ ^{✈✟✟✈❍❍✈}₂₆

₃₉

_✟❍^✈

³⁵

16

❍✈₂₈

P R₁(4)

¹² ₂₆

₄₉ ^{✟✈✟❍✈❍✈}₄₄

₂₄

₅₃ ^{✈✟✟✈❍❍✈}₄₆

²⁵ _❍^✈_✟^✟✈32

5

27 _❍✟✈

40

_✟^✈36

^{43 ✈❍}_❍✟^✈✟✈50

30

⁴⁵ _❍^✈_✟^✟✈54

19

₃₃

₃₇ ^{✈✟✟✈❍❍✈} ₆

₂₉

_✟❍^✈

⁴¹

❍✈₄

₅₁

₂₂ ^{✟✈✟❍✈❍✈}₂₉

₄₇

₂₀ ^{✈✟✟✈❍❍✈}₂₈

³ _❍^✈_✟^✟✈38

² _❍ ^✟✈42

^{27 ✈❍}_❍✟^✈✟✈23

²⁵ _❍^✈_✟^✟✈21

³⁴ P R₅(4) ³⁰

_{39 56}

⁵² P R₂(4) ⁴⁸

_{31 50}

₄₃ ^{✈✟✟❍✈❍✈}₁₀

₄₈ ^{✟❍✈❍✈}₈

₁₆ ^{✟❍✈❍✈}₅₆

₁₄ ^{✈✟✟❍✈❍✈}₅₈

⁷ _❍✟^✈✟✈46

38

^{12 ✈❍}_❍✟^✈✟✈44

60

^{55 ✈❍}_❍✟^✈✟✈17

36

57 _❍✈✟

51

_✟^✈15

₄₅

₅₈ ^{✟✈✟❍✈❍✈}₃₇

₁₁

₅₉ ^{✟❍✈❍✈}₄₁

₁₈

_✟❍^✈

⁵⁴

❍✈₃₅

₅₉

₅₂ ^{✈✟✟✈❍}

❍✈₃₃

⁴² _❍✟^✈✟✈55

^{40 ✈❍}_❍✟^✈✟✈57

^{34 ✈❍}_❍

_✟^✈49

³² _❍^✈_✟^✟✈53

⁴⁷ P R₄(4) ⁹

¹³ P R₃ (4) ⁶⁰

Рис. 3.6. 3-раскраска S₅ (P R)

(вершины, имеющие одинаковые номера, связаны r₄ -ребром)

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

[1] Ф.Харари. Теория графов. М.: Мир, 1973. 300 c.

[2] R.L.Brooks. On colouring the nodes of a network, Proc. Cambridge Phil.

Soc., 37 (1941) 194–197.

[3] H. Dweighter, E 2569 in: Elementary problems and solutions, Amer. Math.

Monthly , 82 (1) (1975) 1010.

[4] E. Konstantinova. Combinatorial problems on Caley graphs, in: Lectures on Combinatorics 1. IPM Lecture Notes Series 8, pp. 67–140.

[5] L. Heydemann. Caley graphs as interconnection networks, in: Graph symmetry: algebraic methods and applications, (G. Halun, G. Sabidussi, eds.), Kluwer, Amsterdam, 1997.

[6] M. Heydari and Sudborough. On Sorting by prefix reversals and the diameter of pancake networks, Lecture notes in computer Science, 678 (1992) 218–227.