Article ID Journal Published Year Pages File Type
419474 Discrete Applied Mathematics 2011 15 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 kk such that GG has an acyclic edge coloring using kk colors.In this paper, we prove that every planar graph GG with girth g(G)g(G) and maximum degree ΔΔ has a′(G)=Δa′(G)=Δ if there exists a pair (k,m)∈{(3,11),(4,8),(5,7),(8,6)}(k,m)∈{(3,11),(4,8),(5,7),(8,6)} such that GG satisfies Δ≥kΔ≥k and g(G)≥mg(G)≥m.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , , ,