Nonrepetitive choice number of trees

A nonrepetitive coloring of a path is a coloring of its vertices such that the sequence of colors along the path does not contain two identical, consecutive blocks. The remarkable construction of Thue asserts that 3 colors are enough to color nonrepetitively paths of any length. A nonrepetitive coloring of a graph is a coloring of its vertices such that all simple paths are nonrepetitively colored. Assume that each vertex $v$ of a graph $G$ has assigned a set (list) of colors $L_v$. A coloring is chosen from ${L_v}_{v\in V(G)}$ifthecolorofeach$v$belongsto$L_v$\mathrm{.}TheThuechoicenumberof$G$,denotedby$\pi_l(G)$,istheminimum$k$ such that for any list assignment $\{L_v\}$ of $G$ with each $\mathrm{\mid }{L}_v\mathrm{\mid }\ge k$ there is a nonrepetitive coloring of $G$ chosen from $\{L_v\}$. Alon et al. (2002) proved that ${\pi }_l(G)=O({\mathrm{\Delta }}^2)$ for every graph $G$ with maximum degree at most $\mathrm{\Delta }$. We propose an almost linear bound in $\mathrm{\Delta }$ for trees, namely for any $\text{epsi}>0$ there is a constant $c$ such that $\pi_l(T)\leq c\Delta^{1+\epsi}$foreverytree$T$withmaximumdegree$\Delta$. The only lower bound for trees is given by a recent result of Fiorenzi et al. (2011) that for any $\mathrm{\Delta }$ there is a tree $T$ such that ${\pi }_l(T)=\mathrm{\Omega }(\frac{\log \mathrm{\Delta }}{\log \log \mathrm{\Delta }})$. We also show that if one allows repetitions in a coloring but still forbid 3 identical consecutive blocks of colors on any simple path, then a constant size of the lists allows to color any tree.