Skip to Main content Skip to Navigation

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 , Laboratoire I3S - 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.
Document type :
Complete list of metadata
Contributor : Frederic Havet <>
Submitted on : Monday, March 9, 2009 - 10:30:38 AM
Last modification on : Wednesday, October 14, 2020 - 4:23:56 AM
Long-term archiving on: : Friday, October 12, 2012 - 1:10:14 PM


Files produced by the author(s)


  • HAL Id : inria-00366589, version 1


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⟩



Record views


Files downloads