ABSTRACT

An acyclic coloring of a graph is a proper vertex coloring such that the union of any two color classes induces a disjoint collection of trees.The purpose of this paper is to derive exact values of acyclic chromatic number of some graphs.

1. Introduction

Graph coloring is a branch of graph theory which deals with such partitioning problems. For example, suppose that we have world map and we would like to color the countries so that if two countries share a boundary line, then they need to get different colors. We can translate the map to graph by letting countries be represented by vertices and two vertices are made adjacent if and only if the corresponding countries share a boundary line. Then the problem of map coloring is equivalent to vertex coloring of the corresponding graph. Hence the original map coloring now reduces to vertex coloring of the associated graph.

Coloring of a graph is an assignment of colors to the elements like vertices or edges or faces (regions) of a graph. It is said to be a proper coloring, if no two adjacent elements are assigned the same color. The most common types of graph colorings are vertex coloring, edge coloring and face coloring.

A vertex coloring of a graph is an assignment of colors to its vertices so that no two vertices have the same color. The chromatic number of a graph is the minimum number of colors needed to label the vertices, so that adjacent vertices receive different colors.

A proper vertex coloring of a graph is acyclic if every cycle uses at least three colors [1]. The acyclic chromatic number of denoted by is the minimum colors required for its acyclic coloring.

2. Acyclic Coloring of Central Graph of

2.1. Central Graph [2]

Let be a finite undirected graph with no loops and multiple edges. The central graph of a graph is obtained by subdividing each edge of exactly once and joining all the non-adjacent vertices of

2.2. Structural Properties of Central Graphs

Let be any undirected simple graph, then by the definition of of a graph.

• The number of vertices in the central graph of is

• For any graph there exists  exactly vertices of degree and vertices of degree in

• The central graph of two isomorphic graphs is also isomorphic.

• The maximum degree in is

• Central graph of any graph is connected.

• If is any graph with odd then is Eulerian.

2.3. Theorem

The acyclic coloring of central graph of cycle, for

Proof

Consider the graph with vertex set Let be the central graph of which is obtained by sub dividing each edge of exactly once and joining non adjacent vertices of Let the newly introduced vertices be with Consider the color class Now assign a proper coloring to the vertices as follows. The coloring is in such a way that the sub graph induced by any two color is a forest containing at most the path The vertices are assigned the cololur for for for

Case 1: When

The newly are assigned the colors and respectively and all others are colored properly.

Case 2: When

all others are assigned so that the coloring is proper. Now the coloring is obviously acyclic, by the very arrangement of the colors. It is also minimum, because if we replace any color by an already used color, it will become either improper or cyclic (Figures 1 and 2).

2.4. Note

for

3. Acyclic Coloring of Line Graph of Central Graph of

3.1. Definition

Let be a finite undirected graph with no loops and multiple edges, the line graph of denoted by

is the intersection graph Thus the points of are the lines of with two points of are adjacent whenever the corresponding lines ofare.

3.2. Structural Properties of Line Graph of Central Graph of

• Number of vertices in

• Maximum Degree of vertices = Minimum Degree of vertices

• contains copies of vertex disjoint

• There is a cycle of length with alternate edges from each of the complete graph

3.3. Theorem

For any complete graph

Proof:

Let be the complete graph on vertices. Consider its line graph of central graph it contains copies of vertex disjoint sub graphs and which are marked in anti-clockwise direction. Let

where so that the total number of vertices in is Here there exist a unique bridge between each pair of sub graphs The bridge in the consecutive pairs of sub graph is given by for it is and for it is only for form a bridge in the sub graph . In a similar manner bridges are formed in non consecutive pairs also. Consider the color class Assign the color to the vertex for Next we prove that the coloring is acyclic. That is the coloring does not induce a bi-chromatic cycle. Clearly for each complete sub graph the coloring is acyclic (it never induce a bi-chromatic cycle). Now exactly two pairs of sub graphs never allow to induce a bi-chromatic cycle for any pair as there is only a unique bridge between each pair of sub graphs Note that bichromatic cycle is possible only for even cycles. The coloring is in such a way that more than three sub graphs never allow to induce a bi-chromatic cycle for any pair The maximum number of times a color will occur in any bi-chromatic path in this coloring is three. So the above said coloring acyclic. Also the coloring is minimum, as contains the subgraph, minimum colors are required for its proper coloring (Figure 3).

4. Acyclic Coloring of Middle Graph of

4.1. Middle Graph [3]

Let be a graph with vertex set and edge set The middle graph of denoted by is defined as follows. The vertex set of is Two vertices in the vertex set of are adjacent in in case one of following holds:

1) are in and are adjacent in 2) is in is in and are incident in.

4.2. Theorem

The acyclic chromatic number of the middle graph of is for

Proof

and in which with Let be the middle graph of the n-cycle. By the definition of middle graph

and

Then in the middle graph, there are -vertices of degree and another -vertices of degree 4. Let be the cycle of length in with degree of each vertex and be the cycle of length in with degree of vertices alternately and 4. The cycle are assigned the colors and alternately with last vertex preceding to by All other vertices except vertices adjacent to (which are colored as) are colored as The coloring is minimum, as for any cycle minimum colors needed for its acyclic coloring. The coloring is acyclic (Figure 4).

5. Acyclic Coloring of Total Graph of

5.1. Total Graph [3]

Let be a graph with vertex set and edge set The total graph of denoted by is defined as follows. The vertex set of is Two vertices in the vertex set of are adjacent in in case one of the following holds:

1) are in and is adjacent to in 2) are in and are adjacent in 3) is in is in and are incident in.

• 5.2. Some Structural Properties of Total Graph of

• Every cycle has a-regular total graph.

• The number of vertices in the total graph of is 2 times the number of vertices in the cycle

• The number of edges in the total graph of is 4 times the number of edges in the cycle

• The total graph of is Eulerian.

• The total graph of is Hamiltonian.

5.3. Theorem

The acyclic chromatic number of the total graph of is for

Proof

Let and in which with Let be the total graph of the n-cycle. By the definition of total graph and

By Menger’s theorem as, there are four pair wise vertex-independent paths between any two non adjacent vertices, the total graph of is -connected. To prove that if possible consider the color class with such that the coloring is acyclic. Then there exist no pair such that they induce a bi-chromatic cycle. i.e., there exist a three vertex cut in This is a contradiction to the fact that is -connected. Also acyclic chromatic number is can’t be 5, as in this case we can replace a color by an already used color.

Therefore for (Figure 5).

5.4. Note

6. Acknowledgements

The authors are thankful to the anonymous reviewers for their valuable comments and constructive suggestions.

REFERENCES

NOTES

^*Middle, total graphs of cycle.