An improved bound on acyclic chromatic index of planar graphs

被引：8
|
作者：
Guan, Yue [1 ]
Hou, Jianfeng [1 ]
Yang, Yingyuan [1 ]
机构：
[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350003, Fujian, Peoples R China
来源：
DISCRETE MATHEMATICS | 2013年 / 313卷 / 10期
基金：
中国国家自然科学基金;
关键词：
Acyclic edge coloring; Planar graph; Critical graph; EDGE COLORINGS;
D O I：
10.1016/j.disc.2013.02.002
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
A proper edge coloring of a graph G is called acyclic if there is no bichromatic cycle in G. The acyclic chromatic index of G, denoted by chi'(a)(G), is the least number of colors k such that G has an acyclic k-edge-coloring. Basavaraju et al. [M. Basavaraju, L.S. Chandran, N. Cohen, F. Havet and T. Muller, Acyclic edge-coloring of planar graphs, SIAM journal of Discrete Mathematics 25 (2) (2011)463-478] showed that chi'(a)(G) <= Delta(G) + 12 for any planar graph G with maximum degree Delta(G). In this paper, the bound is improved to Delta(G) + 10. (C) 2013 Elsevier B.V. All rights reserved.
引用
收藏
页码：1098 / 1103
页数：6
相关论文
共 50 条
  • [31] An improved upper bound on the adjacent vertex distinguishing chromatic index of a graph
    Zhang, Lianzhu
    Wang, Weifan
    Lih, Ko-Wei
    DISCRETE APPLIED MATHEMATICS, 2014, 162 : 348 - 354
  • [32] Acyclic edge colorings of planar graphs and seriesparallel graphs
    Hou JianFeng
    Wu JianLiang
    Liu GuiZhen
    Liu Bin
    SCIENCE IN CHINA SERIES A-MATHEMATICS, 2009, 52 (03): : 605 - 616
  • [33] Acyclic edge colorings of planar graphs and seriesparallel graphs
    JianFeng Hou
    JianLiang Wu
    GuiZhen Liu
    Bin Liu
    Science in China Series A: Mathematics, 2009, 52 : 605 - 616
  • [34] A bound for the game chromatic number of graphs
    Dinski, T
    Zhu, XD
    DISCRETE MATHEMATICS, 1999, 196 (1-3) : 109 - 115
  • [35] Improved Bounds on the Generalized Acyclic Chromatic Number
    Wu, Yu-wen
    Tan, Kan-ran
    Yan, Gui-ying
    ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2016, 32 (01): : 67 - 72
  • [36] Acyclic total colorings of planar graphs without l cycles
    Sun, Xiang Yong
    Wu, Jian Liang
    ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2011, 27 (07) : 1315 - 1322
  • [37] An improved upper bound on the linear 2-arboricity of planar graphs
    Wang, Yiqiao
    DISCRETE MATHEMATICS, 2016, 339 (01) : 39 - 45
  • [38] Acyclic edge coloring of planar graphs with girth at least 5
    Hou, Jianfeng
    Wang, Weitao
    Zhang, Xiaoran
    DISCRETE APPLIED MATHEMATICS, 2013, 161 (18) : 2958 - 2967
  • [39] Acyclic edge coloring of planar graphs without adjacent cycles
    Min Wan
    BaoGang Xu
    Science China Mathematics, 2014, 57 : 433 - 442
  • [40] Acyclic Edge Coloring of Planar Graphs without Adjacent Triangles
    Dezheng XIE 1
    2.School of Mathematics and Computer Science
    Journal of Mathematical Research with Applications, 2012, (04) : 407 - 414
12345