Nonrepetitive Colouring via Entropy Compression

Abstract

A vertex colouring of a graph is \emph{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 $\Delta$ is $c{\Delta }^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(k^2)$-colourable.

v4: Minor changes made following helpful comments by the referees

References in corpus (6)

• Acyclic edge-coloring using entropy compression
• Nonrepetitive Colouring via Entropy Compression
• On the facial Thue choice index via entropy compression
• The complexity of nonrepetitive edge coloring of graphs
• On the facial Thue choice number of plane graphs via entropy compression method
• Nonrepetitive colorings of lexicographic product of graphs

Cited by in corpus (22)

• Acyclic edge-coloring using entropy compression
• Nonrepetitive Colouring via Entropy Compression
• Layered Separators in Minor-Closed Graph Classes with Applications
• The Local Cut Lemma
• The Johansson--Molloy Theorem for DP-Coloring
• Planar graphs have bounded nonrepetitive chromatic number
• On the facial Thue choice index via entropy compression
• Progress on the adjacent vertex distinguishing edge colouring conjecture
• Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours
• Pathwidth and nonrepetitive list coloring
• A local lemma via entropy compression
• A general framework for hypergraph colouring
• The Local Action Lemma
• A new bound on the acyclic edge chromatic index
• On the facial Thue choice number of plane graphs via entropy compression method
• Nonrepetitive colorings of lexicographic product of graphs
• Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
• Nonrepetitive graph colouring
• The Thue choice number versus the Thue chromatic number of graphs
• Anagram-free colourings of graph subdivisions
• Total Thue colourings of graphs
• Nonrepetitively 3-colorable subdivisions of graphs with a logarithmic number of subdivisions per edge