Acyclic edge-colorings of planar graphs
Manu Basavaraju, Sunil L Chandran, Nathann Cohen, Frédéric Havet, Tobias Müller · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · 2011
A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an acyclic edge-colouring.The acyclic chromatic index of a graph G, denoted χ a (G), is the minimum k such that G admits an acyclic edge-colouring with k colours.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 et al. [12].