  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
$\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.
