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
相关论文
共 18 条
[1]   Acyclic edge colorings of graphs [J].
Alon, N ;
Sudakov, B ;
Zaks, A .
JOURNAL OF GRAPH THEORY, 2001, 37 (03) :157-167
[2]   A PARALLEL ALGORITHMIC VERSION OF THE LOCAL LEMMA [J].
ALON, N .
RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) :367-378
[3]   Optimal acyclic edge-coloring of cubic graphs [J].
Andersen, Lars Dovling ;
Macajova, Edita ;
Mazak, Jan .
JOURNAL OF GRAPH THEORY, 2012, 71 (04) :353-364
[4]   Acyclic edge coloring of subcubic graphs [J].
Basavaraju, Manu ;
Chandran, L. Sunil .
DISCRETE MATHEMATICS, 2008, 308 (24) :6650-6653
[5]   Acyclic Edge Coloring of Triangle-Free Planar Graphs [J].
Basavaraju, Manu ;
Chandran, L. Sunil .
JOURNAL OF GRAPH THEORY, 2012, 71 (04) :365-385
[6]   ACYCLIC EDGE-COLORING OF PLANAR GRAPHS [J].
Basavaraju, Manu ;
Chandran, L. Sunil ;
Cohen, Nathann ;
Havet, Frederic ;
Mueller, Tobias .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) :463-478
[7]   Acyclic Edge Coloring of Graphs with Maximum Degree 4 [J].
Basavaraju, Manu ;
Chandran, L. Sunill .
JOURNAL OF GRAPH THEORY, 2009, 61 (03) :192-209
[8]   Acyclic edge colouring of planar graphs without short cycles [J].
Borowiecki, Mieczyslaw ;
Fiedorowicz, Anna .
DISCRETE MATHEMATICS, 2010, 310 (09) :1445-1455
[9]   About acyclic edge colourings of planar graphs [J].
Fiedorowicz, Anna ;
Haluszczak, Mariusz ;
Narayanan, Narayanan .
INFORMATION PROCESSING LETTERS, 2008, 108 (06) :412-417
[10]   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
12