DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Acyclic Coloring of Graphs of Maximum Degree Δ

Guillaume Fertin, André Raspaud


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  [albert]. 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.

Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page

Valid XHTML 1.0 Transitional