Graphs with maximum degree 5 are acyclically 7-colorable
An acyclic coloring is a proper coloring with the additional property that the union of any two color classes induces a forest. We show that every graph with maximum degree at most 5 has an acyclic 7-coloring. We also show that every graph with maximum degree at most r has an acyclic (1 + ⌊(r + 1)2/4⌋-coloring.
Acyclic coloring, maximum degree