Acyclic Edge-Coloring of Planar Graphs
Manu Basavaraju, L. Sunil Chandran, Nathann Cohen, Frédéric Havet, Tobias Müller · SIAM Journal on Discrete Mathematics · 2011
A proper edge-coloring with the property that every cycle contains edges of at least three distinct colors is called an acyclic edge-coloring. The acyclic chromatic index of a graph [Formula: see text], denoted [Formula: see text], is the minimum [Formula: see text] such that [Formula: see text] admits an acyclic edge-coloring with [Formula: see text] colors. We conjecture that if [Formula: see text] is planar and [Formula: see text] is large enough, then [Formula: see text]. We settle this conjecture for planar graphs with girth at least 5. We also show that [Formula: see text] for all planar [Formula: see text], which improves a previous result by Fiedorowicz, Haluszczak, and Narayan [Inform. Process. Lett., 108 (2008), pp. 412–417].