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
    Guan, Yue
    Hou, Jianfeng
    Yang, Yingyuan
    [J]. DISCRETE MATHEMATICS, 2013, 313 (10) : 1098 - 1103
  • [12] Acyclic Edge Chromatic Number of Outerplanar Graphs
    Hou, Jian-Feng
    Wu, Jian-Liang
    Liu, Gui-Zhen
    Liu, Bin
    [J]. JOURNAL OF GRAPH THEORY, 2010, 64 (01) : 22 - 36
  • [13] Acyclic chromatic index of planar graphs with triangles
    Hou, Jianfeng
    Roussel, Nicolas
    Wu, Jianliang
    [J]. INFORMATION PROCESSING LETTERS, 2011, 111 (17) : 836 - 840
  • [14] Improved bounds for acyclic chromatic index of planar graphs
    Hou, Jianfeng
    Liu, Guizhen
    Wang, Guanghui
    [J]. DISCRETE APPLIED MATHEMATICS, 2011, 159 (08) : 876 - 881
  • [15] Acyclic edge colorings of planar graphs and seriesparallel graphs
    Hou JianFeng
    Wu JianLiang
    Liu GuiZhen
    Liu Bin
    [J]. SCIENCE IN CHINA SERIES A-MATHEMATICS, 2009, 52 (03): : 605 - 616
  • [16] Acyclic edge coloring of planar graphs with Δ colors
    Hudak, David
    Kardos, Frantisek
    Luzar, Borut
    Sotak, Roman
    Skrekovski, Riste
    [J]. 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
    Shu, Qiaojun
    Wang, Weifan
    Wang, Yiqiao
    [J]. JOURNAL OF GRAPH THEORY, 2013, 73 (04) : 386 - 399
123