\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf J{\'a}nos Bar{\'a}t and David R. Wood}
%
%
\medskip
\noindent
%
%
{\bf Notes on Nonrepetitive Graph Colouring}
%
%
\vskip 5mm
\noindent
%
%
%
%
A vertex colouring of a graph is {\em 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.

\bye

.