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 等数据库收录! |
|