Facial non-repetitive edge-colouring of plane graphsReportar como inadecuado

Facial non-repetitive edge-colouring of plane graphs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

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 2 Institute of Mathematics Kosice, Slovakia

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 π′fG the minimum number of colors of a facial non-repetitive edge-coloring of G. In this article, we show that π′fG≤8 for any plane graph G. We also get better upper bounds for π′fG 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.

Autor: Frédéric Havet - Stanislav Jendrol- - Roman Sotak - Erika Skrabulakova -

Fuente: https://hal.archives-ouvertes.fr/


Documentos relacionados