Name
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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00493-015-3070-6 | Combinatorica |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Vertex (geometry),Loop (graph theory),Vertex (graph theory),Neighbourhood (graph theory),Cycle graph,Entropy compression,Degree (graph theory),Pathwidth,Mathematics | Journal | abs/1112.5524 |
Issue | ISSN | Citations |
6 | 0209-9683 | 7 |
PageRank | References | Authors |
0.50 | 29 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Vida Dujmovic | 1 | 416 | 43.34 |
| Gwenaël Joret | 2 | 196 | 28.64 |
| jakub kozik | 3 | 7 | 0.50 |
| David R. Wood | 4 | 1073 | 96.22 |