Acyclic chromatic indices of planar graphs with girth at least five

被引：0
作者：
Qiaojun Shu
Weifan Wang
机构：
[1] Zhejiang Normal University,Department of Mathematics
来源：
Journal of Combinatorial Optimization | 2012年 / 23卷
关键词：
Acyclic edge coloring; Planar graph; Girth; Maximum degree;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G) of G is the smallest integer k such that G has an acyclic edge coloring using k colors. In this paper, we prove that every planar graph G with girth g(G)≥5 and maximum degree Δ≥12 has a′(G)=Δ.
引用
收藏
页码：140 / 157
页数：17
相关论文
共 35 条
  • [1] Alon N(2002)Algorithmic aspects of acyclic edge coloring colorings Algorithmica 32 611-614
  • [2] Zaks A(1991)Acyclic coloring of graphs Random Struct Algorithms 2 277-288
  • [3] Alon N(2001)Acyclic edge-colorings of graphs J Graph Theory 37 157-167
  • [4] McDiarmid C(2010)Acyclic edge coloring of planar graphs without short cycles Discrete Math 310 1445-1455
  • [5] Reed B(2009)Acyclic edge-colouring of planar graphs. Extended abstract Electron Not Discrete Math 34 417-421
  • [6] Alon N(2008)About acyclic edge colourings of planar graphs Inf Process Lett 108 412-417
  • [7] Sudakov B(2008)Acyclic edge colorings of planar graphs and series-parallel graphs Sci China Ser A 38 1335-1346
  • [8] Zaks A(2010)Acyclic edge chromatic number of outerplanar graphs J Graph Theory 64 22-36
  • [9] Borowiecki M(2006)Improved bounds on acyclic edge coloring Electron Not Discrete Math 19 171-177
  • [10] Fiedorowicz A(2005)The acyclic edge chromatic number of a random J Graph Theory 49 69-74
1234