Acyclic edge coloring of planar graphs with girth at least 5

被引：7

作者：

Hou, Jianfeng ^{[1
]}

Wang, Weitao ^{[1
]}

Zhang, Xiaoran ^{[1
]}

机构：

[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China

来源：

DISCRETE APPLIED MATHEMATICS | 2013年 / 161卷 / 18期

基金：

中国国家自然科学基金;

关键词：

Planar graph; Girth; Acyclic edge coloring; Critical; SPARSE HESSIAN MATRICES; CHROMATIC INDEXES;

D O I：

10.1016/j.dam.2013.06.013

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A proper edge coloring of a graph G is acyclic if there is no bichromatic cycle in G. The acyclic chromatic index of G, denoted chi(a)'(G), is the least number of colors k such that G has an acyclic k-edge-coloring. In this paper, it is shown that if G is a planar graph with girth at least 5 and maximum degree Delta, then chi(a)'(G) <= Delta + 1. Moreover, Delta >= 9, then chi(a)'(G) = Delta. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：2958 / 2967

页数：10

共 23 条

[11] An improved bound on acyclic chromatic index of planar graphs [J].

Guan, Yue ;

Hou, Jianfeng ;

Yang, Yingyuan .

DISCRETE MATHEMATICS, 2013, 313 (10) :1098-1103

[12] Acyclic Edge Chromatic Number of Outerplanar Graphs [J].

Hou, Jian-Feng ;

Wu, Jian-Liang ;

Liu, Gui-Zhen ;

Liu, Bin .

JOURNAL OF GRAPH THEORY, 2010, 64 (01) :22-36

[13] Acyclic chromatic index of planar graphs with triangles [J].

Hou, Jianfeng ;

Roussel, Nicolas ;

Wu, Jianliang .

INFORMATION PROCESSING LETTERS, 2011, 111 (17) :836-840

[14] Improved bounds for acyclic chromatic index of planar graphs [J].

Hou, Jianfeng ;

Liu, Guizhen ;

Wang, Guanghui .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (08) :876-881

[15] 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

[16] Acyclic edge coloring of planar graphs with Δ colors [J].

Hudak, David ;

Kardos, Frantisek ;

Luzar, Borut ;

Sotak, Roman ;

Skrekovski, Riste .

DISCRETE APPLIED MATHEMATICS, 2012, 160 (09) :1356-1368

[17]

Kostochka AV, 1997, J GRAPH THEOR, V24, P331, DOI 10.1002/(SICI)1097-0118(199704)24:4<331::AID-JGT5>3.0.CO

[18]

2-P

[19]

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

[20] Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4 [J].

Shu, Qiaojun ;

Wang, Weifan ;

Wang, Yiqiao .

JOURNAL OF GRAPH THEORY, 2013, 73 (04) :386-399

← 1 2 3 →