Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428256 | Information Processing Letters | 2008 | 8 Pages |
Abstract
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. In this paper, we show that any graph of maximum degree 5 has acyclic chromatic number at most 9, and we give a linear time algorithm that achieves this bound.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics