On acyclic colorings of graphs
Abu Reyan Ahmed, Md. Mazharul Islam, Md. Saidur Rahman · 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 a complete k-partite graph G having n1, n2,…, nkvertices in its Ρ1,Ρ2,…, Pkpartition respectively is acyclically (2k − 1)-colorable using ∑i≠j, i, j≤kninj+ nmax+ (k−1) − ∑k−1i=0(k−i)ni+1division 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.