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