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].
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2011, 25 (2), pp.436--478
Liste complète des métadonnées


https://hal.inria.fr/inria-00638448
Contributeur : Frederic Havet <>
Soumis le : dimanche 23 octobre 2016 - 16:25:06
Dernière modification le : mardi 25 octobre 2016 - 01:05:07

Fichier

acyclic-final.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00638448, version 1

Collections

Citation

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, Society for Industrial and Applied Mathematics, 2011, 25 (2), pp.436--478. <inria-00638448>

Partager

Métriques

Consultations de
la notice

238

Téléchargements du document

62