Notes on Nonrepetitive Graph Colouring
| dc.creator | Barát, János | |
| dc.creator | Wood, David R. | |
| dc.date | 2005-09-26 | |
| dc.date | 2007-07-18 | |
| dc.date.accessioned | 2026-07-07T10:01:29Z | |
| dc.date.available | 2026-07-07T10:01:29Z | |
| dc.description | A vertex colouring of a graph is \emph{nonrepetitive on paths} if there is no path $v_1,v_2,...,v_{2t}$ such that v_i and v_{t+i} receive the same colour for all i=1,2,...,t. We determine the maximum density of a graph that admits a k-colouring that is nonrepetitive on paths. We prove that every graph has a subdivision that admits a 4-colouring that is nonrepetitive on paths. The best previous bound was 5. We also study colourings that are nonrepetitive on walks, and provide a conjecture that would imply that every graph with maximum degree $Δ$ has a $f(Δ)$-colouring that is nonrepetitive on walks. We prove that every graph with treewidth k and maximum degree $Δ$ has a $O(kΔ)$-colouring that is nonrepetitive on paths, and a $O(kΔ^3)$-colouring that is nonrepetitive on walks. | |
| dc.identifier | https://arxiv.org/abs/math/0509608 | |
| dc.identifier | http://arxiv.org/abs/math/0509608 | |
| dc.identifier | Electronic J. Combinatorics 15:R99, 2008 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168645 | |
| dc.subject | Combinatorics | |
| dc.subject | 05C15 | |
| dc.title | Notes on Nonrepetitive Graph Colouring | |
| dc.type | text |