2011/12/31 by Vida Dujmović, Gwenaël Joret, Jakub Kozik +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Discrete mathematics #Geometry #Graph #Limits and Structures in Graph Theory #Mathematical proof #Mathematics #Vertex (graph theory) #cs.DM #math.CO #semigroups and automata theory
paper · pdf · doi:10.1007/s00493-015-3070-6
published as Combinatorica, 36/6:661--686, 2016 · v4: Minor changes made following helpful comments by the referees
arxiv created 2014/06/13 · openalex publication_date 2015/06/24 · arxiv updated 2017/01/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
A vertex colouring of a graph is nonrepetitive if there is no path whose first half receives the same sequence of colours as the second half. A graph is nonrepetitively k-choosable if given lists of at least k colours at each vertex, there is a nonrepetitive colouring such that each vertex is coloured from its own list. It is known that every graph with maximum degree Δ is cΔ2-choosable, for some constant c. We prove this result with c=1 (ignoring lower order terms). We then prove that every subdivision of a graph with sufficiently many division vertices per edge is nonrepetitively 5-choosable. The proofs of both these results are based on the Moser-Tardos entropy-compression method, and a recent extension by Grytczuk, Kozik and Micek for the nonrepetitive choosability of paths. Finally, we prove that every graph with pathwidth k is nonrepetitively O(k2)-colourable.