ABSTRACT

Using the linear space over the binary field that related to a graph G, a sufficient and necessary condition for the chromatic number of G is obtained.

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 A_n 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 A_n 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 R_G. 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

is the linear subspace of

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,

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

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 A₂. 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.

[1] REFERENCES

[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.