NONREPETITIVE COLOURING VIA ENTROPY COMPRESSION

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 l-choosable if given lists of at least l colours at each vertex, there is a nonrepetitive colouring such that each vertex is coloured from its own list. It is known that, for some constant c, every graph with maximum degree Delta is c Delta(2)-choosable. 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 graphs with pathwidth theta are nonrepetitively O(theta(2))-colourable.