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), Fiorenzi, Ochem, Ossona de Mendez, and Zhu 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.: 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$.
@article{10_37236_5855,
author = {Adam G\k{a}gol and Gwena\"el Joret and Jakub Kozik and Piotr Micek},
title = {Pathwidth and nonrepetitive list coloring},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {4},
doi = {10.37236/5855},
zbl = {1353.05048},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5855/}
}
TY - JOUR
AU - Adam Gągol
AU - Gwenaël Joret
AU - Jakub Kozik
AU - Piotr Micek
TI - Pathwidth and nonrepetitive list coloring
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/5855/
DO - 10.37236/5855
ID - 10_37236_5855
ER -
%0 Journal Article
%A Adam Gągol
%A Gwenaël Joret
%A Jakub Kozik
%A Piotr Micek
%T Pathwidth and nonrepetitive list coloring
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/5855/
%R 10.37236/5855
%F 10_37236_5855
Adam Gągol; Gwenaël Joret; Jakub Kozik; Piotr Micek. Pathwidth and nonrepetitive list coloring. The electronic journal of combinatorics, Tome 23 (2016) no. 4. doi: 10.37236/5855
