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 条
  • [21] Acyclic edge coloring of planar graphs with Δ colors
    Hudak, David
    Kardos, Frantisek
    Luzar, Borut
    Sotak, Roman
    Skrekovski, Riste
    DISCRETE APPLIED MATHEMATICS, 2012, 160 (09) : 1356 - 1368
  • [22] PRECISE UPPER BOUND FOR THE STRONG EDGE CHROMATIC NUMBER OF SPARSE PLANAR GRAPHS
    Borodin, Oleg V.
    Ivanova, Anna O.
    DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2013, 33 (04) : 759 - 770
  • [23] d-Regular Graphs of Acyclic Chromatic Index at Least d+2
    Basavaraju, Manu
    Chandran, L. Sunil
    Kummini, Manoj
    JOURNAL OF GRAPH THEORY, 2010, 63 (03) : 226 - 230
  • [24] Acyclic chromatic indices of fully subdivided graphs
    Fiedorowicz, Anna
    Haluszczak, Mariusz
    INFORMATION PROCESSING LETTERS, 2012, 112 (13) : 557 - 561
  • [25] New bounds for the acyclic chromatic index
    Bernshteyn, Anton
    DISCRETE MATHEMATICS, 2016, 339 (10) : 2543 - 2552
  • [26] Local conditions for planar graphs of acyclic edge coloring
    Wenwen Zhang
    Journal of Applied Mathematics and Computing, 2022, 68 : 721 - 738
  • [27] Local conditions for planar graphs of acyclic edge coloring
    Zhang, Wenwen
    JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2022, 68 (02) : 721 - 738
  • [28] Defective acyclic colorings of planar graphs
    Lo, On-Hei Solomon
    Seamone, Ben
    Zhu, Xuding
    JOURNAL OF GRAPH THEORY, 2024, 107 (04) : 729 - 741
  • [29] A note on acyclic number of planar graphs
    Petrusevski, Mirko
    Skrekovski, Riste
    ARS MATHEMATICA CONTEMPORANEA, 2017, 13 (02) : 317 - 322
  • [30] Remarks on planar edge-chromatic critical graphs
    Jin, Ligang
    Kang, Yingli
    Steffen, Eckhard
    DISCRETE APPLIED MATHEMATICS, 2016, 200 : 200 - 202
12345