Thue choosability of trees

A vertex colouring of a graph GG is nonrepetitive   if for any path P=(v1,v2,…,v2r)P=(v1,v2,…,v2r) in GG, the first half is coloured differently from the second half. The Thue choice number   of GG is the least integer ℓℓ such that for every ℓℓ-list assignment LL of GG, there exists a nonrepetitive LL-colouring of GG. We prove that for any positive integer ℓℓ, there is a tree TT with πch(T)>ℓ. On the other hand, it is proved that if G′G′ is a graph of maximum degree ΔΔ, and GG is obtained from G′G′ by attaching to each vertex vv of G′G′ a connected graph of tree-depth at most zz rooted at vv, then πch(G)≤c(Δ,z) for some constant c(Δ,d)c(Δ,d) depending only on ΔΔ and zz.

► We prove that the Thue choice number of trees is unbounded.
► The class of graphs with bounded maximum degree has bounded Thue choice number.
► The class of graphs with bounded tree-depth has bounded Thue choice number.
► A larger class (containing both classes above) of graphs has bounded Thue choice number.