Acyclic coloring with few division vertices

An acyclic k-coloring of a graph G is a mapping ϕ from the set of vertices of G to a set of k distinct colors such that no two adjacent vertices receive the same color and ϕ does not contain any bichromatic cycle. In this paper we prove that every planar graph with n   vertices has a 1-subdivision that is acyclically 3-colorable (respectively, 4-colorable), where the number of division vertices is at most 2n−52n−5 (respectively, n−3n−3). On the other hand, we prove a 1.28n (respectively, 0.3n) lower bound on the number of division vertices for acyclic 3-colorings (respectively, 4-colorings) of planar graphs. Furthermore, we establish the NP-completeness of deciding acyclic 4-colorability for graphs with maximum degree 5 and for planar graphs with maximum degree 7.