Notes on nonrepetitive graph colouring
The electronic journal of combinatorics, Tome 15 (2008)
Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website
Zbl arXiv EuDML
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.
János Barát; David R. Wood. Notes on nonrepetitive graph colouring. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/823
@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/}
}
Cité par Sources :