Skip to Main content Skip to Navigation
New interface
Journal articles

Acyclic edge-colouring of planar graphs

Abstract : 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 G, denoted χa′(G), is the minimum k such that G admits an acyclic edge-coloring with k colors. We conjecture that if G is planar and Δ(G) is large enough, then χa′(G) = Δ(G). We settle this conjecture for planar graphs with girth at least 5. We also show that χa′(G) ≤ Δ(G)+12 for all planar G, which improves a previous result by Fiedorowicz, Haluszczak, and Narayan [Inform. Process. Lett., 108 (2008), pp. 412-417].
Document type :
Journal articles
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Sunday, October 23, 2016 - 4:25:06 PM
Last modification on : Friday, November 4, 2022 - 3:02:54 PM


Files produced by the author(s)


  • HAL Id : inria-00638448, version 1



Manu Basavaraju, L. Sunil Chandran, Nathann Cohen, Frédéric Havet, Tobias Müller. Acyclic edge-colouring of planar graphs. SIAM Journal on Discrete Mathematics, 2011, 25 (2), pp.436--478. ⟨inria-00638448⟩



Record views


Files downloads