Facial non-repetitive vertex colouring of some families of 2-connected plane graphs
Jochen Harant, Stanislav Jendrol′ · Common Library Network (Der Gemeinsame Bibliotheksverbund) · 2011
A sequence a 1 a 2 . . .a 2n such that a i = a n+i for all 1 ≤ i ≤ n is called a repetition.A sequence S is called non-repetitive if no subsequence of consecutive terms of S is a repetition.Let G be a graph whose vertices are coloured.A path in G is a called nonrepetitive if the sequence of colours of its vertices is non-repetitive.If G is a plane graph, a facial non-repetitive vertex colouring of G is a vertex colouring such that any facial path (i.e. a path of consecutive vertices on the boundary walk of a face) is non-repetitive.We denote π f (G) the minimum number of colours of a facial non-repetitive vertex colouring of G.In this article, we show that π f (G) ≤ 16 for any plane hamiltonian graph G and π f (G) ≤ 112 for any 2-connected cubic plane graph G.These bounds are improved for some subfamilies of 2-connected plane graphs.All proofs are constructive.