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 
Figure 1. Acyclic coloring of central graph of 
Figure 2. Acyclic coloring of central graph of 
is the intersection graph 
Thus the points of 
are the lines of 
with two points of 
are adjacent whenever the corresponding lines of
are.
3.2. Structural Properties of Line Graph of Central Graph of 
Line graph of central graph of
is denoted by
• 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).
Figure 4. Acyclic coloring of middle graph of
.
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
Figure 5. Acyclic coloring of middle graph of
.
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.
NOTES