Pathwidth and nonrepetitive list coloring (Q504976): Difference between revisions

Summary: A vertex coloring of a graph is nonrepetitive if there is no path in the~graph whose first half receives the same sequence of colors as the second half. While every tree can be nonrepetitively colored with a bounded number of colors (4 colors is enough), \textit{F. Fiorenzi} et al. [Discrete Appl. Math. 159, No. 17, 2045--2049 (2011; Zbl 1239.05064)] recently showed that this does not extend to the list version of the problem, that is, for every \(\ell \geq 1\) there is a tree that is not nonrepetitively \(\ell\)-choosable. In this paper we prove the following positive result, which complements the result of Fiorenzi et al. [loc. cit.]: There exists a function \(f\) such that every tree of pathwidth \(k\) is nonrepetitively \(f(k)\)-choosable. We also show that such a property is specific to trees by constructing a family of pathwidth-2 graphs that are not nonrepetitively \(\ell\)-choosable for any fixed \(\ell\).