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 $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.
Type de document :
Rapport
[Research Report] RR-6873, INRIA. 2009
Liste complète des métadonnées

https://hal.inria.fr/inria-00366589
Contributeur : Frederic Havet <>
Soumis le : lundi 9 mars 2009 - 10:30:38
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : vendredi 12 octobre 2012 - 13:10:14

Fichier

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

Identifiants

  • HAL Id : inria-00366589, version 1

Citation

Frédéric Havet, Stanislav Jendrol', Roman Sotak, Erika Skrabulakova. Facial non-repetitive edge-colouring of plane graphs. [Research Report] RR-6873, INRIA. 2009. 〈inria-00366589〉

Partager

Métriques

Consultations de la notice

348

Téléchargements de fichiers

220