Notes on Nonrepetitive Graph Colouring

A vertex colouring of a graph is \emph{nonrepetitive on paths} if there is no path $v_1,v_2,\mathrm{.}\mathrm{.}\mathrm{.},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 $\mathrm{\Delta }$ has a $f(\mathrm{\Delta })$-colouring that is nonrepetitive on walks. We prove that every graph with treewidth k and maximum degree $\mathrm{\Delta }$ has a $O(k\mathrm{\Delta })$-colouring that is nonrepetitive on paths, and a $O(k{\mathrm{\Delta }}^3)$-colouring that is nonrepetitive on walks.