Acyclic edge-colouring of planar graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2009

Acyclic edge-colouring of planar graphs

Résumé

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.
Fichier principal
Vignette du fichier
RR-6876.pdf (279.97 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00367394 , version 1 (11-03-2009)

Identifiants

  • HAL Id : inria-00367394 , version 1

Citer

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

Partager

Gmail Facebook X LinkedIn More