Acyclic colorings of graph subdivisions revisited

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 is bichromatic. An acyclic k-coloring of G is an acyclic coloring of G using at most k colors. In this paper we prove that any triangulated plane graph G with n   vertices has a subdivision that is acyclically 3-colorable, where the number of division vertices is at most 2.75n−62.75n−6. This upper bound on the number of division vertices reduces to 2n−62n−6 in the case of acyclic 4-coloring. We show that it is NP-complete to decide whether a graph with degree at most 6 is acyclically 4-colorable or not. Furthermore, we give some upper bounds on the number of division vertices for acyclic 3-coloring of subdivisions of k-trees and cubic graphs.