Acyclic coloring of graphs of maximum degree five: Nine colors are enough |
| |
| Authors: | Guillaume Fertin André Raspaud |
| |
| Affiliation: | a LINA, FRE CNRS 2729, Université de Nantes, 2 rue de la Houssinière, BP 92208, F44322 Nantes Cedex 3, France
b LaBRI UMR CNRS 5800, Université Bordeaux 1, 351 Cours de la Libération, F33405 Talence Cedex, France |
| |
| 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. |
| |
| Keywords: | Acyclic chromatic number Acyclic coloring algorithm Maximum degree 5 Graph algorithms |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
