{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:09:16Z","timestamp":1758823756563,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>A vertex coloring of a graph is nonrepetitive if there is no path in the\u00a0graph whose first half receives the same sequence of colors as the second half.\u00a0While 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\u00a0$\\ell$-choosable. In this paper we prove the following positive result, which\u00a0complements the result of Fiorenzi et al.: There exists a function $f$ such\u00a0that every tree of pathwidth $k$ is nonrepetitively $f(k)$-choosable. We also\u00a0show 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\u00a0$\\ell$.<\/jats:p>","DOI":"10.37236\/5855","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T19:46:37Z","timestamp":1578685597000},"source":"Crossref","is-referenced-by-count":2,"title":["Pathwidth and Nonrepetitive List Coloring"],"prefix":"10.37236","volume":"23","author":[{"given":"Adam","family":"G\u0105gol","sequence":"first","affiliation":[]},{"given":"Gwena\u00ebl","family":"Joret","sequence":"additional","affiliation":[]},{"given":"Jakub","family":"Kozik","sequence":"additional","affiliation":[]},{"given":"Piotr","family":"Micek","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2016,12,9]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v23i4p40\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v23i4p40\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T05:09:52Z","timestamp":1579237792000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v23i4p40"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,9]]},"references-count":0,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2016,10,14]]}},"URL":"https:\/\/doi.org\/10.37236\/5855","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2016,12,9]]},"article-number":"P4.40"}}