Notes on nonrepetitive graph colouring
The electronic journal of combinatorics, Tome 15 (2008)
A vertex colouring of a graph is nonrepetitive on paths if there is no path $v_1,v_2,\dots,v_{2t}$ such that $v_i$ and $v_{t+i}$ receive the same colour for all $i=1,2,\dots,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 $\Delta$ has a $f(\Delta)$-colouring that is nonrepetitive on walks. We prove that every graph with treewidth $k$ and maximum degree $\Delta$ has a $O(k\Delta)$-colouring that is nonrepetitive on paths, and a $O(k\Delta^3)$-colouring that is nonrepetitive on walks.A corrigendum was added to this paper on Dec 12, 2014.
@article{10_37236_823,
author = {J\'anos Bar\'at and David R. Wood},
title = {Notes on nonrepetitive graph colouring},
journal = {The electronic journal of combinatorics},
year = {2008},
volume = {15},
doi = {10.37236/823},
zbl = {1163.05316},
url = {http://geodesic.mathdoc.fr/articles/10.37236/823/}
}
János Barát; David R. Wood. Notes on nonrepetitive graph colouring. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/823
Cité par Sources :