8481 articles  [english version]

inria-00366589, version 1

## Facial non-repetitive edge-colouring of plane graphs

Frederic Havet () 1, Stanislav Jendrol' 2, Roman Sotak 2, Erika Skrabulakova 2

N° RR-6873 (2009)

Résumé : A sequence $r_1,r_2,\dots,r_{2n}$ such that $r_i=r_{n+i}$ for all $1\leq i \leq n$, is called a {\em repetition}. A sequence $S$ is called {\em non-repetitive} if no {\it block} (i.e. subsequence of consecutive terms of $S$) is a repetition. Let $G$ be a graph whose edges are coloured. A trail is called {\em non-repetitive} if the sequence of colours of its edges is non-repetitive. If $G$ is a plane graph, a {\em facial non-repetitive edge-colouring} of $G$ is an edge-colouring such that any {\it facial trail} (i.e. trail of consecutive edges on the boundary walk of a face) is non-repetitive. We denote $\pi'_f(G)$ the minimum number of colours of a facial non-repetitive edge-colouring of $G$. In this paper, we show that $\pi'_f(G)\leq 8$ for any plane graph $G$. We also get better upper bounds for $\pi'_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.

• 1 :  MASCOTTE (INRIA Sophia Antipolis / Laboratoire I3S)
• INRIA – Université Nice Sophia Antipolis [UNS] – CNRS : UMR7271
• 2 :  Institute of Mathematics [Kosice, Slovakia]
• P.J. Safarik University
• Domaine : Informatique/Mathématique discrète
• Référence interne : RR-6873

• inria-00366589, version 1
• oai:hal.inria.fr:inria-00366589
• Contributeur :
• Soumis le : Lundi 9 Mars 2009, 10:30:38
• Dernière modification le : Lundi 9 Mars 2009, 10:35:45