Graphs with maximum degree 5 are acyclically 7-colorable
Alexandr V. Kostochka, Christopher J. Stocker · Ars Mathematica Contemporanea · 2011
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.