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 条
  • [1] Acyclic edge colorings of graphs
    Alon, N
    Sudakov, B
    Zaks, A
    [J]. JOURNAL OF GRAPH THEORY, 2001, 37 (03) : 157 - 167
  • [2] A PARALLEL ALGORITHMIC VERSION OF THE LOCAL LEMMA
    ALON, N
    [J]. RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (04) : 367 - 378
  • [3] Optimal acyclic edge-coloring of cubic graphs
    Andersen, Lars Dovling
    Macajova, Edita
    Mazak, Jan
    [J]. JOURNAL OF GRAPH THEORY, 2012, 71 (04) : 353 - 364
  • [4] Basavaraju M., 2010, DISCRETE MATH, V310, P1445
  • [5] ACYCLIC EDGE-COLORING OF PLANAR GRAPHS
    Basavaraju, Manu
    Chandran, L. Sunil
    Cohen, Nathann
    Havet, Frederic
    Mueller, Tobias
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) : 463 - 478
  • [6] Acyclic Edge Coloring of Graphs with Maximum Degree 4
    Basavaraju, Manu
    Chandran, L. Sunill
    [J]. JOURNAL OF GRAPH THEORY, 2009, 61 (03) : 192 - 209
  • [7] ESTIMATION OF SPARSE HESSIAN MATRICES AND GRAPH-COLORING PROBLEMS
    COLEMAN, TF
    MORE, JJ
    [J]. MATHEMATICAL PROGRAMMING, 1984, 28 (03) : 243 - 270
  • [8] THE CYCLIC COLORING PROBLEM AND ESTIMATION OF SPARSE HESSIAN MATRICES
    COLEMAN, TF
    CAI, JY
    [J]. SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02): : 221 - 235
  • [9] Some results on acyclic edge coloring of plane graphs
    Dong, Wei
    Xu, Baogang
    [J]. INFORMATION PROCESSING LETTERS, 2010, 110 (20) : 887 - 892
  • [10] Star coloring of graphs
    Fertin, G
    Raspaud, A
    Reed, B
    [J]. JOURNAL OF GRAPH THEORY, 2004, 47 (03) : 163 - 182
123