In [3], a theorem was
proved on the existence of a colored disk passing through linked edges in a
basis simple cycle of a planar correctly colored cubic graph
H.
Based on
the proved theorem, it was shown that the four-color problem can be represented
as its consequence. The introduction of a new operation – the rotation of a
colored disk – made it possible to recolor the edges in a plane colored cubic
graph and construct a visual coloring algorithm. The presented method allows
recursively color the edges of the subsequent plane cubic graph
H
with
n
vertices in three colors based on the previous colored cubic graph with
n-2
vertices.
As for coloring there is a
relation between the maximal planar graph
G
¢
and the planar cubic
graph
Í
dual to
G
¢
. This relation is set by
the following theorem.
Theorem 1.
(
Tait
) [7]. A
bridge-free trivalent plane graph can be face-colored with 4 colors if and only
if it can be edge-colored with 3 colors.
In other words, let
Í
be a plane homogeneous cubic graph
without isthmuses; a necessary and sufficient condition for the possibility of such
coloring the faces of the graph in four colors, in which no two adjacent faces
are colored the same color, is that the chromatic class of graph
Í
be equal to three [4].
Thus, the coloring of edges
and faces of a plane cubic graph is adequate to the coloring of vertices and
edges in a maximally plane graph
G
¢
. Therefore, it is convenient to
consider only the process of coloring a plane graph.
Tait’s theorem not only
establishes a relation between the coloring of vertices of a maximally plane
graph and the coloring of edges of a cubic graph dual to it, but also indicates
the use of the fourth-order transformation of the Klein group for coloring a
graph [2]. This transformation allows connecting in a single whole the coloring
of faces of a plane cubic graph
H
in four colors and coloring of edges
in three colors.
|
+
|
0
|
1
|
2
|
3
|
|
W
|
W
|
R
|
B
|
G
|
|
R
|
R
|
W
|
G
|
B
|
|
B
|
B
|
G
|
W
|
R
|
|
G
|
G
|
B
|
R
|
W
|
|
(1)
|
Further development of the
methods of coloring edges and faces in a plane cubic graph revealed the existence
of a close relationship between the coloring and the topological drawing of a plane
graph. In this article, we consider an algebraic framework for coloring cubic
graphs.
Graph
G
= (
V
,
E
)
is generally defined by a set of vertices
V
, a set of edges
E
and
a triple predicate
Ð
in the form of adjacency
(incidence) matrix [1,6] without describing a drawing of the graph. For a
topological description of planar graph drawing we use the concept of graph
vertex rotation introduced by G. Ringel [5].
Definition 1.
Given a graph
G
, a rotation of a vertex A
is an oriented cyclic order (or a cyclic permutation) of all arcs incident with
A.
Fig
. 1.
Graph
G
and the rotation of
its vertices.
Definition 2.
A rotation of graph vertices
is the totality of the rotations of all
vertices of
G
.
We will further represent the
rotation of all vertices of a graph in the form of diagrams and denote it as
. For example, for the
graph drawing depicted in Fig. 1, the vertex rotation diagram has the following
form:
|
1:
|
2
|
3
|
4
|
|
|
2:
|
6
|
5
|
3
|
1
|
|
3:
|
2
|
5
|
4
|
1
|
|
4:
|
1
|
3
|
5
|
6
|
|
5:
|
3
|
2
|
6
|
4
|
|
6:
|
2
|
4
|
5
|
|
For convenience, the
numbers in the vertex rotation diagram, indicate the numbers of vertices. In
turn, the rotation of graph vertices induces a system of oriented simple
cycles. In order to obtain such a system, we carry out a traversal along the
edges, considering the transition from edge to edge according to the rotation
of the vertices. We should note that during rotation each oriented edge always
appears twice, the second time – in the opposite direction and in different
cycle [5].
For example, for a plane
graph
G
with rotation shown in Fig. 1, we have the following system of
induced cycles: < v
1
,v
3
,v
2
>, < v
1
,v
4
,v
3
>,
< v
2
,v
3
,v
5
>, < v
5
,v
3
,v
4
>,
< v
2
,v
5
,v
6
>, < v
6
,v
5
,v
4
>,
< v
2
,v
6
,v
4
,v
1
>. We will
represent induced cycles in the form of a cyclic tuple of vertices describing a
closed oriented path (either clockwise or counterclockwise, but always
specifying this explicitly). Induced cycles can also be represented as sets of
edges: {e
1
,e
2
,e
4
}, {e
2
,e
3
,e
7
},
{e
7
,e
8
,e
9
}, {e
4
,e
5
,e
8
},
{e
5
,e
6
,e
11
}, {e
9
,e
10
,e
11
}.
Another induced cycle {e
1
,e
3
,e
6
,e
10
}
is the rim of the graph. It is equal to the ring sum of the cycles representing
the boundaries of the graph drawing faces [5]. Thus, the rotation of graph
vertices does not only represent a diagram of the vertices rotation, but it is also
a system of simple cycles that are the boundaries of the faces (2-cells) of the
plane drawing of the graph. On the other hand, such cycles form the basis of
the subspace of cycles. Henceforth, we shall denote them as the
basis cycles
.
Induced oriented cycles
can also be written as a closed sequence of oriented edges (arcs), e.g.: < v
1
,v
3
,v
2
>
= (v
1
,v
3
) + (v
3
,v
2
) + (v
2
,v
1
).
Definition 3.
A topological drawing of a
plane graph is a graph with a given rotation of vertices.
The rotation of vertices
induces simple cycles
that form a basis in the subspace of graph cycles
C
. To establish the
coloring of a plane cubic graph
H
, it is necessary to color its edges (Fig.
2).
Fig
. 2.
Edge coloring in the
plane cubic graph
Í
1
.
If
the cubic graph
H
has a chromatic class of three, then its edges must be
colored in three colors. The coloring assumes the presence of three edges of
different colors for each vertex of graph
H
. We call a cubic graph with
chromatic class equal to three a colored plane cubic graph
H
. E.g.,
the cubic graph shown in Fig. 2 is essentially a colored cubic graph
H
. Here,
white color is designated with letter W or number 0, and on the graph drawings
the edges of this color are represented with a dash-and-dot line. Red color is
designated with letter R, or number 1, and on the graph drawings the edges
of this color are represented with a solid line. Blue color is designated with
letter B and number 2, and the edges of this color are represented with a
dotted line on the graph drawings. In turn, green color is designated with
letter G, or number 3, and edges of this color are represented with dashed
line. According to Tait’s theorem, coloring of edges induces coloring of faces
of a plane cubic graph
H
, and coloring of faces, in turn, induces
coloring of edges.
Fig.
3. Designation of colored lines.
Definition 4.
In a colored plane cubic
graph, a colored disk is a closed path of even length with edges of only two
colors.
Thus, a red colored disk
consists only of blue and green edges. A green colored disk consists only of
blue and red edges. A blue colored disk consists only of green and red edges. The
process of constructing a color disk can be seen as a sequence of connecting
colored edges of two colors:
|
D = < v
1
,e
1
,v
2
,e
2
,…,v
p-1
,e
p-1
v
p
,e
p
,v
1
>
|
(2)
|
where p – is the length of a colored disk.
Let us denote a colored
disk with the Latin letter D and the name of a color. For example, the red colored
disk DR of the plane cubic graph
Í
1
in Fig. 2 can be represented as a tuple:
DR = < v
1
,e
2
,v
5
,e
10
,v
10
,e
12
,v
6
,e
11
,v
7
,e
13
,v
8
,e
14
,v
9
,e
9
,v
4
,e
6
,v
3
,e
4
,v
2
,e
1,
v
1
>;
or taking into account the
color of the edge indicated in square brackets:
DR = < e
2
[2],e
10
[3],e
12
[2],e
11
[3],e
13
[2],e
14
[3],e
9
[2],e
6
[3],e
4
[2],e
1
[3]>.
A colored disk in a plane
cubic graph
H
can be represented as a ring addition of cycles [6]. Moreover,
ring addition is carried out in the adjacency order of two cycles having a
common edge of the disk’s color. For example, the colored induced cycles of the
graph
Í
1
(which is shown in Fig. 2).
ñ
1
= {e
2
[2],e
3
[1],e
10
[3],e
12
[2]}; ñ
2
= {e
1
[3],e
3
[1],e
5
[1],e
11
[3]};
ñ
3
= {e
4
[2],e
5
[1],e
7
[1],e
13
[2]}; ñ
4
= {e
6
[3],e
7
[1],e
9
[2],e
14
[3]};
ñ
5
= {e
8
[1],e
9
[2],e
10
[3],e
15
[1]}; ñ
6
= {e
11
[3],e
12
[2],e
13
[2],e
14
[3],e
15
[1]};
ñ
0
= {e
1
[3],e
2
[2],e
4
[2],e
6
[3],e
8
[1]}.
form the following colored 2-factors:
R
c
= ñ
1
Å
ñ
2
Å
ñ
3
Å
ñ
4
= {e
2
[2],e
3
[1],e
10
[3],e
12
[2]}
Å
Å
{e
1
[3],e
3
[1],e
5
[1],e
11
[3]}
Å
{e
4
[2],e
5
[1],e
7
[1],e
13
[2]}
Å
Å
{e
6
[3],e
7
[1],e
9
[2],e
14
[3]}
=
= {e
2
[2],e
10
[3],e
12
[2],e
1
[3],e
5
[1],e
11
[3]}
Å
{e
4
[2],e
5
[1],e
7
[1],e
13
[2]}
Å
Å
{e
6
[3],e
7
[1],e
9
[2],e
14
[3]}
=
= {e
2
[2],e
10
[3],e
12
[2],e
1
[3],e
11
[3],e
4
[2],e
7
[1],e
13
[2]}
Å
Å
{e
6
[3],e
7
[1],e
9
[2],e
14
[3]}
=
= {e
2
[2],e
10
[3],e
12
[2],e
1
[3],e
11
[3],e
4
[2],e
13
[2],e
6
[3],e
9
[2],e
14
[3]}
=
= < e
2
[2],e
10
[3],e
12
[2],e
11
[3],e
13
[2],e
14
[3],e
9
[2],e
6
[3],e
4
[2],e
1
[3]>;
B
c
= (ñ
4
Å
ñ
5
)
Å
(ñ
2
)
= ({e
6
[3],e
7
[1],e
9
[2],e
14
[3]}
Å
Å
{e
8
[1],e
9
[2],e
10
[3],e
15
[1]})
Å
Å
({e
1
[3],e
3
[1],e
5
[1],e
11
[3]})
= ({e
6
[3],e
7
[1],e
14
[3],e
8
[1],e
10
[3],e
15
[1]})
Å
Å
({e
1
[3],e
3
[1],e
5
[1],e
11
[3]})
= (< e
6
[3],e
7
[1],e
14
[3],e
15
[1],e
10
[3],e
8
[1]>),
(< e
1
[3],e
5
[1],e
11
[3],e
3
[1]>);
G
c
= (ñ
1
Å
ñ
5
)
Å
(ñ
3
)
= ({e
2
[2],e
3
[1],e
10
[3],e
12
[2]}
Å
Å
{e
8
[1],e
9
[2],e
10
[3],e
15
[1]})
Å
Å
({e
4
[2],e
5
[1],e
7
[1],e
13
[2]})
= ({e
2
[2],e
3
[1],e
12
[2],e
8
[1],e
9
[2],e
15
[1]})
Å
Å
({e
4
[2],e
5
[1],e
7
[1],e
13
[2]})
= (< e
2
[2],e
3
[1],e
12
[2],e
15
[1],e
9
[2],e
8
[1]>),
(< e
13
[2],e
5
[1],e
4
[2],e
7
[1]>).
Since all edges are
involved in the coloring of a plane graph twice (according to MacLane’s
theorem), then it follows from the construction:
Corollary 1.
The ring sum (addition
modulo 2) of all the edges included in the colored disks is an empty set.
|
|
(3)
|
A special case is
represented by
white cycles
that are not included in expression (2), where
the edges can be colored in three colors. For our example:
W
c
= c
6
Å
c
0
= ({e
11
[3],e
12
[2],e
13
[2],e
14
[3],e
15
[1]})
Å
({e
1
[3],e
2
[2],e
4
[2],e
6
[3],e
8
[1]}).
|
|
|
Fig. 4.
The drawing of a colored plane cubic
graph
Í
2
.
|
While the formation of
color disks as a closed path of edges is carried out unambiguously, the
formation of color disks by cycles has its own specific features. For illustration,
let’s consider the following drawing of a colored graph
Í
2
(
Fig. 4)
. For a
given cubic graph
Í
2
, we select the following basis
cycles:
c
1
= {e
1
[3],e
2
[1],e
5
[2],e
17
[3]},
c
2
= {e
4
[1],e
5
[2],e
6
[3],e
8
[1],e
11
[3],e
16
[1]},
c
3
= {e
10
[3],e
11
[2],e
12
[1],e
14
[3]},
c
4
= {e
14
[3],e
15
[2],e
16
[1],e
17
[3]},
c
5
= {e
2
[1],e
3
[2],e
12
[1],e
13
[2],e
15
[2],e
19
[3],e
28
[1]},
c
6
= {e
8
[1],e
9
[2],e
10
[3],e
13
[2],e
21
[1],e
23
[3],e
25
[1],e
26
[3]},
c
7
= {e
6
[3],e
7
[2],e
9
[2],e
20
[3]},
c
8
= {e
1
[3],e
3
[2],e
4
[1],e
7
[2],e
18
[1]},
c
9
= {e
22
[2],e
23
[3],e
24
[2],e
30
[3],e
32
[1]},
c
10
= {e
24
[2],e
25
[1],e
27
[2],e
33
[1]},
c
11
= {e
26
[3],e
27
[2],e
28
[1],e
29
[2],e
34
[3],e
35
[1]},
c
12
= {e
30
[3],e
31
[2],e
33
[1],e
34
[3]},
c
13
= {e
31
[2],e
32
[1],e
35
[1],e
36
[3]}.
Let’s form the rim of the
graph: c
0
= {e
18
[1],e
19
[3],e
20
[3],e
21
[1],e
22
[2],e
29
[2],e
36
[3]}.
Next, we consider the case
of the formation of a colored disk DB consisting of the following cycles:
DB = c
4
Å
c
5
Å
c
6
Å
c
7
Å
c
8
= {e
14
[3],e
15
[2],e
16
[1],e
17
[3]}
Å
Å
{e
2
[1],e
3
[2],e
12
[1],e
13
[2],e
15
[2],e
19
[3],e
28
[1]}
Å
Å
{e
8
[1],e
9
[2],e
10
[3],e
13
[2],e
21
[1],e
23
[3],e
25
[1],e
26
[3]}
Å
Å
{e
6
[3],e
7
[2],e
9
[2],e
20
[3]}
Å
{e
1
[3],e
3
[2],e
4
[1],e
7
[2],e
18
[1]}
=
= {e
14
,e
16
,e
17
,e
2
,e
12
,e
8
,e
10
,e
6
,e
1
,e
4
,e
19
,e
28
,e
21
,e
23
,e
25
,c
26
,e
20
,e
18
}
=
=< e
14
[3],e
16
[1],e
17
[3],e
2
[1],e
1
[3],e
4
[1],e
6
[3],e
8
[1],e
10
[3],e
12
[1]>
Å
< e
19
[3],e
28
[1],e
26
[3],e
25
[1],e
23
[3],e
21
[1],e
20
[3],e
18
[1]>.
As one can see, this set
of cycles forms two unicolored disks. For the unambiguous formation of a color
disk, we need to add cycles
ñ
1
,
ñ
2
,
ñ
3
, which in turn also unambiguously form a colored disk.
For the graph presented in
Fig. 6, the colored disks before rotation are as follows:
DB
1
=
ñ
1
Å
ñ
2
Å
ñ
3
= < e
14
[3],e
16
[1],e
17
[3],e
2
[1],e
1
[3],e
4
[1],e
6
[3],
e
8
[1],e
10
[3],e
12
[1]>;
DB
2
= c
4
Å
c
5
Å
c
6
Å
c
7
Å
c
8
Å
ñ
1
Å
ñ
2
Å
ñ
3
=
= < e
19
[3],e
28
[1],e
26
[3],e
25
[1],e
23
[3],e
21
[1],e
20
[3],e
18
[1]
>
.
DB
3
= c
12
Å
c
13
= < e
30
[3],e
32
[1],e
36
[3],e
35
[1],e
34
[3],e
33
[1]>;
Thus, the concept of
embeddability
of colored disks emerges. Considering the cycles of the graph
Í
2
, we can state that the cycles of the
colored disk DB
1
are
embedded
into the colored disk DB
2
.
Let’s construct all the
colored disks of the cubic graph Í
2
(Fig. 4).
DR
1
= c
1
Å
c
5
Å
c
3
Å
c
11
Å
c
13
Å
c
9
=
= < e
19
[3],e
29
[2],e
36
[3],e
22
[2],e
23
[3],e
24
[2],e
30
[3],e
31
[2],e
34
[3],e
27
[2],
e
26
[3],e
13
[2],e
10
[3],
e
11
[2],e
14
[3],e
15
[2],e
17
[3],e
5
[2],e
1
[3],e
3
[2]>;
DR
2
= c
7
= < e
7
[2],e
20
[3],e
9
[2],e
6
[3]>;
DG
1
= ñ
10
=
< e
24
[2],e
33
[1],e
27
[2],e
25
[1]>;
DG
2
= c
1
Å
c
3
Å
c
4
Å
c
6
Å
c
8
Å
ñ
9
Å
ñ
10
Å
ñ
11
Å
ñ
12
=
= < e
18
[1],e
3
[2],e
2
[1],e
15
[2],e
12
[1],e
13
[2],e
28
[1],e
29
[2],e
35
[1],e
31
[2],e
32
[1],
e
22
[2],e
21
[1],
e
9
[2],e
8
[1],e
11
[2],e
16
[1],e
5
[2],e
4
[1],e
7
[2]>;
Notice that the disk DG
2
is embeddable into the disk DG
1
.
|
|
|
Fig.
5.
Red
2-
factor
before rotation
.
|
|
|
|
Fig
.
6.
Blue
2-
factor
before rotation
.
|
W
c
= c
0
= < e
18
[1],e
19
[3],e
20
[3],e
21
[1],e
22
[2],e
29
[2],e
36
[3]>;
Colored 2-factors are
formed as a ring sum of the corresponding colored disks. For instance, for the graph
Í
2
, the red disks are shown
in Fig. 5.
R
ñ
=
D
R
1
Å
D
R
2
= (c
1
Å
c
5
Å
c
3
Å
c
11
Å
c
13
Å
c
9
)
Å
(c
7
) =
=
< e
19
[3],e
29
[2],e
36
[3],e
22
[2],e
23
[3],e
24
[2],e
30
[3],e
31
[2],e
34
[3],e
27
[2],
e
26
[3],e
13
[2],e
10
[3],e
11
[2],
e
14
[3],e
15
[2],e
17
[3],e
5
[2],e
1
[3],e
3
[2]>
Å
Å
< e
7
[2],e
20
[3],e
9
[2],e
6
[3]>;
|
|
|
Fig. 7. Green 2-factor before rotation.
|
|
|
|
Fig. 8. Red 2-factor after rotation.
|
The blue disks are shown
in Fig. 6.
B
ñ
=
DB
1
Å
DB
2
Å
DB
3
=
(ñ
1
Å
ñ
2
Å
ñ
3
)
Å
(c
4
Å
c
5
Å
c
6
Å
c
7
Å
c
8
Å
ñ
1
Å
ñ
2
Å
Å
ñ
3
)
Å
(c
12
Å
c
13
) = (c
4
Å
c
5
Å
c
6
Å
c
7
Å
c
8
)
Å
(c
12
Å
c
13
) =
= < e
14
[3],e
16
[1],e
17
[3],e
2
[1],e
1
[3],e
4
[1],e
6
[3],e
8
[1],e
10
[3],e
12
[1]>
Å
Å
< e
18
[1],e
20
[3],e
21
[1],e
23
[3],e
25
[1],e
26
[3],e
28
[1],e
19
[3]>
Å
Å
< e
30
[3],e
32
[1],e
36
[3],e
35
[1],e
34
[3],e
33
[1]>;
The green disks are shown
in Fig
. 7.
G
ñ
=
DG
1
Å
DG
2
= (c
8
Å
c
1
Å
c
4
Å
c
3
Å
c
6
Å
c
11
Å
c
12
Å
c
9
Å
c
10
)
Å
(c
10
) =
= c
8
Å
c
1
Å
c
4
Å
c
3
Å
c
6
Å
c
11
Å
c
12
Å
c
9
=
= < e
2
[1],e
15
[2],e
12
[1],e
13
[2],e
28
[1],e
29
[2],e
35
[1],e
31
[2],e
32
[1],e
22
[2],e
21
[1],
e
9
[2],e
8
[1],e
11
[2],
e
16
[1],e
5
[2],e
4
[1],e
7
[2],e
18
[1],e
3
[2]>
Å
< e
24
[2],e
33
[1],
e
27
[2],e
25
[1]>.
The ring sum of all colored
disks of the same color forms a 2-factor of the same color. For example, in Fig.
5-7 the following colored 2-factors are shown:
;
;
From the construction
follows
:
Corollary
2.
The ring sum (adding
modulo 2) of all cycles involved in the formation of colored 2-factors is an
empty set:
The following expression
establishes a relation between the colored 2-factors and the basis cycles of a
plane cubic graph:
|
|
(5)
|
Corollary
3.
The doubled sum of the basis cycles
of the topological drawing and the rim is equal to the ring sum of the cycles
of the colored 2-factors plus the doubled sum of the white cycles.
By
rotation
of a
colored Hamiltonian disk, we mean a change in the sequence of coloring of the
edges of a given disk. Disk rotation changes other colored disks.
Consider the rotation of
the colored disk DR
2
. During rotation, only the colors of the edges e
6
,e
7
,e
9
,e
20
belonging to the colored disk DR
2
change. The colors of other edges
do not change. To define new sequences in colored disks, we attach the cycles
belonging to the disk DR
2
to other colored 2-factors.
R
ñ
= DR
1
Å
DR
2
= (c
1
Å
c
5
Å
c
3
Å
c
11
Å
c
13
Å
c
9
)
Å
(c
7
);
B
ñ
=
DB
1
Å
DB
2
Å
DB
3
= (
c
4
Å
c
5
Å
c
6
Å
c
7
Å
c
8
)
Å
(
c
12
Å
c
13
)
Å
(ñ
7
);
G
ñ
=
DG
1
Å
DG
2
= (
c
8
Å
c
1
Å
c
4
Å
c
3
Å
c
6
Å
c
11
Å
c
12
Å
c
9
)
Å
(ñ
7
);
As a result, we obtain the
coloring of red colored disks (Fig. 8):
R
ñ
= (
c
1
Å
c
5
Å
c
3
Å
c
11
Å
c
13
Å
c
9
)
Å
(
c
7
) =
= <
e
19
[3],
e
29
[2],
e
36
[3],
e
22
[2],
e
23
[3],
e
24
[2],
e
30
[3],
e
31
[2],
e
34
[3],
e
27
[2],
e
26
[3],
e
13
[2],
e
10
[3],
e
11
[2],
e
14
[3],e
15
[2],e
17
[3],e
5
[2],e
1
[3],e
3
[2]>
Å
Å
< e
7
[3],e
20
[2],e
9
[3],e
6
[2]>;
blue colored disks
(
Fig
. 9):
B
ñ
= (
c
4
Å
c
5
Å
c
6
Å
c
7
Å
c
8
)
Å
(
c
12
Å
c
13
)
Å
(ñ
7
) =
=
{
e
14
[3]
,
e
15
[2]
,
e
16
[1]
,
e
17
[3]
}
Å
{
e
2
[1]
,
e
3
[2]
,
e
12
[1]
,
e
13
[2]
,
e
15
[2]
,
e
19
[3]
,
e
28
[1]
}
Å
{
e
8
[1]
,
e
9
[3]
,
e
10
[3]
,
e
13
[2]
,
e
21
[1]
,
e
23
[3]
,
e
25
[1]
,
e
26
[3]
}
Å
{
e
6
[2]
,
e
7
[3]
,
e
9
[3]
,
e
20
[2]
}
Å
{
e
1
[3],
e
3
[2],
e
4
[1],
e
7
[3],
e
18
[1]}
Å
{
e
30
[3],
e
31
[2],
e
33
[1],
e
34
[3]}
Å
{
e
31
[2],
e
32
[1],
e
35
[1],
e
36
[3]}
Å
{
e
6
[2],
e
7
[3],
e
9
[3],
e
20
[2]} =
= {
e
14
[3],
e
16
[1],
e
17
[3],
e
2
[1],
e
12
[1],
e
19
[3],
e
28
[1],
e
8
[1],
e
10
[3],
e
21
[1],
e
23
[3],
e
25
[1],
e
26
[3],
e
1
[3],
e
4
[1],
e
7
[3],
e
18
[1],
e
30
[3],
e
33
[1],
e
34
[3],
e
32
[1],
e
35
[1],
e
36
[3]} =
= <
e
14
[3],
e
16
[1],
e
17
[3],
e
2
[1],
e
1
[3],
e
4
[1],
e
7
[3],
e
18
[1],
e
19
[3],
e
28
[1],
e
26
[3],
e
25
[1],
e
23
[3],
e
21
[1],
e
9
[3],
e
8
[1],
e
10
[3],
e
12
[1]>
Å
Å
<
e
30
[3],
e
32
[1],
e
36
[3],
e
35
[1],
e
34
[3],
e
33
[1]>;
green colored disks
(
Fig
. 10):
G
ñ
= (
c
8
Å
c
1
Å
c
4
Å
c
3
Å
c
6
Å
c
11
Å
c
12
Å
c
9
)
Å
(ñ
7
) = {
e
1
[3],
e
3
[2],
e
4
[1],
e
7
[3],
e
18
[1]}
Å
{
e
1
[3],
e
2
[1],
e
5
[2],
e
17
[3]}
Å
{
e
14
[3],
e
15
[2],
e
16
[1],
e
17
[3]}
Å
Å
{
e
10
[3],
e
11
[2],
e
12
[1],
e
14
[3]}
Å
Å
{
e
8
[1],
e
9
[3],
e
10
[3],
e
13
[2],
e
21
[1],
e
23
[3],
e
25
[1],
e
26
[3]}
Å
Å
{
e
26
[3],
e
27
[2],
e
28
[1],
e
29
[2],
e
34
[3],
e
35
[1]}
Å
Å
{
e
30
[3],
e
31
[2],
e
33
[1],
e
34
[3]}
Å
{
e
22
[2],
e
23
[3],
e
24
[2],
e
30
[3],
e
32
[1]}
Å
Å
{
e
6
[2],
e
7
[3],
e
9
[3],
e
20
[2]} =
{
e
15
[2],
e
16
[1],
e
11
[2],
e
12
[1],
e
8
[1],
e
13
[2],
e
21
[1],
e
25
[1],
e
27
[2],
e
28
[1],
e
29
[2],
e
35
[1],
e
31
[2],
e
33
[1],
e
22
[2],
e
24
[2],
e
32
[1],
e
6
[2],
e
18
[1],
e
3
[2],
e
4
[1],
e
2
[1],
e
5
[2],
e
20
[2]} =
= <
e
15
[2],
e
12
[1],
e
13
[2],
e
28
[1],
e
29
[2],
e
35
[1],
e
31
[2],
e
32
[1],
e
22
[2],
e
21
[1],
e
20
[2],
e
18
[1],
e
3
[2],
e
2
[1]>
Å
<
e
5
[2],
e
4
[1],
e
6
[2],
e
8
[1],
e
11
[2],
e
16
[1]>
Å
Å
<
e
24
[2],
e
25
[1],
e
27
[2],
e
33
[1]>.
Next, we form the rim of
the graph
,
c
0
= {
e
18
[1]
,
e
19
[3]
,
e
20
[3]
,
e
21
[1]
,
e
22
[2]
,
e
29
[2]
,
e
36
[3]
}.
|
|
|
Fig
. 9.
Blue
2-
factor
after rotation
.
|
|
|
|
Fig
.
10.
Green
2-
factor
after
rotation
.
|
A rule for determining the
composition of disks after rotation.
To determine the composition of
colored disks after rotating a colored disk Y, it is necessary to recolor its
edges and add cycles of colored disk Y to other colored 2-factors; then carry
out the edge construction in accordance to (2).
Of interest are colored
cubic graphs in which white colored disks have an even length and their total
length is 2m/3.
For the colored cubic
graph
Í
3
(Fig. 11), we select the
following basis cycles:
c
1
= {
e
2
[2]
,
e
3
[1]
,
e
8
[1]
,
e
10
[2]
}
; c
2
= {
e
1
[3]
,
e
2
[2]
,
e
4
[1]
,
e
6
[3]
}
;
c
3
= {
e
9
[3]
,
e
10
[2]
,
e
11
[1]
,
e
13
[3]
}
;
c
4
= {
e
4
[1]
,
e
5
[2]
,
e
7
[2]
,
e
18
[1]
}
;
c
5
=
{
e
11
[1]
,
e
12
[2]
,
e
14
[2]
,
e
23
[1]
}
;
c
6
= {
e
6
[3]
,
e
7
[2]
,
e
8
[1]
,
e
9
[3]
,
e
12
[2]
,
e
15
[3]
,
e
17
[1]
,
e
24
[3]
}
;
c
7
= {
e
16
[2]
,
e
17
[1]
,
e
20
[1]
,
e
22
[2]
}
;
c
8
= {
e
15
[3],
e
16
[2],
e
18
[1],
e
19
[3]};
c
9
= {
e
21
[3],
e
22
[2],
e
23
[1],
e
24
[3]}.
|
|
|
|
Fig.
11. Coloring of the cubic graph
Í
3
.
|
Fig
. 12.
Recoloring of the cubic graph
Í
3
.
|
Next, form the
rim, c
0
=
{
e
1
[3]
,
e
3
[1]
,
e
5
[2]
,
e
13
[3]
,
e
14
[2]
,
e
19
[3]
,
e
20
[1]
,
e
21
[3]
}
.
R
ñ
=
DR
1
Å
DR
2
= (
c
3
Å
c
5
Å
c
9
)
Å
(
c
2
Å
c
4
Å
c
8
) =
= ({e
9
[3],
e
10
[2],
e
11
[1],
e
13
[3]}
Å
Å
{
e
11
[1],
e
12
[2],
e
14
[2],
e
23
[1]}
Å
{
e
21
[3],
e
22
[2],
e
23
[1],
e
24
[3]})
Å
Å
({
e
1
[3],
e
2
[2],
e
4
[1],
e
6
[3]}
Å
Å
{
e
4
[1],
e
5
[2],
e
7
[2],
e
18
[1]}
Å
{
e
15
[3],
e
16
[2],
e
18
[1],
e
19
[3]}) =
= <
e
9
[3],
e
10
[2],
e
13
[3],
e
14
[2],
e
21
[3],
e
22
[2],
e
24
[3],
e
12
[2]>
Å
Å
<
e
1
[3],
e
2
[2],
e
6
[3],
e
7
[2],
e
15
[3],
e
16
[2],
e
19
[3],
e
5
[2]>;
B
ñ
=
DB
1
Å
DB
2
= (
c
1
Å
c
2
Å
c
3
)
Å
(
c
7
Å
c
8
Å
c
9
) =
= ({e
2
[2],
e
3
[1],
e
8
[1],
e
10
[2]}
Å
Å
{
e
1
[3],
e
2
[2],
e
4
[1],
e
6
[3]}
Å
{
e
9
[3],
e
10
[2],
e
11
[1],
e
13
[3]})
Å
Å
({
e
16
[2],
e
17
[1],
e
20
[1],
e
22
[2]}
Å
Å
{
e
15
[3],
e
16
[2],
e
18
[1],
e
19
[3]}
Å
{
e
21
[3],
e
22
[2],
e
23
[1],
e
24
[3]}) =
= <
e
3
[1],
e
1
[3],
e
4
[1],
e
6
[3],
e
8
[1],
e
9
[3],
e
11
[1],
e
13
[3]>
Å
Å
<
e
17
[1],
e
15
[3],
e
18
[1],
e
19
[3],
e
20
[1],
e
21
[3],
e
23
[1],
e
24
[3]>;
G
ñ
=
DG
1
Å
DG
2
Å
DG
3
Å
DG
4
= (
c
1
)
Å
(
c
4
)
Å
(
c
5
)
Å
(
c
7
) =
= < e
2
[2],
e
3
[1],
e
8
[1],
e
10
[2]>
Å
Å
<
e
4
[1],
e
5
[2],
e
7
[2],
e
18
[1]>
Å
<
e
11
[1],
e
12
[2],
e
14
[2],
e
23
[1]>
Å
Å
<
e
16
[2],
e
17
[1],
e
20
[1],
e
22
[2]>.
W
c
=
c
6
Å
c
0
= {
e
6
[3],
e
7
[2],
e
8
[1],
e
9
[3],
e
12
[2],
e
15
[3],
e
17
[1],
e
24
[3]}
Å
Å
{
e
1
[3]
,
e
3
[1]
,
e
5
[2]
,
e
13
[3]
,
e
14
[2]
,
e
19
[3]
,
e
20
[1]
,
e
21
[3]
}
.
Further we carry out the
recoloring of edges, taking colored disks instead of white ones as a basis (Fig.
12).
c
1
= {
e
2
[1]
,
e
3
[2]
,
e
8
[2]
,
e
10
[1]
},
c
2
= {
e
1
[3]
,
e
2
[1]
,
e
4
[1]
,
e
6
[3]
},
c
3
= {
e
9
[3]
,
e
10
[1]
,
e
11
[1]
,
e
13
[3]
},
c
4
= {
e
4
[1]
,
e
5
[2]
,
e
7
[2]
,
e
18
[1]
},
c
5
=
{
e
11
[1]
,
e
12
[2]
,
e
14
[2]
,
e
23
[1]
},
c
6
= {
e
6
[3]
,
e
7
[2]
,
e
8
[2]
,
e
9
[3]
,
e
12
[2]
,
e
15
[3]
,
e
17
[2]
,
e
24
[3]
},
c
7
= {
e
16
[1]
,
e
17
[2]
,
e
20
[2]
,
e
22
[1]
},
c
8
= {
e
15
[3],
e
16
[1],
e
18
[1],
e
19
[3]},
c
9
= {
e
21
[3],
e
22
[1],
e
23
[1],
e
24
[3]}.
And determine the rim as c
0
= {e
1
[3],e
3
[2],e
5
[2],e
13
[3],e
14
[2],e
19
[3],e
20
[2],e
21
[3]}.
R
ñ
= DR
1
Å
DR
2
=
=
(c
6
)
Å
(c
0
) = (c
6
)
Å
(c
1
Å
c
2
Å
c
3
Å
c
4
Å
c
5
Å
c
6
Å
c
7
Å
c
8
Å
c
9
) =
= < e
6
[3],e
7
[2],e
15
[3],e
17
[2],e
24
[3],e
12
[2],e
9
[3],e
8
[2]>
Å
Å
< e
1
[3],e
3
[2],e
13
[3],e
14
[2],e
21
[3],e
20
[2],e
19
[3],e
5
[2]>;
B
ñ
=
DB
1
Å
DB
2
Å
DB
3
Å
DB
4
= (c
2
)
Å
(c
3
)
Å
(c
8
)
Å
(c
9
) =
= < e
1
[3],e
2
[1],e
6
[3],e
4
[1]>
Å
Å
< e
9
[3],e
10
[1],e
13
[3],e
11
[1]>
Å
< e
15
[3],e
16
[1],e
19
[3],e
18
[1]>
Å
Å
< e
21
[3],e
22
[1],e
24
[3],e
23
[1]>;
G
ô
=
DG
1
Å
DG
2
Å
DG
3
Å
DG
4
= (c
1
)
Å
(c
4
)
Å
(c
5
)
Å
(c
7
) =
= < e
2
[1],e
3
[2],e
10
[1],e
8
[2]>
Å
Å
< e
4
[1],e
5
[2],e
18
[1],e
7
[2]>
Å
< e
11
[1],e
12
[2],e
23
[1],e
14
[2]>
Å
= < e
16
[1],e
17
[2],e
22
[1],e
20
[2]>.
An important case is the
coloring of cycles in non-planar cubic graphs (Fig. 13).
First, we select basis
cycles in the graph:
c
1
= {
e
1
,
e
2
,
e
4
,
e
6
};
c
2
= {
e
9
,
e
10
,
e
11
,
e
12
};
c
3
= {
e
2
,
e
3
,
e
8
,
e
11
};
c
4
= {
e
4
,
e
5
,
e
7
,
e
10
};
c
5
= {
e
6
,
e
7
,
e
8
,
e
9
,
e
10
};
c
0
= {
e
1
,
e
3
,
e
5
,
e
10
,
e
12
}.
Let's represent colored
disks for the given edge coloring in the following form:
DR
1
= (
e
1
,
G
)
Å
(
e
5
,
B
)
Å
(
e
9
,
G
)
Å
(
e
8
,
B
)
Å
(
e
6
,
G
)
Å
(
e
7
,
B
)
Å
Å
(
e
12
,
G
)
Å
(
e
3
,
B
) =
ñ
1
Å
ñ
2
Å
ñ
3
Å
ñ
4
;
DB
1
= (e
1
,G)
(e
4
,R)
Å
(e
6
,G)
Å
(e
2
,R) =
ñ
1
;
DB
2
= (e
9
,G)
(e
10
,R)
Å
(e
13
,G)
Å
(e
11
,R) =
ñ
2
;
DG
1
= (e
2
,R)
(e
3
,B)
Å
(e
11
,R)
Å
(e
3
,B) =
ñ
3
;
DG
2
= (e
4
,R)
(e
7
,B)
Å
(e
10
,R)
Å
(e
5
,B) =
ñ
4
.
Fig
. 13.
Colored cubic
non-planar graph
H
3
.
The colored 2-factors of the
colored cubic non-planar graph
H
3
are:
R
c
= DR
1
;
B
c
= DB
1
DB
2
;
G
c
=
DG
1
Å
DG
2
;
Thus, we can determine the
colors of the basis cycles as follows:
c
1
(R
c
B
c
)
G; c
2
(R
c
B
c
)
G;
c
3
(R
c
G
c
)
B; c
4
(R
c
G
c
)
B;
c
5
W
;
c
0
W
.
Consider the edge coloring:
e
1
(c
1
c
0
)
G + W = G; e
2
(c
1
c
3
)
G + B = R;
e
3
(c
3
c
0
)
B + W = B; e
4
(c
1
c
4
)
G + B = R;
e
5
(c
4
c
0
)
B + W = B; e
6
(c
1
c
5
)
G + W = G;
e
7
(c
4
c
5
)
B + W = B; e
8
(c
3
c
5
)
B + W = B;
e
9
(c
2
c
5
)
G + W = G;
e
10
(c
2
c
4
c
5
c
0
)
G + W + W + B = R;
e
11
(c
2
c
3
)
G + B = R; e
12
(c
2
c
0
)
G + W = G.
Next, consider the
following non-planar graph
Í
4
(Fig. 14). Let’s single out the following basis cycles in
this graph:
c
1
= {
e
1
,
e
2
,
e
5
,
e
12
,
e
15
};
c
2
= {
e
10
,
e
11
,
e
12
,
e
16
};
c
3
= {
e
1
,
e
3
,
e
4
,
e
7
,
e
13
};
c
4
= {
e
4
,
e
5
,
e
6
,
e
9
,
e
17
};
c
5
= {
e
6
,
e
7
,
e
8
,
e
11
,
e
18
};
c
6
= {
e
8
,
e
9
,
e
10
,
e
12
,
e
15
,
e
17
};
c
7
= {
e
13
,
e
14
,
e
15
,
e
16
,
e
17
,
e
18
};
c
0
= {
e
2
,
e
3
,
e
12
,
e
14
,
e
15
,
e
17
}.
Fig. 14. Colored non-planar graph
Í
4
.
The colored disks for this
edge coloring are as follows:
DR
1
= (
e
2
,
G
)
Å
(
e
12
,
B
)
Å
(
e
16
,
G
)
Å
(
e
11
,
B
)
Å
(
e
8
,
G
)
Å
(
e
9
,
B
)
Å
Å
(
e
17
,
G
)
Å
(
e
5
,
B
)
Å
(
e
4
,
G
)
Å
(
e
7
,
B
)
Å
(
e
13
,
G
)
Å
(
e
3
,
B ) =
=
ñ
1
Å
ñ
2
Å
ñ
3
Å
ñ
6
;
DB
1
= (
e
1
,
R
)
Å
(
e
2
,
G
)
Å
(
e
10
,
R
)
Å
(
e
8
,
G
)
Å
(
e
6
,
R
)
Å
(
e
4
,
G )=
= ñ
1
Å
ñ
4
Å
ñ
6
;
DB
2
= (
e
13
,
G
)
Å
(
e
18
,
R
)
Å
(
e
16
,
G
)
Å
(
e
15
,
R
)
Å
(
e
17
,
G
)
Å
(
e
14
,
R
) = ñ
7
;
DG
1
= (
e
10
,
R
)
Å
(
e
11
,
B
)
Å
(
e
18
,
R
)
Å
(
e
7
,
B
)
Å
(
e
6
,
R
)
Å
(
e
9
,
B
)
Å
Å
(
e
14
,
R
)
Å
(
e
3
,
B
)
Å
(
e
1
,
R
)
Å
(
e
5
,
B
)
Å
(
e
15
,
R
)
Å
(
e
12
,
B ) =
= ñ
2
Å
ñ
3
Å
ñ
4
Å
ñ
7
.
Colored 2-factors of the colored
cubic non-planar graph
H
4
are:
R
c
= DR
1
;
B
c
= DB
1
DB
2
;
G
c
=
DG
1
;
From this, the colors of
the basis cycles can be determined as:
c
1
(R
c
B
c
)
G; c
2
(R
c
G
c
)
B;
c
3
(R
c
G
c
)
B; c
4
(B
c
G
c
)
R;
c
5
W; c
6
(B
c
R
c
)
G;
c
7
(
B
c
G
c
)
R
;
c
0
W
.
Consider the edge coloring:
e
1
(c
1
c
3
)
G + B = R; e
2
(c
1
c
0
)
G + W = G;
e
3
(c
3
c
0
)
B + W = B; e
4
(c
3
c
4
)
B + R = G;
e
5
(c
1
c
4
)
G + R = B; e
6
(c
4
c
5
)
R + W = R;
e
7
(c
3
c
5
)
B + W = B; e
8
(c
5
c
6
)
G + W = G;
e
9
(c
4
c
6
)
R + G = B; e
10
(c
2
c
6
B + G = R;
e
11
(c
2
c
5
)
B + W = B;
e
12
(c
1
c
2
c
6
c
0
)
G + B + G + W = B;
e
13
(c
3
c
7
)
B + R = G; e
14
(c
7
c
0
)
R + W = R;
e
15
(c
7
c
0
)
R + W = R; e
16
(c
2
c
7
)
B + R = G;
e
17
(c
4
c
6
c
7
c
0
)
G + R + W + R = G;
e
18
(
c
5
c
7
)
R
+
W
=
R
.
Hence, Formula 5 is also
applicable to colored non-planar graphs.
A cyclic order of the form 1 – 2 – 3 (R – B – G) of
the traversal of edges for a vertex of a plane cubic graph
H
is further denoted
as the
colored rotation of vertices
. If the edges of a vertex are
colored with three colors, then the order of traversing the colors 1 – 2 – 3 (R
– B – G) for colored edges can be either clockwise or counterclockwise. We put “+1”
in correspondence with those vertices for which color rotation occurs
clockwise, and “-1” – with those for which the rotation direction is opposite.
Consider the following color rotation of the vertices shown in Fig. 15.
|
|
|
Fig.
15. Colored rotation of vertices.
|
Then, for the set of
vertices belonging to the face of a plane cubic graph, we can write the Heawood
system of equations [1] for each basis cycle and rim:
|
|
(6)
|
where
a
= 1,2,... ,
m
-
n
+2.
At the same time, the
solution of the Heawood system determines the coloring, since in the Heawood system
the clockwise colored rotation of the vertices of a plane cubic graph can be
put in correspondence with “+1”, and the
counterclockwise
colored rotation – with “-1”.
Thus, it is possible to write the Heawood equations
[1] in the following form:
x(v
1
) + x(v
4
) + x(v
5
)
+ x(v
8
) = (-1) + (+1) + (-1) + (+1)
º
0 (mod 3);
x(v
1
) + x(v
2
) + x(v
3
)
+ x(v
4
) = (-1) + (-1) + (+1) + (+1)
º
0 (mod 3);
x(v
5
) + x(v
6
) + x(v
7
)
+ x(v
8
) = (-1) + (-1) + (+1) + (+1)
º
0 (mod 3);
x(v
2
) + x(v
3
) + x(v
10
)
+ x(v
11
) = (-1) + (+1) + (-1) + (+1)
º
0 (mod 3);
x(v
6
) + x(v
7
) + x(v
14
)
+ x(v
15
) = (-1) + (+1) + (-1) + (+1)
º
0 (mod 3);
x(v
3
) + x(v
4
) + x(v
5
)
+ x(v
6
) + x(v
9
) + x(v
10
) + x(v
15
) +
x(v
16
) =
= (+1) + (+1) + (-1) + (-1) + (-1) + (-1) + (+1) + (+1)
º
0 (mod 3);
x(v
9
) + x(v
12
) + x(v
13
)
+ x(v
16
) = (-1) + (+1) + (-1) + (+1)
º
0 (mod 3);
x(v
9
) + x(v
10
) + x(v
11
)
+ x(v
12
) = (-1) + (-1) + (+1) + (+1)
º
0 (mod 3);
x(v
13
) + x(v
14
) + x(v
15
)
+ x(v
16
) = (-1) + (-1) + (+1) + (+1)
º
0 (mod 3);
x(v
1
) + x(v
2
) + x(v
7
)
+ x(v
8
) + x(v
11
) + x(v
12
) + x(v
13
)
+ x(v
14
) =
=
(-1) + (-1) + (+1) + (+1) + (+1) + (+1) + (-1) + (-1)
º
0 (
mod
3);
The following
theorem holds for maximal planar graphs.
Theorem 1
[4]
.
Let M be the
set of vertices of a plane cubic graph. Then for any correct coloring
|
|
(7)
|
Indeed,
x(v
1
) + x(v
2
)
+ x(v
3
) + x(v
4
) + x(v
5
) + x(v
6
) + x(v
7
)
+ x(v
8
) + x(v
9
) + x(v
10
) + x(v
11
) +
x(v
12
) + x(v
13
) + x(v
14
) + x(v
15
) +
x(v
16
) = (-1) + (-1) + (+1) + (+1) + (-1) + (+1) + (+1) + (-1) +
(-1) + (-1) + (+1) + (+1) + (-1) + (-1) + (+1) + (+1)
º
0 (mod4).
Thus, we can construct closed Heawood paths in a plane colored
cubic graph, sequentially selecting edges according to the color rotation of
the vertices.
= < e
3
[1],e
10
[2],e
9
[3],e
11
[1],e
14
[2],e
21
[3],e
20
[1],e
16
[2],e
15
[3],e
18
[1],
e
5
[2],e
1
[3]>;
= < e
3
[1],e
2
[2],e
6
[3],e
4
[1],e
5
[2],e
19
[3],e
20
[1],e
22
[2],e
24
[3],e
23
[1],
e
14
[2],e
13
[3]>;
= < e
23
[1],e
12
[2],e
9
[3],e
8
[1],e
2
[2],e
1
[3],e
4
[1],e
7
[2],e
15
[3],e
17
[1],
e
22
[2],e
21
[3]>;
= < e
11
[1],e
12
[2],e
24
[3],e
17
[1],e
16
[2],e
19
[3],e
18
[1],e
7
[2],e
6
[3],e
8
[1],
e
10
[2],e
13
[3]>.
Heawood closed paths pass
through an edge twice, but the second time is always in the opposite direction.
The length of the Heawood closed path is a multiple of three.
The article addresses algebraic methods for coloring arbitrary – both
plane and non-planar – cubic graphs. The methods are partially based on the corollaries
of the Tait’s theorem and the coloring of a plane cubic graph is described
using the fourth-order Klein group transformation. It is established that the
topological drawing of a plane graph, which is formally described by vertices rotation,
induces basis simple cycles of the cycle subspace of a graph. The transition to
graph coloring is done by coloring the edges of basis cycles. It is assumed
that the coloring was made by the methods presented in [3]. Details on the
formation of colored disks based on the coloring of edges are presented in the
article. The authors introduce the concept of embeddability of colored disks in
order to unambiguously describe the representation of colored disks by means of
basis cycles. In addition, the issues related to the mathematical description
of colored disks rotation operation and their subsequent recoloring are
considered in the article. The relationship between the colored vertex rotation
of a plane cubic graph and the closed Heawood paths is revealed and formally described.
1.
A.A. Zykov.
Fundamentals of Graph
Theory. – B C S Associates, 1990. – 365 p.
2.
I. Grossman, W Magnus.
In Groups
and Their Graphs. – Mathematical Association of America, 1992. – 195 p.
3.
Kurapov
S. V, Davidovsky M. V.
Visual algorithm for
coloring planar graphs // Scientific Visualization. – 201
8
, Vol. 10, No 3 – P. 1–33.
4.
N. Z. Shor, G. A. Donets.
Algebraic Approach to the
Plane Graph Coloring. – Naukova Dumka, 1982. English translation published by Springer-Verlag, Berlin, 1985.
5.
G.
Ringel
.
Map Color Theorem. – Repr.
of the orig. 1st ed. (1974), Springer, 2011. – 212 p.
6.
M. N. S. Swamy
. Graphs, networks, and
algorithms / Swamy, M.N.S., Thulasiraman K. – Wiley New York, 1981. – 592 p.
7.
P. G. Tait
. Remarks on the
Colourings of Maps // In Proc. R. Soc. Edinburgh 10: 729, 1880.
