Facial Nonrepetitive Graph Colourings

A facial path is a path of consecutive vertices on the boundary walk of a face of a plane graph G. A nonrepetitive facial colouring of G is a vertex colouring such that the sequence of colours of any facial path is nonrepetitive, and the minimum number of colours required for such a colouring is the facial Thue chromatic number of G.Using a new blocking set technique, we show that the facial Thue chromatic number of an outerplane graph is bounded by 11, and by 7 for outerplane graphs that contain at most one 2-connected component.Furthermore, we show that the facial Thue chromatic number of plane graphs is bounded by twice the facial Thue chromatic number of outerplane graphs, which results in an upper bound of 22 for this parameter, an improvement over the previous bound of 24 by Barat and Czap (Journal of Graph Theory, 2013).