Acyclic Edge Chromatic Number of Outerplanar Graphs

被引：36

作者：

Hou, Jian-Feng ^{[1
,2
]}

Wu, Jian-Liang ^{[1
]}

Liu, Gui-Zhen ^{[1
]}

Liu, Bin ^{[1
]}

机构：

[1] Shandong Univ, Sch Math, Jinan 250100, Peoples R China

[2] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Peoples R China

来源：

JOURNAL OF GRAPH THEORY | 2010年 / 64卷 / 01期

关键词：

acyclic; edge coloring; outerplanar graph; PLANAR GRAPHS; COLORINGS;

D O I：

10.1002/jgt.20436

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by 7(G), is the least number of colors in an acyclic edge coloring of G. In this paper, we determine completely the acyclic edge chromatic number of outerplanar graphs. The proof is constructive and supplies a polynomial time algorithm to acyclically color the edges of any outerplanar graph G using chi(a)'(G) colors. (C) 2009 Wiley Periodicals. Inc. J Graph Theory 64: 22-36, 2010

引用

页码：22 / 36

页数：15

共 13 条

[1] Algorithmic aspects of acyclic edge colorings [J].

Alon, N ;

Zaks, A .

ALGORITHMICA, 2002, 32 (04) :611-614

[2] Acyclic edge colorings of graphs [J].

Alon, N ;

Sudakov, B ;

Zaks, A .

JOURNAL OF GRAPH THEORY, 2001, 37 (03) :157-167

[3] ACYCLIC COLORING OF GRAPHS [J].

ALON, N ;

MCDIARMID, C ;

REED, B .

RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :277-288

[4] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

BORODIN, OV .

DISCRETE MATHEMATICS, 1979, 25 (03) :211-236

[5]

Burnstein M.I., 1979, SOOBSC AKAD NAUK GRU, V93, P21

[6] ACYCLIC COLORINGS OF PLANAR GRAPHS [J].

GRUNBAUM, B .

ISRAEL JOURNAL OF MATHEMATICS, 1973, 14 (04) :390-408

[7] Acyclic edge colorings of planar graphs and seriesparallel graphs [J].

Hou JianFeng ;

Wu JianLiang ;

Liu GuiZhen ;

Liu Bin .

SCIENCE IN CHINA SERIES A-MATHEMATICS, 2009, 52 (03) :605-616

[8] PAPER OF GRUNBAUM ON ACYCLIC COLORINGS [J].

KOSTOCHKA, AV ;

MELNIKOV, LS .

DISCRETE MATHEMATICS, 1976, 14 (04) :403-406

[9]

Molloy M., 1998, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, P524, DOI 10.1145/276698.276866

[10] Improved bounds on acyclic edge colouring [J].

Muthu, Rahul ;

Narayanan, N. ;

Subramanian, C. R. .

DISCRETE MATHEMATICS, 2007, 307 (23) :3063-3069

← 1 2 →