Acyclic coloring of graphs of maximum degree five: Nine colors are enough

被引：23

作者：

Fertin, Guillaume

Raspaud, Andre

机构：

[1] Univ Nantes, CNRS, FRE, LINA, F-44322 Nantes, France

[2] Univ Bordeaux 1, CNRS, UMR, LaBRI, F-33405 Talence, France

来源：

INFORMATION PROCESSING LETTERS | 2007年 / 105卷 / 02期

关键词：

acyclic chromatic number; acyclic coloring algorithm; maximum degree 5; graph algorithms;

D O I：

10.1016/j.ipl.2007.08.022

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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. (c) 2007 Elsevier B.V. All rights reserved.

引用

页码：65 / 72

页数：8