Keywords: Vertex Coloring; Chromatic Number; Outer-Kernel Subspace; Plane Graph
1. Introduction
Let
be a graph, where V is a set of vertices and E is a set of edges of G. A vertex coloring of a graph G is a coloring to all the vertices of G with p colors so that no two adjacent vertices have the same color. Such the graph is called
-coloring. The minimal number p is called the chromatic number of G, and is denoted by
. The so-called Four Color Problem is that for any plane graph G,
[1].
The coloring of a graph G is an interesting problem for many people [2]. This is mainly caused by the Four Color Problem [3].
In this paper, putting a graph into a linear space over the binary field
, we obtain the sufficient and necessary condition for the chromatic number of G.
And as an application of above result, we give a characterization for a maximal plane graph to be 4-coloring.
2. The Linear Space An over GF(2)
Now we introduce the linear space over the field
.
Firstly, the field
contains only two members:
, where the addition and multiplication are as usual excepting that
.
Let
be the n vertices, the all vectors of the linear space
are formed of the symbolic expression
.
It has
vectors. The addition of two vectors is defined by
.
Here, the
vertices
will serve as the most basic elements of the linear space
. They will be as a basis of the linear space
. For them the basic assumption is that these n vertices are linearly independent in
.
According to the addition in
, for any vector
in the linear space
, it has
.
Here we denote the zero vector by 0.
For a vector
the order of the vector
is defined by
where the
means that the addition is the usual addition in the integer set.
A vector with k order is called a k-order vector, and a vector whose order is even is called an even-order vector.
We now give some structures to the linear space
. In other words, we want to “put” a graph into the linear space
.
In the linear space
, 1-order vectors are vertices of a graph. The edge is expressed as the 2-order vertex, i.e.
is the edge
. So we have two ways to describe a edge: by
(in the usual sense), or by
(in the linear space
).
In the following, we always discuss a graph in the linear space
, it means we express edges with the second form.
All the 2-order vectors in the linear space
are the all possible edges with
vertices
, that we denote by
:
.
For a giving graph
with
vertices, in the linear space
, the elements of the set
are the 2-order vectors of
, then the edge set
of
is the subset of the set
,
.
We give two examples here.
1) For the set
with all the 2-order vertices in
, the graph
is a complete graph, whose any two vertices are adjacent.
2) For a graph
with
vertices, the complementary set of
in the set of the 2-order vertices of
is
. Then the complementary graph
of the graph
is
.
We now see the addition in
. For a path of
with a sequence of edges
, where the end-points are
and
, the sum of the edges is:
.
This expression indicates the relation between the addition in the linear space and the connectivity of a graph. That is why we put the graph into the linear space
.
Lemma 1. The sum of even-order vectors is even-order.
This is clear by the property that
if and only if
.
As a special case of the Lemma 1, we have Lemma 2. Let
are the vertices of
, if
then
is even.
Definition. Let An be the n-dimensional linear space derived by the graph
above, and
be a set of 2-order vectors. Denote by
the linear subspace spanned by RG. If there are no edges of E in
, i.e.
(1)
then
is called an outer-kernel subspace of
. And
is a maximal outer-kernel subspace if the rank of
is maxima in all the outer-kernel subspace of
.
Now we give some basic properties of a outer-kernel subspace of a graph
.
By definition,
is a subspace of
. Denote the set of all 2-order vectors of
by
, then
is a subgraph of the complementary graph
of
, here
is the 1-order vectors appeared in
. The subgraph
consists of some connected blocks.
Lemma 3. Let
be a connected block of
, and
be the vertices of
, then
,
is a complete graph
in the
and
![](https://www.scirp.org/html/htmlimages\1-1200164x\7ef115ca-570f-4783-b220-dd6a15355739.png)
is the linear subspace of ![](https://www.scirp.org/html/htmlimages\1-1200164x\430ff0f2-8522-4b70-b4fc-75b22a648d5d.png)
This lemma means that every connected block of
is a complete graph.
Proof. Because
is spanned by 2-order vectors, so
.
Suppose that
for
is a linear space , then
.
Since
is connected block of
, so
. On the other hand, if
, then
. Hence all the 2-order vectors formed by the set of vertices
span the linear subspace
of
. Thus the connected block
is a complete graph in
.
Lemma 4. If
, then
is even and there exists a
such that
.
Proof. By the definition of
,
is even. For
is spanned by 2-order vectors, so
is in a connected block
of
. Thus another vertex
of
must appear in
.
3. The Main Results
The outer-kernel subspace plays an important role in the problem of vertex coloring.
Theorem 1. Let
be a graph with n vertices, then the sufficient and necessary condition for
to be p-coloring is that the rank of an outer-kernel subspace
of
is
.
Proof. First we prove the necessity. Suppose that the graph
is
-coloring. Then all the vertices of
can be divided into
subsets by the colors:
. (2)
That means the vertices with a same color are in the same subset. Because it may have a subset with only one vertex, we denote the one-vertex subsets with different colors by
.
The elements of subset
are not less then 2. Denote them by
then by (2)
. (3)
Let
,
and
then the vectors of
are independent. Hence by (3), the dimension of subspace
spanned by
is
(4)
It is clear that
.
For the sufficiency, suppose that there exists an outerkernel subspace
with condition (1), and the dimension of
is
.
We divide the vertices of
into some subsets according to the subspace
. If for two vertices
and
there have
, (5)
then we put
and
into a same subset. Like the notation of congruence we denote
.
Obviously, if a vertex a appears in
, then there has at least another vertex in the same subset with a. If a vertex does not appear in
, then this vertex forms a subset by itself, i.e. the subset contains only one vertex.
Lemma 5. The vertices from different subset are linear independence on
, i.e. if
belong to different subsets respectively, then
.
In fact, if
, by Lemma 4, there exists a vertex
such that
. That means
is in the same subset.
Now we go on with the proof of the sufficiency. Suppose that the 2-order vectors
form a basis of
, and the vertices of the graph G are now divided into the disjoint subset
by the method above. Take
,
, then any vertex a of G must be in some subset
and by (5) we have
.
So any vertex of
can be expressed by
and an element of
. Thus by Lemma 5,
![](https://www.scirp.org/html/htmlimages\1-1200164x\e572fae8-21a1-41f9-a2e2-34795cab8664.png)
are the basis of linear space
. Hence
.
By the definition of
and (5) we know that the two vertices in the same subset
are non-adjacent. Thus, we can assign one color to the vertices of each subset
. So we just need p colors for G. The graph is
-coloring.
Due to Theorem 1 and the expression (4), we have:
Theorem 2. For a graph G with n vertices, the sufficient and necessary condition for
is that the rank of a maximal outer-kernel subspace
is
.
4. An Application to Plane Graphs
As an application of Theorem 1, we consider a result of the coloring to the plane graph.
A maximal plane graph is a graph G such that for any two non-adjacent vertices a and b of G, G added to the edge ab makes a non-planar graph. It is clear that all the faces of a maximal plane graph are triangles.
A maximal plane graph is 3-CR-edge coloring if we can color its edges by 3 colors such that the three edges of every its triangle face are coloring by different colors. Later we will see that the CR in the definition is borrowed from the Cauchy-Riemann condition in the complex function theory.
Theorem 3. If a maximal plane graph is 3-CR-edge coloring, then the graph is 4-vertex coloring.
The inverse of the Theorem 3 is true, too. That means if a maximal plane graph is 4-vertex coloring, then the graph is 3-CR-edge coloring.
Proof. We introduce the 2-demensional linear space
:
.
Let
be 3-CR-edge coloring, and the all edges of G can map to the three elements
of
by their colors, respectively. That is the mapping f
![](https://www.scirp.org/html/htmlimages\1-1200164x\6c3175a0-ffef-4556-bf8f-8bb39581511e.png)
such that if
are the vertices of a face of G, then
(6)
For a path of G with the end-point a, b and the sequence of the edges
, we define
. (7)
By the condition of 3-CR-edge coloring, the extending mapping f by (7) is dependent only on the end-point a and b, and independent on their path.
Let
be the
-dimensional linear subspace spanned by all the 2-order vectors of the space
. Then f is the homomorphic mapping from subspace
onto the space A2. The homomorphic kernel
consists of such vector e of
that satisfies
(8)
Suppose
is the subset of 2-order vectors of
that satisfies (8) and
is spanned by R. Then by (8) we have
.
Denote the linear independent spanning elements of
by
, that is just the basis of
. And
.
We take
such that
.
Then the linear subspace
is spanning by
.
Hence
, and
. By Theorem 1, the graph G is 4-vertex coloring.
[2] F. Harary, “Graph Theory,” Addison-Wesley, Boston, 1969.
[3] P. Erdös and A. Hajnal, “Chromatic Number of Finite and Infinite Graphs and Hypergraphs,” Discrete Mathematics, Vol. 53, 1985, pp. 281-285.
[4] N. Biggs, E. Lloyd and R. Wilson, “Graph Theory 1736- 1936,” Oxford University Press, Oxford, 1986.