# Acyclic edge-colouring of planar graphs

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , 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.
Type de document :
Rapport
[Research Report] RR-6876, INRIA. 2009

https://hal.inria.fr/inria-00367394
Contributeur : Frederic Havet <>
Soumis le : mercredi 11 mars 2009 - 10:47:16
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 13:25:24

### Fichier

RR-6876.pdf
Fichiers produits par l'(les) auteur(s)

### Identifiants

• HAL Id : inria-00367394, version 1

### Citation

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

### Métriques

Consultations de la notice

## 371

Téléchargements de fichiers