\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{R99}{15}{2008}

\usepackage{amsthm,amsmath,graphicx,amsfonts}
\usepackage[sort&compress,numbers]{natbib}
\allowdisplaybreaks
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{open}[theorem]{Open Problem}

\newcommand{\thm}[2]{\begin{theorem}\label{thm:#1}#2\end{theorem}}
\newcommand{\con}[2]{\begin{conjecture}\label{con:#1}#2\end{conjecture}}
\newcommand{\cor}[2]{\begin{corollary}\label{cor:#1}#2\end{corollary}}
\newcommand{\lem}[3][]{\begin{lemma}[#1]\label{lem:#2}#3\end{lemma}}
\newcommand{\opn}[2]{\begin{open}\label{open:#1}#2\end{open}}
\newcommand{\prop}[2]{\begin{proposition}\label{prop:#1}#2\end{proposition}}
\newcommand{\prf}[2][Proof]{\begin{proof}[#1]#2\end{proof}}
\newcommand{\sect}[2]{\section{#2}\label{sec:#1}}

\newcommand{\eqnref}[1]{Equation~\eqref{#1}}
\newcommand{\corref}[1]{Corollary~\ref{cor:#1}}
\newcommand{\conref}[1]{Conjecture~\ref{con:#1}}
\newcommand{\propref}[1]{Proposition~\ref{prop:#1}}
\newcommand{\openref}[1]{Open Problem~\ref{open:#1}}
\newcommand{\thmref}[1]{Theorem~\ref{thm:#1}}
\newcommand{\lemref}[1]{Lemma~\ref{lem:#1}}
\newcommand{\twolemref}[2]{Lemmas~\ref{lem:#1} and \ref{lem:#2}}
\newcommand{\threelemref}[3]{Lemmas~\ref{lem:#1}, \ref{lem:#2} and \ref{lem:#3}}
\newcommand{\secref}[1]{Section~\ref{sec:#1}}

%\newcommand{\comment}[1]{\medskip\noindent\framebox{\parbox{\textwidth-2mm}{#1}}\medskip}

\newcommand{\half}{\ensuremath{\protect\tfrac{1}{2}}}
\newcommand{\eighth}{\ensuremath{\protect\tfrac{1}{8}}}
\newcommand{\ninth}{\ensuremath{\protect\tfrac{1}{9}}}
\newcommand{\bracket}[1]{\ensuremath{\protect\left(#1\right)}}
\newcommand{\FLOOR}[1]{\ensuremath{\protect\left\lfloor#1\right\rfloor}}
\newcommand{\floor}[1]{\ensuremath{\protect\lfloor#1\rfloor}}
\newcommand{\ceil}[1]{\ensuremath{\protect\lceil#1\rceil}}
\newcommand{\Oh}[1]{\ensuremath{\protect\mathcal{O}(#1)}}
\newcommand{\e}{\ensuremath{\mathbf{e}}}
\newcommand{\A}{\ensuremath{\mathcal{A}}}
\newcommand{\D}{\ensuremath{\mathcal{D}}}
\newcommand{\Z}{\ensuremath{\mathbb{Z}}}
\newcommand{\Prob}{\textbf{\textup{P}}}

\title{\bf Notes on Nonrepetitive Graph Colouring}

\date{\dateline{Jul 18, 2007}{Jul 23, 2008}{Jul 28, 2008}\\
\small Mathematics Subject Classification: 05C15 (coloring of graphs and hypergraphs)}
   
\author{J{\'a}nos~Bar{\'a}t\thanks{Research supported by a Marie Curie
Fellowship of the European Community under contract number HPMF-CT-2002-01868
and by the OTKA Grant T.49398.}\\
\small Department of Mathematics\\[-0.8ex]
\small University of Szeged\\[-0.8ex]
\small Szeged, Hungary\\[-0.8ex]
\small \texttt{barat@math.u-szeged.hu}
\and
David~R.~Wood\thanks{Research supported by a QEII Research Fellowship. Research conducted at the Universitat Polit\`ecnica de Catalunya (Barcelona, Spain), where supported by a Marie Curie Fellowship of the European Community under contract MEIF-CT-2006-023865, and by the projects MEC MTM2006-01267 and DURSI 2005SGR00692.}\\
\small Department of Mathematics and Statistics\\[-0.8ex]
\small The University of Melbourne\\[-0.8ex]
\small Melbourne, Australia \\[-0.8ex]
\small \texttt{D.Wood@ms.unimelb.edu.au}}

%\small Departament de Matem\'atica Aplicada II\\[-0.8ex]
%\small Universitat Polit\`ecnica de Catalunya\\[-0.8ex]
%\small Barcelona, Spain\\[-0.8ex]
%\small \texttt{david.wood@upc.es}}

\begin{document}
\maketitle

\begin{abstract}
A vertex colouring of a graph is \emph{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.
\end{abstract}

\sect{Introduction}{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We consider simple, finite, undirected graphs $G$ with vertex set $V(G)$, edge set $E(G)$, and maximum degree $\Delta(G)$. Let $[t]:=\{1,2,\dots,t\}$. A \emph{walk} in $G$ is a sequence $v_1,v_2,\dots,v_t$ of vertices of $G$, such that $v_iv_{i+1}\in E(G)$ for all $i\in[t-1]$. A $k$-\emph{colouring} of $G$ is a function $f$ that assigns one of $k$ colours to each vertex of $G$. A walk $v_1,v_2,\dots,v_{2t}$ is \emph{repetitively} coloured by $f$ if $f(v_i)=f(v_{t+i})$ for all $i\in[t]$. A walk $v_1,v_2,\dots,v_{2t}$ is \emph{boring} if $v_i=v_{t+i}$ for all $i\in[t]$. Of course, a boring walk is repetitively coloured by every colouring. We say a colouring $f$ is \emph{nonrepetitive on walks} (or \emph{walk-nonrepetitive}) if the only walks that are repetitively coloured by $f$ are boring. Let $\sigma(G)$ denote the minimum $k$ such that $G$ has a $k$-colouring that is nonrepetitive on walks. 

A walk $v_1,v_2,\dots,v_t$ is a \emph{path} if $v_i\ne v_j$ for all distinct $i,j\in[t]$. A colouring $f$ is \emph{nonrepetitive on paths} (or \emph{path-nonrepetitive}) if no path of $G$ is repetitively coloured by $f$. Let $\pi(G)$ denote the minimum $k$ such that $G$ has a $k$-colouring that is nonrepetitive on paths. Observe that a colouring that is path-nonrepetitive is \emph{proper}, in the sense that adjacent vertices receive distinct colours. Moreover, a path-nonrepetitive colouring has no $2$-coloured $P_4$ (a path on four vertices). A proper colouring with no $2$-coloured $P_4$ is called a \emph{star colouring} since each bichromatic subgraph is a star forest; see \citep{Albertson-EJC04, Grunbaum73, FRR-JGT04, Borodin-DM79, NesOdM-03, Wood-DMTCS05}. The \emph{star chromatic number} $\chi_{\text{st}}(G)$ is the minimum number of colours in a proper colouring of $G$ with no $2$-coloured $P_4$. Thus
\begin{equation}
\chi(G)\leq\chi_{\text{st}}(G)\leq\pi(G)\leq\sigma(G).
\end{equation}

Path-nonrepetitive colourings are widely studied \citep{Grytczuk-PatternAvoidance, AGHR-RSA02, BreakingRhythm, BV-NonRepVertex, BK-AC04, Grytczuk-EJC02, CG-ENDM07, BGKNP-NonRepTree-DM07, Currie-TCS05, AG-EuroComb05, Manin, KP}; see the surveys by \citet{ThueProblems,Gryczuk-IJMMS07}. Nonrepetitive edge colourings have also been considered \citep{BV-NonRepEdge, AGHR-RSA02}.

The seminal result in this field is by \citet{Thue06}, who in 1906 proved\footnote{The nonrepetitive $3$-colouring of $P_n$ by \citet{Thue06} is obtained as follows. Given a nonrepetitive sequence over $\{1,2,3\}$, replace each $1$ by the sequence $12312$,  replace each $2$ by the sequence $131232$, and replace each $3$ by the sequence $1323132$. \citet{Thue06} proved that the new sequence is nonrepetitive. Thus arbitrarily long paths can be nonrepetitively $3$-coloured.} that the $n$-vertex path $P_n$ satisfies
\begin{equation}
\label{Path}
\pi(P_n)=%\sigma(P_n)=
\begin{cases}
n	&\text{ if }n\leq 2,\\
3	&\text{ otherwise.}
\end{cases}
\end{equation}
A result by \citet{KP} (see \lemref{PathLoop}) implies 
\begin{equation}
\sigma(P_n)\leq 4\enspace.
\end{equation}
\citet{Currie-EJC02} proved that the $n$-vertex cycle $C_n$ satisfies
\begin{equation}
\label{Cycle}
\pi(C_n)=
\begin{cases}
4	&\text{if }n\in\{5,7,9,10,14,17\},\\
3	&\text{otherwise.}
\end{cases}
\end{equation}

Let $\pi(\Delta)$ and $\sigma(\Delta)$ denote the maximum of $\pi(G)$ and $\sigma(G)$, taken over all graphs $G$ with maximum degree $\Delta(G)\leq\Delta$. Now $\pi(2)=4$ by \eqref{Path} and \eqref{Cycle}. In general, \citet{AGHR-RSA02} proved that 
\begin{equation}
\label{PiDegree}
\frac{\alpha\Delta^2}{\log\Delta}\leq\pi(\Delta)\leq\beta\Delta^2,
\end{equation}
for some constants $\alpha$ and $\beta$. The upper bound was proved using the 
Lov\'{a}sz Local Lemma, and the lower bound is attained by a random graph. 

In \secref{Bounded} we study whether $\sigma(\Delta)$ is finite, and provide a natural conjecture that would imply an affirmative answer. 

In \secref{Treewidth} we study path- and walk-nonrepetitive colourings of graphs of bounded treewidth\footnote{The \emph{treewidth} of a graph $G$ can be defined to be the minimum integer $k$ such that $G$ is a subgraph of a chordal graph with no clique on $k+2$ vertices. Treewidth is an important graph parameter, especially in structural graph theory and algorithmic graph theory; see the surveys \citep{Bodlaender-TCS98, Reed-AlgoTreeWidth03}.}. \citet{KP} and \citet{BV-NonRepVertex} independently proved that graphs of bounded treewidth have bounded $\pi$. The best bound is due to \citet{KP} who proved that $\pi(G)\leq4^k$ for every graph $G$ with treewidth at most $k$. Whether there is a polynomial bound on $\pi$ for graphs of treewidth $k$ is an open question. 
We answer this problem in the affirmative under the additional assumption of bounded degree. In particular, we prove a \Oh{k\Delta} upper bound on $\pi$, and a \Oh{k\Delta^3} upper bound on $\sigma$.

%\comment{DW: My Guess is that there is $k$-tree $G$ with $\pi(G)\geq c^k$ for some constant $c>1$.}

In \secref{Subdivision} we will prove that every graph has a subdivision that admits a path-nonrepetitive $4$-colouring; the best previous bound was $5$. 
In \secref{Density} we determine the maximum density of a graph that admits a path-nonrepetitive $k$-colouring, and prove bounds on the maximum density for walk-nonrepetitive $k$-colourings. 

%Grytczuk-Berge, AG-ICGT05, 

\sect{Bounded}{\boldmath Is $\sigma(\Delta)$ bounded?}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Consider the following elementary lower bound on $\sigma$, where $G^2$ is the \emph{square} graph of $G$. That is, $V(G^2)=V(G)$, and $vw\in E(G^2)$ if and only if the distance between $v$ and $w$ in $G$ is at most $2$. A proper colouring of $G^2$ is called a \emph{distance-$2$} colouring of $G$.

\lem{WalkLowerBound}{Every walk-nonrepetitive colouring of a graph $G$ is distance-$2$. Thus $\sigma(G)\geq\chi(G^2)\geq\Delta(G)+1$.}

\prf{Consider a walk-nonrepetitive colouring of $G$. Adjacent vertices $v$ and $w$ receive distinct colours, as otherwise $v,w$ would be a repetitively coloured path. If $u,v,w$ is a path, and $u$ and $w$ receive the same colour, then the non-boring walk $u,v,w,v$ is repetitively coloured. Thus vertices at distance at most $2$ receive distinct colours. Hence $\sigma(G)\geq\chi(G^2)$. In a distance-$2$ colouring, each vertex and its neighbours all receive distinct colours. Thus $\chi(G^2)\geq\Delta(G)+1$.}

Hence $\Delta(G)$ is a lower bound on $\sigma(G)$. Whether high degree is the only obstruction for bounded $\sigma$ is an open problem.

%\opn{sigmapi}{Is there a function $f$ such that $\sigma(G)\leq f(\pi(G),\Delta(G))$ for every graph $G$?}

\opn{Degree}{Is there a function $f$ such that $\sigma(\Delta)\leq f(\Delta)$?}

%By \eqnref{PiDegree}, a positive answer to \openref{sigmapi} would imply  a positive answer to \openref{Degree}.

First we answer \openref{Degree} in the affirmative for $\Delta=2$.
The following lemma will be useful.

\lem{useful}{Fix a distance-$2$ colouring of a graph $G$. If  $W=(v_1,v_2,\dots,v_{2t})$ is a repetitively coloured non-boring walk in $G$, then $v_i\ne v_{t+i}$ for all $i\in[t]$.}

\prf{Suppose on the contrary that $v_i=v_{t+i}$ for some $i\in[t-1]$. Since $W$ is repetitively coloured, $c(v_{i+1})=c(v_{t+i+1})$. Each neighbour of $v_i$ receives a distinct colour. Thus $v_{i+1}=v_{t+i+1}$. By induction, $v_j=v_{t+j}$ for all $j\in[i,t]$. By the same argument, $v_j=v_{t+j}$ for all $j\in[1,i]$. Thus 
$W$ is boring, which is the desired contradiction.}

\prop{PathCycle}{$\sigma(2)\leq 5$.}

\prf{A result by \citet{KP} implies that $\sigma(P_n)\leq 4$ (see \lemref{PathLoop}).
Thus it suffices to prove that $\sigma(C_n)\leq 5$. 
Fix a walk-nonrepetitive $4$-colouring of the path $(v_1,v_2,\dots,v_{2n-4})$.
Thus for some $i\in[1,n-2]$, the vertices $v_i$ and $v_{n+i-2}$ receive distinct colours.
Create a cycle $C_n$ from the sub-path $v_i,v_{i+1},\dots,v_{n+i-2}$ by adding one vertex $x$ adjacent to $v_i$ and $v_{n+i-2}$. 
Colour $x$ with a fifth colour.
Observe that since $v_i$ and $v_{n+i-2}$ receive distinct colours, 
the colouring of $C_n$ is distance-$2$.
Suppose on the contrary that $C_n$ has a repetitively coloured walk $W=y_1,y_2,\dots,y_{2t}$. 
If $x$ is not in $W$, then $W$ is a repetitively coloured walk in the starting path, which is a contradiction.
Thus $x=y_i$ for some $i\in[t]$ (with loss of generality, by considering the reverse of $W$). 
Since $x$ is the only vertex receiving the fifth colour 
and $W$ is repetitive, $x=y_{t+i}$.
By \lemref{useful}, $W$ is boring.
Hence the $5$-colouring of $C_n$ is walk-nonrepetitive.}

Below we propose a conjecture that would imply a positive answer to \openref{Degree}. First consider the following lemma which is a slight generalisation of a result by \citet{BV-NonRepEdge}. A walk $v_1,v_2,\dots,v_t$ has \emph{length} $t$ and \emph{order} $|\{v_i:1\leq i\leq t\}|$. That is, the order is the number of distinct vertices in the walk.

\prop{SmallWalks}{Suppose that in some coloured graph, there is a repetitively coloured non-boring walk. Then there is a repetitively coloured non-boring walk of order $k$ and length at most $2k^2$.}

\prf{Let $k$ be the minimum order of a repetitively coloured non-boring walk. 
Let $W=v_1,v_2,\dots,v_{2t}$ be a repetitively coloured non-boring walk of order $k$ and with $t$ minimum. If $2t\leq2k^2$, then we are done. Now assume that $t>k^2$. By the pigeonhole principle, there is a vertex $x$ that appears at least $k+1$ times in $v_1,v_2,\dots,v_t$. Thus there is a vertex $y$ that appears at least twice in the set $\{v_{t+i}:v_i=x,i\in[t]\}$. As illustrated in Figure~\ref{fig:Shorten}, $W=AxBxCA'yB'yC'$ for some walks $A,B,C,A',B',C'$ with $|A|=|A'|$, $|B|=|B'|$, and $|C|=|C'|$. Consider the walk $U:=AxCA'yC'$. If $U$ is not boring, then it is a repetitively coloured non-boring walk of order at most $k$ and length less than $2t$, which contradicts the minimality of $W$. Otherwise $U$ is boring, implying $x=y$, $A=A'$, and $C=C'$. Thus $B\ne B'$ since $W$ is not boring, implying $xBxB'$ is a repetitively coloured non-boring walk of order at most $k$ and length less than $2t$, which contradicts the minimality of $W$.}

\begin{figure}[!ht]
\begin{center}
\includegraphics{r99Shorten.eps}
\caption{Illustration for the proof of \propref{SmallWalks}.}
\label{fig:Shorten} 
\end{center}
\end{figure}

We conjecture the following strengthening of \propref{SmallWalks}.

%\con{SmallWalks}{There exists a function $h$ such that for every graph $G$ and for every path-nonrepetitive distance-$2$ colouring of $G$ with $c$ colours, if $G$ contains a repetitively coloured non-boring walk, then $G$ contains a repetitively coloured non-boring walk of order $k$ and length at most $h(c)\cdot k$.}

\con{SmallWalks}{Let $G$ be a graph. Consider a path-nonrepetitive distance-$2$ colouring of $G$ with $c$ colours, such that $G$ contains a repetitively coloured non-boring walk. Then $G$ contains a repetitively coloured non-boring walk of order $k$ and length at most $h(c)\cdot k$, for some function $h$ that only depends on $c$.}

\thm{sigmaBounded}{If \conref{SmallWalks} is true, then there is a 
function $f$ for which $\sigma(\Delta)\leq f(\Delta)$. That is, every graph $G$ has a walk-nonrepetitive colouring with $f(\Delta(G))$ colours.}

\thmref{sigmaBounded} is proved using the Lov\'{a}sz Local Lemma \citep{EL75}. 

\lem[\citep{EL75}]{LLL}{Let $\A=\A_1\cup\A_2\cup\dots\cup\A_r$ be a partition of a set of `bad' events \A. Suppose that there are sets of real numbers $\{p_i\in[0,1):i\in[r]\}$, $\{x_i\in[0,1):i\in[r]\}$, and $\{D_{ij}\geq0:i,j\in[r]\}$ such that the following conditions are satisfied by every event $A\in\A_i$:
\begin{itemize}
\item the probability $\displaystyle
\Prob(A)\;\leq\;p_i\;\leq\;x_i\cdot\!\!\!\!\prod_{j=1}^r(1-x_j)^{D_{ij}}\enspace$, and
\item $A$ is mutually independent of $\A\setminus(\{A\}\cup\D_A)$, for some $\D_A\subseteq\A$ with $|\D_A\cap\A_j|\leq D_{ij}$ for all $j\in[r]$. 
\end{itemize}
Then 
\begin{equation*}
\Prob\bracket{\bigwedge_{A\in\A} \overline{A}}\;\geq\;\prod_{i=1}^r(1-x_i)^{|\A_i|}\;>\;0\enspace.
\end{equation*}
That is, with positive probability, no event in $\A$ occurs.}

\prf[Proof of \thmref{sigmaBounded}]{Let $f_1$ be a path-nonrepetitive colouring of $G$ with $\pi(G)$ colours. Let $f_2$ be a distance-$2$ colouring of $G$ with $\chi(G^2)$ colours. Note that $\pi(G)\leq \beta\Delta^2$ for some constant $\beta$ by Equation~\eqref{PiDegree}, and $\chi(G^2)\leq\Delta(G^2)+1\leq\Delta^2+1$ by a greedy colouring of $G^2$. Hence $f_1$ and $f_2$ together define a path-nonrepetitive distance-$2$ colouring of $G$. The number of colours $\pi(G)\cdot\chi(G^2)$ is bounded by a function solely of $\Delta(G)$. Consider this initial colouring to be fixed. Let $c$ be a positive integer to be specified later. For each vertex $v$ of $G$, choose a third colour $f_3(v)\in[c]$ independently and randomly. Let $f$ be the colouring defined by $f(v)=(f_1(v),f_2(v),f_3(v))$ for all vertices $v$.

Let $h:=h(\pi(G)\cdot\chi(G^2))$ from \conref{SmallWalks}. A non-boring walk $v_1,v_2,\dots,v_{2t}$ of order $i$ is \emph{interesting} if its length $2t\leq hi$, and $f_1(v_j)=f_1(v_{t+j})$ and $f_2(v_j)=f_2(v_{t+j})$ for all $j\in[t]$. For each interesting walk $W$, let $A_W$ be the event that $W$ is repetitively coloured by $f$. Let $\A_i$ be the set of events $A_W$, where $W$ is an interesting walk of order $i$. Let $\A=\bigcup_i\A_i$. 

We will apply \lemref{LLL} to prove that, with positive probability, no event $A_W$ occurs. This will imply that there exists a colouring $f_3$ such that no interesting walk is repetitively coloured by $f$. A non-boring non-interesting walk $v_1,v_2,\dots,v_{2t}$ of order $i$ satisfies (a) $2t>hi$, or (b) $f_1(v_j)\ne f_1(v_{t+j})$ or $f_2(v_j)\ne f_2(v_{t+j})$ for some $j\in[t]$. In case (a), by the assumed truth of \conref{SmallWalks}, $W$ is not repetitively coloured by $f$. In case (b), $f(v_j)\ne f(v_{t+j})$ and $W$ is not repetitively coloured by $f$. Thus no non-boring walk is repetitively coloured by $f$, as desired.

Consider an interesting walk $W=v_1,v_2,\dots,v_{2t}$ of order $i$. 

We claim that $v_\ell\ne v_{t+\ell}$ for all $\ell\in[t]$. 
Suppose on the contrary that $v_\ell=v_{t+\ell}$ for some $\ell\in[t]$. 
Since $W$ is not boring, $v_j\ne v_{t+j}$ for some $j\in[t]$. 
Thus $v_j=v_{t+j}$ and $v_{j+1}\ne v_{t+j+1}$  for some $j\in[t]$ (where $v_{t+t+1}$ means $v_1$). Since $W$ is interesting, $f_2(v_{j+1})=f_2(v_{t+j+1})$, which is a contradiction since $v_{j+1}$ and $v_{t+j+1}$ have a common neighbour $v_j$ ($=v_{t+j}$). Thus $v_j\ne v_{t+j}$ for all $j\in[t]$, as claimed. 

This claim implies that for each of the $i$ vertices $x$ in $W$, there is at least one other vertex $y$ in $W$, such that $f_3(x)=f_3(y)$ must hold for $W$ to be repetitively coloured. Hence at most $c^{i/2}$ of the $c^i$ possible colourings of $W$ under $f_3$, lead to repetitive colourings of $W$ under $f$. Thus the probability $\Prob(A_W)\leq p_i:=c^{-i/2}$, and 
\lemref{LLL} can be applied as long as
\begin{equation}
\label{eqn:One}
c^{-i/2}\;\leq\;x_i\cdot\!\!\!\!\prod_j(1-x_j)^{D_{ij}}\enspace,
\end{equation}

Every vertex is in at most $hj\Delta^{hj}$ interesting walks of order $j$. Thus an interesting walk of order $i$ shares a vertex with at most $hij\Delta^{hj}$ interesting walks of order $j$. Thus we can take $D_{ij}:=hij\Delta^{hj}$. 
Define $x_i:=(2\Delta^{h})^{-i}$. Note that $x_i\leq\half$. So $1-x_i\geq\e^{-2x_i}$. Thus to prove \eqref{eqn:One} it suffices to prove that 
\begin{align*}
&
c^{-i/2}
\;\leq\;
x_i\cdot\!\!\!\!\prod_j\e^{-2x_jD_{ij}}\enspace,\\
\Longleftarrow\;\;\;&
c^{-i/2}
\;\leq\;
(2\Delta^{h})^{-i}\cdot\!\!\!\!\prod_j\e^{-2(2\Delta^{h})^{-j}hij\Delta^{hj}}\enspace,\\
\Longleftarrow\;\;\;&
c^{-1/2}
\;\leq\;
(2\Delta^{h})^{-1}\cdot\!\!\!\!\prod_j\e^{-2(2)^{-j}hj}\enspace,\\
\Longleftarrow\;\;\;&
c^{-1/2}
\;\leq\;
(2\Delta^{h})^{-1}\e^{-2h\sum_jj2^{-j}}\enspace,\\
\Longleftarrow\;\;\;&
c^{-1/2}
\;\leq\;
(2\Delta^{h})^{-1}\e^{-4h}\enspace,\\
\Longleftarrow\;\;\;&
%c^{1/2}
%&\;\geq\;
%2(\e^4\Delta)^h\enspace,\\
c\;\;\;\;\;\;\;\;\geq\;
4(\e^4\Delta)^{2h}\enspace.
\end{align*}
Choose $c$ to be the minimum integer that satisfies this inequality, and the lemma is applicable. We obtain a $c$-colouring $f_3$ of $G$ such that $f$ is nonrepetitive on walks. The number of colours in $f$ is at most $h\ceil{4(\e^4\Delta)^{2h}}$, which is a function solely of $\Delta$.}

\sect{Treewidth}{Trees and Treewidth}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We start this section by considering walk-nonrepetitive colourings of trees.

\thm{Trees}{Let $T$ be a tree. A colouring $c$ of $T$ is walk-nonrepetitive if and only if $c$ is path-nonrepetitive and distance-$2$.}

\prf{For every graph, every walk-nonrepetitive colouring is path-nonrepetitive (by definition) and distance-$2$ (by \lemref{WalkLowerBound}). 

Now fix a path-nonrepetitive distance-$2$ colouring $c$ of $T$. Suppose on the contrary that $T$ has a repetitively coloured non-boring walk. Let $W=(v_1,v_2,\dots,v_{2t})$ be a repetitively coloured non-boring walk in $T$ of minimum length. Some vertex is repeated in $W$, as otherwise $W$ would be a repetitively coloured path. By considering the reverse of $W$, without loss of generality, $v_i=v_j$ for some $i\in[1,t-1]$ and $j\in[i+2,2t]$. Choose $i$ and $j$ to minimise $j-i$. Thus $v_i$ is not in the sub-walk $(v_{i+1},v_{i+2},\dots,v_{j-1})$. Since $T$ is a tree, $v_{i+1}=v_{j-1}$. Thus $i+1=j-1$, as otherwise $j-i$ is not minimised. That is, $v_i=v_{i+2}$. Assuming $i\neq t-1$, since $W$ is repetitively coloured, $c(v_{t+i})=c(v_{t+i+2})$, which implies that $v_{t+i}=v_{t+i+2}$ because $c$ is a distance-$2$ colouring. Thus, even if $i=t-1$, deleting the vertices $v_{i},v_{i+1},v_{t+i},v_{t+i+1}$ from $W$, gives a walk $(v_1,v_2,\dots,v_{i-1},v_{i+2},\dots,v_{t+i-1},v_{t+i+2},\dots,v_{2t})$ that is also repetitively coloured. This contradicts the minimality of the length of $W$.}

Note that \thmref{Trees} implies that \conref{SmallWalks} is vacuously true for trees.
Also, since every tree $T$ has a path-nonrepetitive $4$-colouring \citep{KP} and a distance-$2$ $(\Delta(T)+1)$-colouring, \thmref{Trees} implies the following result, where the lower bound is \lemref{WalkLowerBound}.

\cor{WalkTree}{Every tree $T$ satisfies $\Delta(T)+1\leq\sigma(T)\leq 4(\Delta(T)+1)$.}

%The \emph{treewidth} of a graph $G$ can be defined to be the minimum integer $k$ such that $G$ is a subgraph of a chordal graph with no clique on $k+2$ vertices. Treewidth is an important graph parameter, especially in structural graph theory and algorithmic graph theory; see the surveys \citep{Bodlaender-TCS98, Reed-AlgoTreeWidth03}. 

%\citet{KP} and \citet{BV-NonRepVertex} independently proved that graphs of bounded treewidth have bounded $\pi$. The best bound is due to \citet{KP} who proved that $\pi(G)\leq4^k$ for every graph $G$ with treewidth at most $k$. Whether there is a polynomial bound on $\pi$ for graphs of treewidth $k$ is an open question. 

In the remainder of this section we prove the following polynomial upper bounds on $\pi$ and $\sigma$ in terms of the treewidth and maximum degree of a graph.

\thm{TreewidthDegree}{Every graph $G$ with treewidth $k$ and maximum degree $\Delta\geq1$ satisfies $\pi(G)\leq ck\Delta$ and $\sigma(G)\leq ck\Delta^3$ for some constant $c$.}

We prove \thmref{TreewidthDegree} by a series of lemmas. The first is by \citet{KP}\footnote{The $4$-colouring in \lemref{PathLoop} is obtained as follows. Given a nonrepetitive sequence on $\{1,2,3\}$, insert the symbol $4$ between consecutive block of length two. For example, from the sequence $123132123$ we obtain $1243143241243$.}. 

\lem[\citep{KP}]{PathLoop}{Let $P^+$ be the pseudograph obtained from a path $P$ by adding a loop at each vertex. Then $\sigma(P^+)\leq 4$.}

%\comment{DW: The proof of \lemref{PathLoop} implies that if a path $P$ is coloured so that it is nonrepetitive on paths and is a proper colouring of $P^2$, then it is nonrepetitive on walks. For what other graphs can we generalise this statement, possibly with other conditions on the colouring?
%JB: I think the idea is that a proper  coloring of $G^2$ kills the walks of length 3 on 3  vertices. I will think about it.}

Now we introduce some definitions by \citet{KP}. A \emph{levelling} of a graph $G$ is a function $\lambda:V(G)\rightarrow\Z$ such that $|\lambda(v)-\lambda(w)|\leq1$ for every edge $vw\in E(G)$. Let $G_{\lambda=k}$ and $G_{\lambda>k}$ denote the subgraphs of $G$ respectively induced by $\{v\in V(G):\lambda(v)=k\}$ and $\{v\in V(G):\lambda(v)>k\}$. The \emph{$k$-shadow} of a subgraph $H$ of $G$ is the set of vertices in $G_{\lambda=k}$ adjacent to some vertex in $H$. A levelling $\lambda$ is \emph{shadow-complete} if the $k$-shadow of every component of $G_{\lambda>k}$ induces a clique. \citet{KP} proved the following lemma for repetitively coloured paths. We show that the same proof works for repetitively coloured walks. 

\lem{LevellingWalks}{For every levelling $\lambda$ of a graph $G$, there is a $4$-colouring of $G$, such that every repetitively coloured walk $v_1,v_2,\dots,v_{2t}$ satisfies $\lambda(v_j)=\lambda(v_{t+j})$ for all $j\in[t]$.}

\prf{The levelling $\lambda$ can be thought of as a homomorphism from $G$ into $P^+$, for some path $P$. By \lemref{PathLoop}, $P^+$ has a 4-colouring that is nonrepetitive on walks. Colour each vertex $v$ of $G$ by the colour assigned to $\lambda(v)$ (thought of as a vertex of $P^+$). Suppose $v_1,v_2,\dots,v_{2t}$ is a repetitively coloured walk in $G$. Thus $\lambda(v_1),\lambda(v_2),\dots,\lambda(v_{2t})$ is a repetitively coloured walk in $P^+$. Since the 4-colouring of $P^+$ is nonrepetitive on walks, $\lambda(v_1),\lambda(v_2),\dots,\lambda(v_{2t})$ is boring. That is, $\lambda(v_j)=\lambda(v_{t+j})$ for all $j\in[t]$.}

\lem[\citep{KP}]{Shadow}{If $\lambda$ is a shadow-complete levelling of a graph $G$, then $$\pi(G)\leq 4\cdot\max_k\pi(G_{\lambda=k}).$$}

Now we generalise \lemref{Shadow} for walks. 

\lem{ShadowWalks}{If $H$ is a subgraph of a graph $G$, and $\lambda$ is a shadow-complete levelling of $G$, then 
$$\sigma(H)\;\leq\; 4\,\chi(H^2)\cdot\max_k\sigma(G_{\lambda=k})
\;\leq\; 4(\Delta(H)^2+1)\cdot\max_k\sigma(G_{\lambda=k}).$$}

%Thus every repetitively coloured walk $v_1,v_2,\dots,v_{2t}$ satisfies $\lambda(v_j)=\lambda(v_{t+j})$ for all $j\in[t]$. 

\prf{Let $c_1$ be the $4$-colouring of $G$ from \lemref{LevellingWalks}. 
Let $c_2$ be an optimal walk-nonrepetitive colouring of each level $G_{\lambda=k}$. Let $c_3$ be a proper $\chi(H^2)$-colouring of $H^2$. The second inequality in the lemma follows from the first since $\chi(H^2)\leq\Delta(H)^2+1$. Let $c(v):=(c_1(v),c_2(v),c_3(v))$ for each vertex $v$ of $H$. We claim that $c$ is nonrepetitive on walks in $H$.

Suppose on the contrary that $W=v_1,\dots,v_{2t}$ is a non-boring walk in $H$ that is repetitively coloured by $c$. Then $W$ is repetitively coloured by each of $c_1$, $c_2$, and $c_3$. Thus $\lambda(v_i)=\lambda(v_{t+i})$ for all $i\in[t]$ by \lemref{LevellingWalks}. Let $W_k$ be the sequence (allowing  repetitions) of vertices $v_i\in W$ such that $\lambda(v_i)=k$. Since $v_i\in W_k$ if and only if $v_{t+i}\in W_k$, each sequence $W_k$ is repetitively coloured. That is, if $W_k=x_1,\dots,x_{2s}$ then $c(x_i)=c(x_{s+i})$ for all $i\in[s]$. 

Let $k$ be the minimum level containing a vertex in $W$. Let $v_i$ and $v_j$ be consecutive vertices in $W_k$ with $i<j$. If $j=i+1$ then $v_iv_j$ is an edge of $W$. Otherwise there is walk from $v_i$ to $v_j$ in $G_{\lambda>k}$ (since $k$ was chosen minimum), implying $v_iv_j$ is an edge of $G$ (since $\lambda$ is shadow-complete). Thus $W_k$ forms a walk in $G_{\lambda=k}$ that is repetitively coloured by $c_2$. Hence $W_k$ is boring. In particular, some vertex $v_i=v_{t+i}$ is in $W_k$. Since $W$ is not boring, $v_j\ne v_{t+j}$ for some $j\in[t]$. Without loss of generality, $i<j$ and $v_\ell=v_{t+\ell}$ for all $\ell\in[i,j-1]$. Thus $v_j$ and $v_{t+j}$ have a common neighbour $v_{j-1}=v_{t+j-1}$ in $H$, which implies that $c_3(v_j)\ne c_3(v_{t+j})$. But $c(v_j)=c(v_{t+j})$ since $W$ is repetitively coloured, which is the desired contradiction.}

Note that some dependence on $\Delta(H)$ in \lemref{ShadowWalks} is unavoidable, since $\sigma(H)\geq\chi(H^2)\geq\Delta(H)+1$. 

\lemref{ShadowWalks} enables the following strengthening of \corref{WalkTree}.

\lem{TreeWalks}{Every tree $T$ satisfies $\Delta(T)+1\leq\sigma(T)\leq 4\,\Delta(T)$.}

\prf{Let $r$ be a leaf vertex of $T$. Let $\lambda(v)$ be the distance from $r$ to $v$ in $T$. Then $\lambda$ is a shadow-complete levelling of $T$ in which each level is an independent set. A greedy algorithm proves that $\chi(T^2)\leq\Delta(T)+1$. Thus \lemref{ShadowWalks} implies that $\sigma(T)\leq 4\,\Delta(T)+4$. Observe that the proof of \lemref{ShadowWalks} only requires $c_3(v)\ne c_3(w)$ whenever $v$ and $w$ are in the same level and have a common parent. Since $r$ is a leaf, each vertex has at most $\Delta(T)-1$ children. Thus a greedy algorithm produces a $\Delta(T)$-colouring with this property. Hence $\sigma(T)\leq4\,\Delta(T)$.}

A \emph{tree-partition} of a graph $G$ is a partition of its vertices into sets (called \emph{bags}) such that the graph obtained from $G$ by identifying the vertices in each bag is a forest (after deleting loops and replacing parallel edges by a single edge)\footnote{The proof by \citet{KP} that $\pi(G)\leq4^k$ for graphs with treewidth at most $k$ can also be described using tree-partitions; cf.~\citep{DMW-SJC05,Wood-JGT06}.}.
 
\lem{TreePartitionLevelling}{Let $G$ be a graph with a tree-partition in which every bag has at most $\ell$ vertices. Then $G$ is a subgraph of a graph $G'$ that has a shadow-complete levelling in which each level satisfies $$\pi(G'_{\lambda=k})\leq\sigma(G'_{\lambda=k})\leq\ell.$$}

\prf{Let $G'$ be the graph obtained from $G$ by adding an edge between all pairs of nonadjacent vertices in a common bag. Let $F$ be the forest obtained from $G'$ by identifying the vertices in each bag. Root each component of $F$. Consider a vertex $v$ of $G'$ that is in the bag that corresponds to node $x$ of $F$. Let $\lambda(v)$ be the distance between $x$ and the root of the tree component of $F$ that contains $x$. Clearly $\lambda$ is a levelling of $G'$. The $k$-shadow of each connected component of $G'_{\lambda>k}$ is contained in a single bag, and thus induces a clique on at most $\ell$ vertices. Hence $\lambda$ is shadow-complete. By colouring the vertices within each bag with distinct colors, we have $\pi(G'_{\lambda=k})\leq\sigma(G'_{\lambda=k})\leq\ell$.}

\threelemref{Shadow}{ShadowWalks}{TreePartitionLevelling} imply:

\lem{TreePartitionColouring}{If a graph $G$ has a tree-partition in which every bag has at most $\ell$ vertices, then $\pi(G)\leq 4\ell$ and $\sigma(G)\leq4\ell(\Delta(G)^2+1)$.}

\citet{Wood-TreePartitions} proved\footnote{The proof by \citet{Wood-TreePartitions} is a minor improvement to a similar result by an anonymous referee of the paper by \citet{DO-JGT95}.} that every graph with treewidth $k$ and maximum degree $\Delta\geq1$ has a tree-partition in which every bag has at most $\frac{5}{2}(k+1)(\frac{7}{2}\Delta-1)$ vertices. With \lemref{TreePartitionColouring} this proves the following quantitative version of \thmref{TreewidthDegree}.

\thm{TreewidthDegreeQuantative}{Every graph $G$ with treewidth $k$ and maximum degree $\Delta\geq1$ satisfies $\pi(G)\leq 10(k+1)(\frac{7}{2}\Delta-1)$ and $\sigma(G)\leq 10(k+1)(\frac{7}{2}\Delta-1)(\Delta^2+1)$.}

%\prf[Proof of Theorem~\ref{thm:TreewidthDegree}]{\citet{Wood-TreePartitions} proved\footnote{The proof is a minor improvement to a similar result by an anonymous referee of the paper by \citet{DO-JGT95}.} that $G$ has a tree-partition in which every bag has at most $2(k+1)(9\Delta-1)$ vertices. Add an edge to $G$ between all pairs of nonadjacent vertices in a common bag. Doing so does not decrease $\pi(G)$. Let $F$ be the forest obtained from $G$ by identifying the vertices in each bag. Root each component of $F$. Consider a vertex $v$ of $G$ that is in the bag that corresponds to node $x$ of $F$. Let $\lambda(v)$ be the distance between $x$ and the root of the tree component of $F$ that contains $x$. Clearly $\lambda$ is a levelling of $G$. Each level $G_{\lambda=k}$ is a set of cliques, each with at most $2(k+1)(9\Delta-1)$ vertices, and thus has a $2(k+1)(9\Delta-1)$-colouring that is nonrepetitive on paths. The $k$-shadow of each connected component of $G_{\lambda>k}$ is contained in a single bag, and thus induces a clique. By Lemma~\ref{lem:Shadow}, $\pi(G)\leq4\cdot2(k+1)(9\Delta-1)$.}

%\section{New Stuff}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%Each level $G_{\lambda=k}$ is a set of cliques, each with at most %$2(k+1)(9\Delta-1)$ vertices, and thus has a $2(k+1)(9\Delta-1)$-colouring that %is nonrepetitive on paths. 

%Thus $c(v_{i-1})=c(v_{t+i-1})$ and $c(v_{i+1})=c(v_{t+i+1})$ since $W$ is repetitive. Thus $v_{i-1}=v_{t+i-1}$ and $v_{i+1}=v_{t+i+1}$ since $c_3$ is a proper colouring of $G^2$. Thus $v_{i-1}$, $v_{i+1}$, $v_{t+i-1}$, $v_{t+i+1}$ are all in level $k+1$. Let $v_i$ be a vertex in $W$ at the minimum level with $i$ minimum. By \lemref{LevellingWalks}, $\lambda(v_i)=\lambda(v_{t+i})$. First suppose that $i\geq2$. Then $\lambda(v_{i-1})>\lambda(v_i)$ since $i$ was chosen minimum. By \lemref{LevellingWalks}, Now $W$ is not contained within level $\lambda(v_i)$, as otherwise $W$ would be repetitively coloured by $c_2$. Apply \lemref{Shadow} to $G$ to obtain a $4b$-colouring $c_1$ be that is nonrepetitive on paths.  

\sect{Subdivision}{Subdivisions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

The results of \citet{Thue06} and \citet{Currie-EJC02} imply that every path and every cycle has a subdivision $H$ with $\pi(H)=3$. \citet{BGKNP-NonRepTree-DM07} proved that every tree has a subdivision $H$ such that $\pi(H)=3$. Which graphs have a subdivision $H$ with $\pi(H)=3$ is an open problem \citep{Gryczuk-IJMMS07}. \citet{Gryczuk-IJMMS07} proved that every graph has a subdivision $H$ with $\pi(H)\leq 5$. Here we improve this bound as follows.

\thm{Subdivision}{Every graph $G$ has a subdivision $H$ with $\pi(H)\leq 4$.}

%The proof of \thmref{Subdivision} depends on the following lemma of \citet{KP}. 

%\lem[\citep{KP}]{Levelling}{For every levelling $\lambda$ of a graph $G$, there is $4$-colouring of $G$, such that every repetitively coloured path $v_1,v_2,\dots,v_{2t}$ satisfies $\lambda(v_j)=\lambda(v_{t+j})$ for all $j\in[t]$.}

\begin{proof} %[Proof of \thmref{Subdivision}]
Without loss of generality $G$ is connected. Say $V(G)=\{v_0,v_1,\dots,v_{n-1}\}$. As illustrated in Figure~\ref{fig:Subdiv}, let $H$ be the subdivision of $G$ obtained by subdividing every edge $v_iv_j\in E(G)$ (with $i<j$) $j-i-1$ times. The distance of every vertex in $H$ from $v_0$ defines a levelling of $H$ such that the endpoints of every edge are in consecutive levels. By \lemref{LevellingWalks}, there is a $4$-colouring of $H$, such that for every repetitively coloured path $x_1,x_2,\dots,x_t,y_1,y_2,\dots,y_t$ in $H$, $x_j$ and $y_j$ have the same level for all $j\in[t]$. Hence there is some $j$ such that $x_{j-1}$ and $x_{j+1}$ are at the same level. Thus $x_j$ is an original vertex $v_i$ of $G$. Without loss of generality $x_{j-1}$ and $x_{j+1}$ are at level $i-1$. There is only one original vertex at level $i$. Thus $y_j$, which is also at level $i$, is a division vertex. Now $y_j$ has two neighbours in $H$, which are at levels $i-1$ and $i+1$. Thus $y_{j-1}$ and $y_{j+1}$ are at levels $i-1$ and $i+1$, which contradicts the fact that $x_{j-1}$ and $x_{j+1}$ are both at level $i-1$. Hence we have a $4$-colouring of $H$ that is nonrepetitive on paths.
\end{proof}

\begin{figure}[!ht]
\begin{center}
\includegraphics{r99Subdiv.eps}
\caption{\label{fig:Subdiv}The subdivision $H$ with $G=K_6$.}
\end{center}
\end{figure}

It is possible that every graph has a subdivision $H$ with $\pi(H)\leq3$. If true, this would provide a striking generalisation of the result of \citet{Thue06} discussed in \secref{Introduction}. 

%\comment{DW: Conjecture: Every graph $G$ has a subdivision $H$ with $\sigma(H)\leq\Delta(G)+\Oh{1}$. 
%JB:  The idea might be that we subdivide each edge $10^{10}$ times and put a palindrome- and  square-free sequence on the new edges using 4  extra symbols.
 % DW: Would it help to subdivide each edge a distinct number of times?}

%Is this related to $\chi'(G')$?

\sect{Density}{Maximum Density}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

In this section we study the maximum number of edges in a nonrepetitively coloured graph.

\prop{Extremal}{The maximum number of edges in an $n$-vertex graph $G$ with $\pi(G)\leq c$ is $(c-1)n-\binom{c}{2}$.}

\prf{Say $G$ is an $n$-vertex graph with $\pi(G)\leq c$. Fix a $c$-colouring of $G$ that is nonrepetitive on paths. Say there are $n_i$ vertices in the $i$-th colour class. Every cycle receives at least three colours. Thus the subgraph induced by the vertices coloured $i$ and $j$ is a forest, and has at most $n_i+n_j-1$ edges. Hence the number of edges in $G$ is at most 
\begin{equation*}
\sum_{1\leq i<j\leq c}(n_i+n_j-1)=\sum_{1\leq i\leq c}(c-1)n_i-\binom{c}{2}
=(c-1)n-\binom{c}{2}.
\end{equation*}
This bound is attained by the graph consisting of a complete graph $K_{c-1}$ completely connected to an independent set of $n-(c-1)$ vertices, which obviously has a $c$-colouring that is nonrepetitive on paths.}

Now consider the maximum number of edges in a coloured graph that is nonrepetitive on walks. First note that the example in the proof of \propref{Extremal} is repetitive on walks. Since $\sigma(G)\geq\Delta(G)+1$ and $|E(G)|\leq\half\Delta(G)|V(G)|$, we have the trivial upper bound, 
$$|E(G)|\leq\half(\sigma(G)-1)|V(G)|.$$
This bound is tight for $\sigma=2$ (matchings) and $\sigma=3$ (cycles), but is not known to be tight for $\sigma\geq 4$. 

We have the following lower bound. 

\prop{Example}{For all $p\geq1$, there are infinitely many graphs $G$ with $\sigma(G)\leq 4p$ and $$|E(G)|\geq\eighth(3\sigma(G)-4)|V(G)|-\ninth\sigma(G)^2.$$}

%We claim that $c$ is nonrepetitive on walks in $G$. Suppose on the contrary that $W=v_1,\dots,v_{2t}$ is a non-boring walk in $G$ that is repetitively coloured by $c$. Then $W$ is repetitively coloured by $c_1$. Thus $\lambda(v_i)=\lambda(v_{t+i})$ for all $i\in[t]$ by \lemref{LevellingWalks}. Since $W$ is not boring, some $v_i\ne v_{t+i}$. By construction, $c(v_i)\ne c(v_{t+i})$, which contradicts the assumption that $W$ is repetitively coloured. 

\prf{Let $G$ be the lexicographic product of a path and $K_p$; that is, $G$ is the graph with a levelling $\lambda$ in which each level induces $K_p$, and every edge is present between consecutive levels. Let $c_1$ be the $4$-colouring of $G$ from \lemref{LevellingWalks}. If $v$ is the $j$-th vertex in its level, where $j\in[p]$, then let $c(v):=(c_1(v),j)$. The number of colours is $4p$. Applying \lemref{LevellingWalks}, it is easily verified that $c$ is nonrepetitive on walks. Hence $\sigma(G)\leq 4p$. Now we count the edges: 
$|E(G)|=\half(3p-1)|V(G)|-p^2$.
As a lower bound, $\sigma(G)\geq\Delta(G)+1=3p$. 
Thus $|E(G)|\geq\half(3\sigma(G)/4-1)|V(G)|-(\sigma(G)/3)^2$.}

%\opn{}{Does every graph $G$ satisfy $|E(G)|\leq(\frac{3}{8}+o(1))\sigma(G)|V(G)|$?}

\section*{Acknowledgement}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Thanks to Carsten Thomassen whose generous hospitality at the Technical University of Denmark enabled this collaboration.

%\section*{Conjectures not for publication}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\comment{DW: Conjecture: The only $\Delta$-regular graph $G$ with $\sigma(G)=\Delta+1$ is $G=K_{\Delta+1}$ for all $\Delta\geq3$.

%JB: Interesting. What happens if $\Delta=3$ and the girth is large? On the other hand, it  might be again sufficient to concentrate on  walks of length 3 on 3 vertices.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\bibliographystyle{myNatbibStyle}
%\bibliography{myBibliography,myConferences}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\soft#1{\leavevmode\setbox0=\hbox{h}\dimen7=\ht0\advance \dimen7
  by-1ex\relax\if t#1\relax\rlap{\raise.6\dimen7
  \hbox{\kern.3ex\char'47}}#1\relax\else\if T#1\relax
  \rlap{\raise.5\dimen7\hbox{\kern1.3ex\char'47}}#1\relax \else\if
  d#1\relax\rlap{\raise.5\dimen7\hbox{\kern.9ex \char'47}}#1\relax\else\if
  D#1\relax\rlap{\raise.5\dimen7 \hbox{\kern1.4ex\char'47}}#1\relax\else\if
  l#1\relax \rlap{\raise.5\dimen7\hbox{\kern.4ex\char'47}}#1\relax \else\if
  L#1\relax\rlap{\raise.5\dimen7\hbox{\kern.7ex
  \char'47}}#1\relax\else\message{accent \string\soft \space #1 not
  defined!}#1\relax\fi\fi\fi\fi\fi\fi} \def\Dbar{\leavevmode\lower.6ex\hbox to
  0pt{\hskip-.23ex \accent"16\hss}D}
\begin{thebibliography}{30}
\providecommand{\natexlab}[1]{#1}
\providecommand{\url}[1]{\texttt{#1}}
\providecommand{\urlprefix}{}
\expandafter\ifx\csname urlstyle\endcsname\relax
  \providecommand{\doi}[1]{doi:\discretionary{}{}{}#1}\else
  \providecommand{\doi}{doi:\discretionary{}{}{}\begingroup
  \urlstyle{rm}\Url}\fi

\setlength{\parskip}{\BiblioSpacing}
\setlength{\itemsep}{\BiblioSpacing}

\bibitem[{Albertson et~al.(2004)Albertson, Chappell, Kierstead, K{\"u}ndgen,
  and Ramamurthi}]{Albertson-EJC04}
\textsc{Michael~O. Albertson, Glenn~G. Chappell, Hal~A. Kierstead, Andr\'{e}
  K{\"u}ndgen, and Radhika Ramamurthi}.
\newblock Coloring with no 2-colored ${P}_4$'s.
\newblock \emph{Electron. J. Combin.}, 11 \#R26, 2004.

\bibitem[{Alon and Grytczuk(2005)}]{AG-EuroComb05}
\textsc{Noga Alon and Jaros{\l}aw Grytczuk}.
\newblock Nonrepetitive colorings of graphs.
\newblock In \textsc{Stefan Felsner}, ed., \emph{2005 European Conf. on
  Combinatorics, Graph Theory and Applications} (EuroComb '05), vol.~AE of
  \emph{Discrete Math. Theor. Comput. Sci. Proceedings}, pp. 133--134. 2005.

\bibitem[{Alon and Grytczuk(2008)}]{BreakingRhythm}
\textsc{Noga Alon and Jaros{\l}aw Grytczuk}.
\newblock Breaking the rhythm on graphs.
\newblock \emph{Discrete Math.}, 308:1375--1380, 2008.

\bibitem[{Alon et~al.(2002)Alon, Grytczuk, Ha{\l}uszczak, and
  Riordan}]{AGHR-RSA02}
\textsc{Noga Alon, Jaros{\l}aw Grytczuk, Mariusz Ha{\l}uszczak, and Oliver
  Riordan}.
\newblock Nonrepetitive colorings of graphs.
\newblock \emph{Random Structures Algorithms}, 21(3-4):336--346, 2002.

\bibitem[{Bar{\'a}t and Varj{\'u}(2007)}]{BV-NonRepVertex}
\textsc{J{\'a}nos Bar{\'a}t and P{\'e}ter~P. Varj{\'u}}.
\newblock On square-free vertex colorings of graphs.
\newblock \emph{Studia Sci. Math. Hungar.}, 44(3):411--422, 2007.

\bibitem[{Bar{\'a}t and Varj{\'u}(pear)}]{BV-NonRepEdge}
\textsc{J{\'a}nos Bar{\'a}t and P{\'e}ter~P. Varj{\'u}}.
\newblock On square-free edge colorings of graphs.
\newblock \emph{Ars Combinatoria}, to appear.

\bibitem[{Bodlaender(1998)}]{Bodlaender-TCS98}
\textsc{Hans~L. Bodlaender}.
\newblock A partial $k$-arboretum of graphs with bounded treewidth.
\newblock \emph{Theoret. Comput. Sci.}, 209(1-2):1--45, 1998.

\bibitem[{Borodin(1979)}]{Borodin-DM79}
\textsc{Oleg~V. Borodin}.
\newblock On acyclic colorings of planar graphs.
\newblock \emph{Discrete Math.}, 25(3):211--236, 1979.

\bibitem[{Bre{\v{s}}ar et~al.(2007)Bre{\v{s}}ar, Grytczuk, Klav{\v{z}}ar,
  Niwczyk, and Peterin}]{BGKNP-NonRepTree-DM07}
\textsc{Bo{\v{s}}tjan Bre{\v{s}}ar, Jaros{\l}aw Grytczuk, Sandi Klav{\v{z}}ar,
  S.~Niwczyk, and Iztok Peterin}.
\newblock Nonrepetitive colorings of trees.
\newblock \emph{Discrete Math.}, 307(2):163--172, 2007.

\bibitem[{Bre{\v{s}}ar and Klav{\v{z}}ar(2004)}]{BK-AC04}
\textsc{Bo{\v{s}}tjan Bre{\v{s}}ar and Sandi Klav{\v{z}}ar}.
\newblock Square-free colorings of graphs.
\newblock \emph{Ars Combin.}, 70:3--13, 2004.

\bibitem[{Currie(2002)}]{Currie-EJC02}
\textsc{James~D. Currie}.
\newblock There are ternary circular square-free words of length {$n$} for
  {$n\geq 18$}.
\newblock \emph{Electron. J. Combin.}, 9(1), 2002.

\bibitem[{Currie(2005)}]{Currie-TCS05}
\textsc{James~D. Currie}.
\newblock Pattern avoidance: themes and variations.
\newblock \emph{Theoret. Comput. Sci.}, 339(1):7--18, 2005.

\bibitem[{Czerwi\'{n}ski and Grytczuk(2007)}]{CG-ENDM07}
\textsc{Sebastian Czerwi\'{n}ski and Jaros{\l}aw Grytczuk}.
\newblock Nonrepetitive colorings of graphs.
\newblock \emph{Electron. Notes Discrete Math.}, 28:453--459, 2007.

\bibitem[{Ding and Oporowski(1995)}]{DO-JGT95}
\textsc{Guoli Ding and Bogdan Oporowski}.
\newblock Some results on tree decomposition of graphs.
\newblock \emph{J. Graph Theory}, 20(4):481--499, 1995.

\bibitem[{Dujmovi{\'c} et~al.(2005)Dujmovi{\'c}, Morin, and Wood}]{DMW-SJC05}
\textsc{Vida Dujmovi{\'c}, Pat Morin, and David~R. Wood}.
\newblock Layout of graphs with bounded tree-width.
\newblock \emph{SIAM J. Comput.}, 34(3):553--579, 2005.

\bibitem[{Erd{\H{o}}s and Lov\'{a}sz(1975)}]{EL75}
\textsc{Paul Erd{\H{o}}s and L\'{a}szl\'{o} Lov\'{a}sz}.
\newblock Problems and results on {$3$}-chromatic hypergraphs and some related
  questions.
\newblock In \emph{Infinite and Finite Sets}, vol.~10 of \emph{Colloq. Math.
  Soc. J\'anos Bolyai}, pp. 609--627. North-Holland, 1975.

\bibitem[{Fertin et~al.(2004)Fertin, Raspaud, and Reed}]{FRR-JGT04}
\textsc{Guillaume Fertin, Andr\'{e} Raspaud, and Bruce Reed}.
\newblock On star coloring of graphs.
\newblock \emph{J. Graph Theory}, 47(3):163--182, 2004.

\bibitem[{Gr{\"u}nbaum(1973)}]{Grunbaum73}
\textsc{Branko Gr{\"u}nbaum}.
\newblock Acyclic colorings of planar graphs.
\newblock \emph{Israel J. Math.}, 14:390--408, 1973.

\bibitem[{Grytczuk(2002)}]{Grytczuk-EJC02}
\textsc{Jaros{\l}aw Grytczuk}.
\newblock Thue-like sequences and rainbow arithmetic progressions.
\newblock \emph{Electron. J. Combin.}, 9(1):R44, 2002.

\bibitem[{Grytczuk(2007{\natexlab{a}})}]{Gryczuk-IJMMS07}
\textsc{Jaros{\l}aw Grytczuk}.
\newblock Nonrepetitive colorings of graphs---a survey.
\newblock \emph{Int. J. Math. Math. Sci.}, 2007:74639, 2007{\natexlab{a}}.

\bibitem[{Grytczuk(2007{\natexlab{b}})}]{Grytczuk-PatternAvoidance}
\textsc{Jaros{\l}aw Grytczuk}.
\newblock Pattern avoidance on graphs.
\newblock \emph{Discrete Math.}, 307(11-12):1341--1346, 2007{\natexlab{b}}.

\bibitem[{Grytczuk(pear)}]{ThueProblems}
\textsc{Jaros{\l}aw Grytczuk}.
\newblock Thue type problems for graphs, points, and numbers.
\newblock \emph{Discrete Math.}, 308(19):4419--4429, 2008.

\bibitem[{K{\"u}ndgen and Pelsmajer(pear)}]{KP}
\textsc{Andre K{\"u}ndgen and Michael~J. Pelsmajer}.
\newblock Nonrepetitive colorings of graphs of bounded tree-width.
\newblock \emph{Discrete Math.}, 308(19):4473--4478, 2008.

\bibitem[{Manin(2007)}]{Manin}
\textsc{Fedor Manin}.
\newblock The complexity of nonrepetitive edge coloring of graphs, 2007.
\newblock \urlprefix\url{arxiv.org/abs/0709.4497}.

\bibitem[{Ne{\v{s}}et{\v{r}}il and {Ossona de Mendez}(2003)}]{NesOdM-03}
\textsc{Jaroslav Ne{\v{s}}et{\v{r}}il and Patrice {Ossona de Mendez}}.
\newblock Colorings and homomorphisms of minor closed classes.
\newblock In \textsc{Boris Aronov, Saugata Basu, J\'{a}nos Pach, and Micha
  Sharir}, eds., \emph{Discrete and Computational Geometry, The Goodman-Pollack
  Festschrift}, vol.~25 of \emph{Algorithms and Combinatorics}, pp. 651--664.
  Springer, 2003.

\bibitem[{Reed(2003)}]{Reed-AlgoTreeWidth03}
\textsc{Bruce~A. Reed}.
\newblock Algorithmic aspects of tree width.
\newblock In \textsc{Bruce~A. Reed and Cl{\'a}udia~L. Sales}, eds.,
  \emph{Recent Advances in Algorithms and Combinatorics}, pp. 85--107.
  Springer, 2003.

\bibitem[{Thue(1906)}]{Thue06}
\textsc{Axel Thue}.
\newblock {\"U}ber unendliche {Z}eichenreihen.
\newblock \emph{Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania}, 7:1--22,
  1906.

\bibitem[{Wood(2005)}]{Wood-DMTCS05}
\textsc{David~R. Wood}.
\newblock Acyclic, star and oriented colourings of graph subdivisions.
\newblock \emph{Discrete Math. Theor. Comput. Sci.}, 7(1):37--50, 2005.

\bibitem[{Wood(2006)}]{Wood-JGT06}
\textsc{David~R. Wood}.
\newblock Vertex partitions of chordal graphs.
\newblock \emph{J. Graph Theory}, 53(2):167--172, 2006.

\bibitem[{Wood(2007)}]{Wood-TreePartitions}
\textsc{David~R. Wood}.
\newblock On tree-partition-width, 2007.
\newblock \urlprefix\url{arXiv.org/math/0602507}.

\end{thebibliography}

\appendix
\section{Corrigendum (12 December 2014)}

The authors are extremely grateful to Joseph Antonides, Claire Spychalla, Nicole Yamzon who identified and corrected an error in this paper (in January 2014). The error occurs in the proof of \thmref{Subdivision} when $t=2$. The proof claimed that $x_{j-1}$ and $x_{j+1}$
are at the same level for some $j$. Since only $x_1,\dots,x_t$ are defined, we must have $j-1\geq 1$ and $j+1\leq t$, implying $t\geq 3$. Thus, this claim does not make sense if $t=2$. In particular, if $v_a,v_{b+1},v_b,v_c$ is a path in $G$ with $a<b<c-1$, and $p$ is the division vertex on $v_av_{b+1}$ adjacent to $v_{b+1}$, and $q$ is the 
division vertex on $v_bv_{c}$ adjacent to $v_{b}$, then $q,v_b,v_{b+1},p$ is a repetitively coloured path in $H$. 

Antonides, Spychalla and Yamzon proposed the following correction. Let $G$ be a connected graph with $V(G)=\{v_0,v_1,\dots,v_{n-1}\}$. Let $H$ be the subdivision of $G$ obtained by subdividing every edge $v_iv_j\in E(G)$ (with $i<j$) $2(j-i)-1$ times. The distance of every vertex in $H$ from $v_0$ defines a levelling of $H$ such that the endpoints of every edge are in consecutive levels. (Think of $v_0,v_1,\dots,v_{n-1}$ on a horizontal line, with a vertical line through each $v_i$, and an additional vertical line between $v_i$ and $v_{i+1}$. Each edge is subdivided at each point it crosses a vertical line.)

Consider the 4-colouring of $H$ given by \lemref{LevellingWalks}. Suppose on the contrary that $H$ contains a repetitively coloured path $x_1,x_2,\dots,x_t,y_1,y_2,\dots,y_t$. By \lemref{LevellingWalks}, $x_j$ and $y_j$ have the same level for all $j\in[t]$. 

First suppose that $t=2$. Since $x_1$ and $y_1$ have the same level, and $x_2$ is adjacent to both $x_1$ and $y_1$, it must be that $x_2$ is an original vertex (since division vertices only have two neighbours, and they are on distinct levels). Similarly, $y_1$ is an original vertex. This is a contradiction, since no two original vertices are adjacent to $H$. Now assume that $t\geq 3$. 

Now suppose that $x_{j-1}$ and $x_{j+1}$ are at the same level for some $j\in[2,t-1]$. Thus $x_j$ is an original vertex of $G$. Say $x_j$ is at level $i$. Without loss of generality $x_{j-1}$ and $x_{j+1}$ are at level $i-1$. There is only one original vertex at each level. Thus $y_j$, which is also at level $i$, is a division vertex. Now $y_j$ has two neighbours in $H$, which are at levels $i-1$ and $i+1$. Thus $y_{j-1}$ and $y_{j+1}$ are at levels $i-1$ and $i+1$, which contradicts the fact that $x_{j-1}$ and $x_{j+1}$ are both at level $i-1$.  Now assume that for all $j\in[2,t-1]$, the vertices $x_{j-1}$ and $x_{j+1}$ are at distinct levels.

Say $x_1$ is at level $i$. Without loss of generality, $x_2$ is at level $i+1$ (since no edge has both endpoints in the same level).  It follows that $x_j$ is at level $i+j-1$ for all $j\in[1,t]$. 
In particular, $x_t$ is at level $i+t-1$. Now, $y_1$ is at level $i$ (the same level as $x_1$). Since $x_ty_1$ is an edge, and every edge goes between consecutive levels, $|(i+t-1)-i|=1$, implying $t=2$, which is a contradiction. Hence we have a $4$-colouring of $H$ that is nonrepetitive on paths.

Finally, note that reference \cite{BV-NonRepEdge} appeared in \emph{Ars Combin.}~87:377--383, 2008; reference \cite{Wood-TreePartitions} appeared in \emph{European J. Combinatorics}~30:1245--1253, 2009; and Andrzej Pezarski and Micha{\l} Zmarz [Non-Repetitive 3-Coloring of Subdivided Graphs, \emph{Electronic J. Combin.} 16(1):\#N15, 2009] 
solved the problem posed at the end of \secref{Subdivision} by proving that every graph has a nonrepetitively 3-colourable subdivision.

\end{document}


%The \emph{width} of a tree-partition is the maximum cardinality of a single bag. The \emph{tree-partition-width} of a graph $G$ is the minimum width of a tree-partition of $G$. 

%A graph with bounded degree has bounded tree-partition-width if and only if it has bounded treewidth \cite{DO-DM96}. In particular, \citet{Seese85} proved the lower bound, 
%\begin{equation*}\label{WidthLowerBound}
%2\cdot\tpw{G}\geq\tw{G}+1\enspace,
%\end{equation*}
%which is tight for even complete graphs. The best known upper bound is
%\begin{equation*}\label{WidthUpperBound}
%\tpw{G}\leq 2\big(\tw{G}+1\big)\big(9\,\Delta(G)-1\big)\enspace,
%\end{equation*}
%which was obtained by the second author \citep{Wood-TreePartitions} using a minor improvement to a similar result by an anonymous referee of the paper by \citet{DO-JGT95}. See \citep{Seese85, Halin91, BodEng-JAlg97, Bodlaender-DMTCS99, Wood-Partitions-JGT, DO-DM96, Edenbrandt86, DMW-SJC05} for other results on tree partitions.


