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

Font Size:
DMTCS Conference vol AE (2005), pp. 389-396

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

### DMTCS Conference Volume AE (2005), pp. 389-396

author: Guillaume Fertin and André Raspaud Acyclic Coloring of Graphs of Maximum Degree Δ Acyclic chromatic number, acyclic coloring algorithm, maximum degree 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. If your browser does not display the abstract correctly (because of the different mathematical symbols) you may look it up in the PostScript or PDF files. Guillaume Fertin and André Raspaud (2005), Acyclic Coloring of Graphs of Maximum Degree Δ , in 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), Stefan Felsner (ed.), Discrete Mathematics and Theoretical Computer Science Proceedings AE, pp. 389-396 For a corresponding BibTeX entry, please consider our BibTeX-file. dmAE0175.ps.gz (65 K) dmAE0175.ps (170 K) dmAE0175.pdf (173 K)