Facial non-repetitive edge-colouring of plane graphs

Frédéric Havet 1 Stanislav Jendrol' 2 Roman Sotak 2 Erika Skrabulakova 2
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 sequence r1, r2, ..., r2n such that ri=rn+ i for all 1≤i≤n is called a repetition. A sequence S is called non-repetitive if no block (i.e. subsequence of consecutive terms of S) is a repetition. Let G be a graph whose edges are colored. A trail is called non-repetitive if the sequence of colors of its edges is non-repetitive. If G is a plane graph, a facial non-repetitive edge-coloring of G is an edge-coloring such that any facial trail (i.e. a trail of consecutive edges on the boundary walk of a face) is non-repetitive. We denote π′f(G) the minimum number of colors of a facial non-repetitive edge-coloring of G. In this article, we show that π′f(G)≤8 for any plane graph G. We also get better upper bounds for π′f(G) in the cases when G is a tree, a plane triangulation, a simple 3-connected plane graph, a hamiltonian plane graph, an outerplanar graph or a Halin graph. The bound 4 for trees is tight.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2011, 66 (1), pp.38--48. <10.1002/jgt.20488>
Liste complète des métadonnées

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

Fichier

nonrepet-soumis.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Frédéric Havet, Stanislav Jendrol', Roman Sotak, Erika Skrabulakova. Facial non-repetitive edge-colouring of plane graphs. Journal of Graph Theory, Wiley, 2011, 66 (1), pp.38--48. <10.1002/jgt.20488>. <inria-00638439>

Partager

Métriques

Consultations de
la notice

144

Téléchargements du document

58