2012/07/21 by Jakub Kozik, Kozik, Jakub, Piotr Micek +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1207.5155
openalex publication_date 2012/07/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Lv. A coloring is chosen from \Lv\v∈ V(G) if the color of each v belongs to Lv. The Thue choice number of G, denoted by πl(G), is the minimum k such that for any list assignment \setLv of G with each |Lv|≥ k there is a nonrepetitive coloring of G chosen from \Lv\. Alon et al. (2002) proved that πl(G)=O(Δ2) for every graph G with maximum degree at most Δ. We propose an almost linear bound in Δ for trees, namely for any \epsi>0 there is a constant c such that πl(T)≤ cΔ1+\epsi for every tree T with maximum degree Δ. The only lower bound for trees is given by a recent result of Fiorenzi et al. (2011) that for any Δ there is a tree T such that πl(T)=Ω((logΔ)/(loglogΔ)). 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.