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]. (C) 2011 Elsevier B.V. All rights reserved.
combinatorial problems graph coloring bounded degree graphs acyclic coloring