HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Acyclic edge-colouring of planar graphs

Nathann Cohen 1 Frédéric Havet 1 Tobias Mueller 2
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A proper edge-colouring with the property that every cycle contains edges of at least three distinct colours is called an {\it acyclic edge-colouring}. The {\it acyclic chromatic index} of a graph $G$, denoted $\chi'_a(G)$ is the minimum $k$ such that $G$ admits an {\it acyclic edge-colouring} with $k$ colours. We conjecture that if $G$ is planar and $\Delta(G)$ is large enough then $\chi'_a(G)=\Delta(G)$. We settle this conjecture for planar graphs with girth at least $5$ and outerplanar graphs. We also show that $\chi'_a(G)\leq \Delta(G) + 25$ for all planar graph $G$, which improves a previous result by Muthu et al.
Document type :
Complete list of metadata

Contributor : Frederic Havet Connect in order to contact the contributor
Submitted on : Wednesday, March 11, 2009 - 10:47:16 AM
Last modification on : Friday, February 4, 2022 - 3:20:12 AM
Long-term archiving on: : Friday, October 12, 2012 - 1:25:24 PM


Files produced by the author(s)


  • HAL Id : inria-00367394, version 1


Nathann Cohen, Frédéric Havet, Tobias Mueller. Acyclic edge-colouring of planar graphs. [Research Report] RR-6876, INRIA. 2009. ⟨inria-00367394⟩



Record views


Files downloads