Facial non-repetitive edge-coloring of plane graphs

Facial non-repetitive edge-coloring of plane graphs: "A sequence r1, r2, [hellip], r2n such that ri=rn+ i for all 1[le]i[le]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 [pi][prime]f(G) the minimum number of colors of a facial non-repetitive edge-coloring of G. In this article, we show that [pi][prime]f(G)[le]8 for any plane graph G. We also get better upper bounds for [pi][prime]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. © 2010 Wiley Periodicals, Inc. J Graph Theory"