Acyclic coloring of graphs with maximum degree at most six

Abstract An acyclic k -coloring of a graph G is a proper vertex coloring using k colors such that any cycle of G is colored with at least three colors, and the minimum integer k is called the acyclic chromatic number of G , denoted by χ a ( G ) . Grunbaum conjectured that the acyclic chromatic number of graphs with maximum degree at most Δ is no more than Δ + 1 in 1973. By now, the conjecture has been proved only for Δ ≤ 4 . We show that χ a ( G ) ≤ 9 for Δ ≤ 6 , which improves the result χ a ( G ) ≤ 10 of Zhao et al. (2014).