Nonrepetitive colorings of trees

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 π(G)π(G). A famous theorem of Thue asserts that π(P)=3π(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 π(T)π(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 π(T)=4π(T)=4 we show that any of them has a sufficiently large subdivision H   such that π(H)=3π(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 Δ+1Δ+1 colors without repetitions on paths.