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 条
  • [41] An improved upper bound for the neighbor sum distinguishing index of graphs
    Wang, Guanghui
    Yan, Guiying
    DISCRETE APPLIED MATHEMATICS, 2014, 175 : 126 - 128
  • [42] Acyclic Edge Colorings of Planar Graphs Without Short Cycles
    Sun, Xiang-Yong
    Wu, Han-Liang
    OPERATIONS RESEARCH AND ITS APPLICATIONS, PROCEEDINGS, 2008, 8 : 325 - +
  • [43] Acyclic Edge Coloring of Planar Graphs Without Small Cycles
    Hou, Jianfeng
    Liu, Guizhen
    Wu, Jianliang
    GRAPHS AND COMBINATORICS, 2012, 28 (02) : 215 - 226
  • [44] Acyclic edge coloring of planar graphs without adjacent cycles
    Wan Min
    Xu BaoGang
    SCIENCE CHINA-MATHEMATICS, 2014, 57 (02) : 433 - 442
  • [45] Acyclic edge coloring of planar graphs without adjacent cycles
    WAN Min
    XU BaoGang
    Science China(Mathematics), 2014, 57 (02) : 433 - 442
  • [46] Acyclic Edge Coloring of Planar Graphs Without Small Cycles
    Jianfeng Hou
    Guizhen Liu
    Jianliang Wu
    Graphs and Combinatorics, 2012, 28 : 215 - 226
  • [47] On acyclic edge coloring of planar graphs without intersecting triangles
    Sheng, Ping
    Wang, Yingqian
    DISCRETE MATHEMATICS, 2011, 311 (21) : 2490 - 2495
  • [48] About acyclic edge colourings of planar graphs
    Fiedorowicz, Anna
    Haluszczak, Mariusz
    Narayanan, Narayanan
    INFORMATION PROCESSING LETTERS, 2008, 108 (06) : 412 - 417
  • [49] Acyclic 4-choosability of planar graphs
    Chen, Min
    Raspaud, Andre
    Roussel, Nicolas
    Zhu, Xuding
    DISCRETE MATHEMATICS, 2011, 311 (01) : 92 - 101
  • [50] Star-Chromatic Numbers of Planar Graphs
    WANG Yijiu Institute of Operations Research
    Journal of Systems Science and Systems Engineering, 1998, (02) : 63 - 66
12345