Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
421230 | Discrete Applied Mathematics | 2012 | 13 Pages |
Abstract
An acyclic edge coloring of a graph GG is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index a′(G)a′(G) of GG is the smallest integer kk such that GG has an acyclic edge coloring using kk colors. Fiamčik (1978) [9] and later Alon et al. (2001) [2] conjectured that a′(G)≤Δ+2a′(G)≤Δ+2 for any simple graph GG with maximum degree ΔΔ. In this paper, we confirm this conjecture for planar graphs without 55-cycles.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Qiaojun Shu, Weifan Wang, Yiqiao Wang,