Acyclic Coloring of Graphs of Maximum Degree
Guillaume Fertin · 2005
An acyclic coloring of a graph G is a coloring of its vertices such that: (i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G, and is denoted by a(G). We show that any graph of maximum degree ∆ has acyclic chromatic number at most ∆(∆−1) 2 for any ∆ ≥ 5, and we give an O(n ∆ 2) algorithm to acyclically color any graph of maximum degree ∆ with the above mentioned number of colors. This result is roughly two times better than the best general upper bound known so far, yielding a(G) ≤ ∆( ∆ − 1) + 2 [ACK + 04]. By a deeper study of the case ∆ = 5, we also show that any graph of maximum degree 5 can be acyclically colored with at most 9 colors, and give a linear time algorithm to achieve this bound.