Nonrepetitive colouring via entropy compression

详细信息    查看全文

• 作者：Vida Dujmović ; Gwenaël Joret ; Jakub Kozik ; David R. Wood
• 关键词：Mathematics Subject Classification (2000)05C15
• 刊名：Combinatorica
• 出版年：2016
• 出版时间：December 2016
• 年：2016
• 卷：36
• 期：6
• 页码：661-686
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Combinatorics; Mathematics, general;
• 出版者：Springer Berlin Heidelberg
• ISSN：1439-6912
• 卷排序：36

文摘

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 ℓ-choosable if given lists of at least ℓ 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 Δis cΔ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 θ are nonrepetitively O(θ2)-colourable.