On acyclic colorings of graphs

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 n₁, n₂,..., n_k vertices in its P₁, P₂,..., P_k partition respectively is acyclically (2k - 1)-colorable using Σ_{i≠j, i, j≤k} n_in_j + n_max + (k-1) - Σ_i=0^k-1 (k-i)n_i+1 division vertices, where n_max = max(n₁, n₂,..., n_k). Finally we show that there is an infinite number of cubic planar graphs which are acyclically 3-colorable.