Article ID Journal Published Year Pages File Type
419440 Discrete Applied Mathematics 2012 13 Pages PDF
Abstract

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. In 1978, it was conjectured that Δ(G)+2Δ(G)+2 colors suffice for an acyclic edge coloring of every graph GG (Fiamčík, 1978 [8]). The conjecture has been verified for several classes of graphs, however, the best known upper bound for as special class as planar graphs are, is Δ+12Δ+12 (Basavaraju and Chandran, 2009 [3]). In this paper, we study simple planar graphs which need only Δ(G)Δ(G) colors for an acyclic edge coloring. We show that a planar graph with girth gg and maximum degree ΔΔ admits such acyclic edge coloring if g≥12g≥12, or g≥8g≥8 and Δ≥4Δ≥4, or g≥7g≥7 and Δ≥5Δ≥5, or g≥6g≥6 and Δ≥6Δ≥6, or g≥5g≥5 and Δ≥10Δ≥10. Our results improve some previously known bounds.

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