We prove that the facial nonrepetitive chromatic number of any outerplanar graph is at most 11 and of any planar graph is at most 22.
Barát and Varjú @cite_33 and K "u ndgen and Pelsmajer @cite_30 independently showed that @math if @math is outerplanar and, more generally, @math if @math has treewidth at most @math . (Barát and Varjú proved the latter bound with @math while K "u ndgen and Pelsmajer proved it with @math .) The bound of @math for @math -trees is tight if @math (trees), but it is not known if it is tight for other values of @math . Even the upper bound of 12 for outerplanar graphs may not be tight, as no outerplanar graph with nonrepetititive chromatic number greater than 7 is known @cite_33 .
@cite_30 @cite_33
2105469400 2141481529
A sequence of the form s"1s"2...s"ms"1s"2...s"m is called a repetition. A vertex-coloring of a graph is called nonrepetitive if none of its paths is repetitively colored. We answer a question of Grytczuk [Thue type problems for graphs, points and numbers, manuscript] by proving that every outerplanar graph has a nonrepetitive 12-coloring. We also show that graphs of tree-width t have nonrepetitive 4^t-colorings. A sequence of symbols a 1 , a 2 … is called square-free if it does not contain a subsequence of consecutive terms of the form x 1 , …, x m , x 1 , …, x m . A century ago Thue showed that there exist arbitrarily long square-free sequences using only three symbols. Sequences can be thought of as colors on the vertices of a path. Following the paper of Alon, Grytczuk, Haluszczak and Riordan, we examine graph colorings for which the color sequence is square-free on any path. The main result is that the vertices of any k -tree have a coloring of this kind using O ( c k ) colors if c > 6. conjectured that a fixed number of colors suffices for any planar graph. We support this conjecture by showing that this number is at most 12 for outerplanar graphs. On the other hand we prove that some outerplanar graphs require at least 7 colors. Using this latter we construct planar graphs, for which at least 10 colors are necessary.