Graphs with maximum degree 6 are acyclically 11-colorable

An acyclic k-coloring of a graph G is a proper vertex coloring of G, which uses at most k colors, such that the graph induced by the union of every two color classes is a forest. In this note, we prove that every graph with maximum degree six is acyclically 11-colorable, thus improving the main result of Yadav et al. (2009) [11].

► In this paper we need to prove the existence of a certain kind of spanning trees in regular graphs. ► A good spanning tree of a Δ regular graph G is a spanning tree T such that T   contains a vertex adjacent to Δ−1Δ−1 leaves. ► We then use such good spanning trees to prove our main result on acyclic colorings. ► Every graph with maximum degree 6 is acyclically 11-colorable.