Article ID Journal Published Year Pages File Type
419374 Discrete Applied Mathematics 2013 10 Pages PDF
Abstract

A proper edge coloring of a graph GG is acyclic if there is no bichromatic cycle in GG. The acyclic chromatic index of GG, denoted χa′(G), is the least number of colors kk such that GG has an acyclic kk-edge-coloring. In this paper, it is shown that if GG is a planar graph with girth at least 5 and maximum degree ΔΔ, then χa′(G)≤Δ+1. Moreover, if Δ≥9Δ≥9, then χa′(G)=Δ.

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