On Acyclic Colorings of Graphs
Published in 2012 15th International Conference on Computer and Information Technology (ICCIT), 2012
An acyclic coloring of a graph G is a coloring of the vertices of G, where no two adjacent vertices of G receive the same color and no cycle of G contains vertices of only two colors. An acyclic k-coloring of a graph G is an acyclic coloring of G using k colors. In this paper we show the necessary and sufficient condition of acyclic coloring of a complete k-partite graph. Then we derive the minimum number of colors for acyclic coloring of such graphs. We also show that any complete k-partite graph G having n1, n2, ...., nk vertices in its P1, P2, ...., Pk partition respectively is acyclically (2k −1)-colorable using X i6=j,i,j≤kninj +nmax +(k −1)− k−1 X i =0 (k −i)ni+1 division vertices, where nmax = max(n1, n2, ..., nk). Finally we show that there is an infinite number of cubic planar graphs which are acyclically 3-colorable.