Graphs with maximum degree 5 are acyclically 7-colorable

Abstract

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)²/4⌋-coloring.