Nonrepetitive Colouring via Entropy Compression

Details Nonrepetitive Colouring via Entropy Compression Nonrepetitive Colouring via Entropy Compression

2011-12-23

arxiv.org/abs/1112.5524v2

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Nonrepetitive Colouring via Entropy Compression does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Nonrepetitive Colouring via Entropy Compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Nonrepetitive Colouring via Entropy Compression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191973