Article ID Journal Published Year Pages File Type
421230 Discrete Applied Mathematics 2012 13 Pages PDF
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
, , ,