A coloring of the vertices of a graph G is nonrepetitive if no path in G forms a sequence consisting of two identical blocks. The minimum number of colors needed is the Thue chromatic number, denoted by @p(G). A famous theorem of Thue asserts that @p(P)=3 for any path P with at least four vertices. In this paper we study the Thue chromatic number of trees. In view of the fact that @p(T) is bounded by 4 in this class we aim to describe the 4-chromatic trees. In particular, we study the 4-critical trees which are minimal with respect to this property. Though there are many trees T with @p(T)=4 we show that any of them has a sufficiently large subdivision H such that @p(H)=3. The proof relies on Thue sequences with additional properties involving palindromic words. We also investigate nonrepetitive edge colorings of trees. By a similar argument we prove that any tree has a subdivision which can be edge-colored by at most @D+1 colors without repetitions on paths.
['Boštjan Brešar', 'Jarosław Grytczuk', 'Sandi Klavar', 'S. Niwczyk', 'Iztok Peterin']
Nonrepetitive colorings of trees