Projects per year
Abstract
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.
Original language | English |
---|---|
Pages (from-to) | 661-686 |
Number of pages | 26 |
Journal | Combinatorica |
Volume | 36 |
Issue number | 6 |
DOIs | |
Publication status | Published - 2016 |
Projects
- 3 Finished
-
Graph colouring via entropy compression
Australian Research Council (ARC)
2/01/14 → 31/12/17
Project: Research
-
Hadwiger's graph colouring conjecture
Wood, D. & Zhou, S.
Australian Research Council (ARC), University of Melbourne
1/01/12 → 30/04/15
Project: Research
-
The Structure and Geometry of Graphs
Australian Research Council (ARC)
1/01/08 → 31/12/13
Project: Research