# Planar Graphs Have Bounded
Nonrepetitive Chromatic Number111This revision of the original published paper
corrects an error in Section 4. In particular, “$K_{\\_}k+$” has been added to
Theorem 14 and “$k+$” has been added in several places thereafter.

Vida Dujmović Research supported by NSERC and the Ontario Ministry of Research
and Innovation. Louis Esperet Partially supported by ANR Projects GATO
(anr-16-ce40-0009-01) and GrR (anr-18-ce40-0032). Gwenaël Joret Research
supported by an ARC grant from the Wallonia-Brussels Federation of Belgium.
Bartosz Walczak Research partially supported by National Science Centre of
Poland grant 2015/17/D/ST1/00585. David R. Wood Research supported by the
Australian Research Council.

###### Abstract

A colouring of a graph is _nonrepetitive_ if for every path of even order, the
sequence of colours on the first half of the path is different from the
sequence of colours on the second half. We show that planar graphs have
nonrepetitive colourings with a bounded number of colours, thus proving a
conjecture of Alon, Grytczuk, Hałuszczak and Riordan (2002). We also
generalise this result for graphs of bounded Euler genus, graphs excluding a
fixed minor, and graphs excluding a fixed topological minor.

title = Planar Graphs Have Bounded Nonrepetitive Chromatic Number, author =
Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, David R. Wood,
plaintextauthor = Vida Dujmovic, Louis Esperet, Gwenael Joret, Bartosz
Walczak, David R. Wood, year=2020, number=5, received=11 April 2019,
published=6 March 2020, updated=7 July 2020,

[classification=text]

##  1 Introduction

A vertex colouring of a graph is _nonrepetitive_ if there is no path for which
the first half of the path is assigned the same sequence of colours as the
second half. More precisely, a $k$-_colouring_ of a graph $G$ is a function
$\phi$ that assigns one of $k$ colours to each vertex of $G$. A path
$(v_{\\_}1,v_{\\_}2,\dots,v_{\\_}{2t})$ of even order in $G$ is _repetitively_
coloured by $\phi$ if $\phi(v_{\\_}i)=\phi(v_{\\_}{t+i})$ for
$i\in\\{1,\dots,t\\}$. A colouring $\phi$ of $G$ is _nonrepetitive_ if no path
of $G$ is repetitively coloured by $\phi$. Observe that a nonrepetitive
colouring is _proper_ , in the sense that adjacent vertices are coloured
differently. The _nonrepetitive chromatic number_ $\pi(G)$ is the minimum
integer $k$ such that $G$ admits a nonrepetitive $k$-colouring.

The classical result in this area is by Thue [51], who proved in 1906 that
every path is nonrepetitively 3-colourable. Starting with the seminal work of
Alon et al. [3], nonrepetitive colourings of general graphs have recently been
widely studied; see the surveys [27, 28, 11, 26, 50] and other references [23,
32, 12, 33, 28, 17, 43, 16, 2, 7, 5, 20, 10, 30, 9, 13, 40, 36, 21, 41, 6, 25,
3, 31, 38, 4, 37, 8, 51, 22, 29, 52, 54, 35, 14, 1, 44, 45, 48, 34, 53, 49,
42, 27, 11, 26, 50].

Several graph classes are known to have bounded nonrepetitive chromatic
number. In particular, cycles are nonrepetitively 3-colourable (except for a
finite number of exceptions) [12], trees are nonrepetitively 4-colourable [9,
36], outerplanar graphs are nonrepetitively $12$-colourable [36, 5], and more
generally, every graph with treewidth $k$ is nonrepetitively
$4^{k}$-colourable [36]. Graphs with maximum degree $\Delta$ are
nonrepetitively $O(\Delta^{2})$-colourable [3, 27, 32, 17], and graphs
excluding a fixed immersion have bounded nonrepetitive chromatic number [53].

It is widely recognised that the most important open problem in the field of
nonrepetitive graph colouring is whether planar graphs have bounded
nonrepetitive chromatic number. It was first asked by Alon et al. [3]. The
best known lower bound is $11$, due to Ochem (see [16]). The best known upper
bound is $O(\log n)$ where $n$ is the number of vertices, due to Dujmović,
Frati, Joret, and Wood [16]. Note that several works have studied colourings
of planar graphs in which only facial paths are required to be nonrepetitively
coloured [33, 44, 45, 4, 48, 34, 8].

This paper proves that planar graphs have bounded nonrepetitive chromatic
number.

######  Theorem 1.

Every planar graph $G$ satisfies $\pi(G)\leqslant 768$.

We generalise this result for graphs of bounded Euler genus, for graphs
excluding any fixed minor, and for graphs excluding any fixed topological
minor.222The Euler genus of the orientable surface with $h$ handles is $2h$.
The Euler genus of the non-orientable surface with $c$ cross-caps is $c$. The
Euler genus of a graph $G$ is the minimum integer $k$ such that $G$ embeds in
a surface of Euler genus $k$. Of course, a graph is planar if and only if it
has Euler genus 0; see [39] for more about graph embeddings in surfaces. A
graph $X$ is a minor of a graph $G$ if a graph isomorphic to $X$ can be
obtained from a subgraph of $G$ by contracting edges. A graph $X$ is a
_topological minor_ of a graph $G$ if a subdivision of $X$ is a subgraph of
$G$. If $G$ contains $X$ as a topological minor, then $G$ contains $X$ as a
minor. If $G$ contains no $X$ minor, then $G$ is _$X$ -minor-free_. If $G$
contains no $X$ topological minor, then $G$ is _$X$ -topological-minor-free._
The result for graphs excluding a fixed minor confirms a conjecture of
Grytczuk [27, 28].

######  Theorem 2.

Every graph $G$ with Euler genus $g$ satisfies $\pi(G)\leqslant
256\max\\{2g,3\\}$.

######  Theorem 3.

For every graph $X$, there is an integer $k$ such that every $X$-minor-free
graph $G$ satisfies $\pi(G)\leqslant k$.

######  Theorem 4.

For every graph $X$, there is an integer $k$ such that every $X$-topological-
minor-free graph $G$ satisfies $\pi(G)\leqslant k$.

The proofs of Theorems 1 and 2 are given in Section 3, and the proofs of
Theorems 3 and 4 are given in Section 4. Before that in Section 2 we introduce
the tools used in our proofs, namely so-called strongly nonrepetitive
colourings, tree-decompositions and treewidth, and strong products. With these
tools in hand, the above theorems quickly follow from recent results of
Dujmović et al. [18] that show that planar graphs and other graph classes are
subgraphs of certain strong products.

##  2 Tools

Undefined terms and notation can be found in [15].

###  2.1 Strongly Nonrepetitive Colourings

A key to all our proofs is to consider a strengthening of nonrepetitive
colouring defined below.

For a graph $G$, a _lazy walk_ in $G$ is a sequence of vertices
$v_{\\_}1,\ldots,v_{\\_}k$ such that for each $i\in\\{1,\dots,k\\}$, either
$v_{\\_}iv_{\\_}{i+1}$ is an edge of $G$, or $v_{\\_}i=v_{\\_}{i+1}$. A lazy
walk can be thought of as a walk in the graph obtained from $G$ by adding a
loop at each vertex. For a colouring $\phi$ of $G$, a lazy walk
$v_{\\_}1,\ldots,v_{\\_}{2k}$ is _$\phi$ -repetitive_ if
$\phi(v_{\\_}i)=\phi(v_{\\_}{i+k})$ for each $i\in\\{1,\dots,k\\}$.

A colouring $\phi$ is _strongly nonrepetitive_ if for every $\phi$-repetitive
lazy walk $v_{\\_}1,\ldots,v_{\\_}{2k}$, there exists $i\in\\{1,\dots,k\\}$
such that $v_{\\_}i=v_{\\_}{i+k}$. Let $\pi^{*}(G)$ be the minimum number of
colours in a strongly nonrepetitive colouring of $G$. Since a path has no
repeated vertices, every strongly nonrepetitive colouring is nonrepetitive,
and thus $\pi(G)\leqslant\pi^{*}(G)$ for every graph $G$.

###  2.2 Layerings

A _layering_ of a graph $G$ is a partition $(V_{\\_}0,V_{\\_}1,\dots)$ of
$V(G)$ such that for every edge $vw\in E(G)$, if $v\in V_{\\_}i$ and $w\in
V_{\\_}j$, then $|i-j|\leqslant 1$. If $r$ is a vertex in a connected graph
$G$ and $V_{\\_}i$ is the set of vertices at distance exactly $i$ from $r$ in
$G$ for all $i\geqslant 0$, then the layering $(V_{\\_}0,V_{\\_}1,\dots)$ is
called a _BFS layering_ of $G$.

Consider a layering $(V_{\\_}0,V_{\\_}1,\dots)$ of a graph $G$. Let $H$ be a
connected component of $G[V_{\\_}i\cup V_{\\_}{i+1}\cup\cdots]$, for some
$i\geqslant 1$. The _shadow_ of $H$ is the set of vertices in $V_{\\_}{i-1}$
adjacent to some vertex in $H$. The layering is _shadow-complete_ if every
shadow is a clique. This concept was introduced by Kündgen and Pelsmajer [36]
and implicitly by Dujmović et al. [19].

We will need the following result.

######  Lemma 5 ([36, 19]).

Every BFS-layering of a connected chordal graph is shadow-complete.

###  2.3 Treewidth

A _tree-decomposition_ of a graph $G$ consists of a collection
$\\{B_{\\_}x\subseteq V(G):x\in V(T)\\}$ of subsets of $V(G)$, called _bags_ ,
indexed by the vertices of a tree $T$, and with the following properties:

  * •

for every vertex $v$ of $G$, the set $\\{x\in V(T):v\in B_{\\_}x\\}$ induces a
non-empty (connected) subtree of $T$, and

  * •

for every edge $vw$ of $G$, there is a vertex $x\in V(T)$ for which $v,w\in
B_{\\_}x$.

The _width_ of such a tree-decomposition is $\max\\{|B_{\\_}x|:x\in
V(T)\\}-1$. The _treewidth_ of a graph $G$ is the minimum width of a tree-
decomposition of $G$. Tree-decompositions were introduced by Robertson and
Seymour [46]. Treewidth measures how similar a given graph is to a tree, and
is particularly important in structural and algorithmic graph theory.

Barát and Varjú [5] and Kündgen and Pelsmajer [36] independently proved that
graphs of bounded treewidth have bounded nonrepetitive chromatic number.
Specifically, Kündgen and Pelsmajer [36] proved that every graph with
treewidth $k$ is nonrepetitively $4^{k}$-colourable, which is the best known
bound. Theorem 7 below strengthens this result. The proof is almost identical
to that of Kündgen and Pelsmajer [36] and depends on the following lemma. A
lazy walk $v_{\\_}1,\ldots,v_{\\_}{2k}$ is _boring_ if $v_{\\_}i=v_{\\_}{i+k}$
for each $i\in\\{1,\dots,k\\}$.

######  Lemma 6 ([36]).

Every path $P$ has a $4$-colouring $\phi$ such that every $\phi$-repetitive
lazy walk is boring.

######  Theorem 7.

For every graph $G$ of treewidth at most $k\geqslant 0$, we have
$\pi^{*}(G)\leqslant 4^{k}$.

###### Proof.

The proof proceeds by induction on $k$. If $k=0$, then $G$ has no edges, so
assigning the same colour to all the vertices gives a strongly nonrepetitive
colouring. For the rest of the proof, assume that $k\geqslant 1$. Consider a
tree-decomposition of $G$ of width at most $k$. By adding edges if necessary,
we may assume that every bag of the tree-decomposition is a clique. Thus, $G$
is connected and chordal, with clique-number at most $k+1$.

Let $(V_{\\_}0,V_{\\_}1,\ldots)$ be a BFS-layering of $G$. We refer to
$V_{\\_}i$ as the set of vertices at _depth_ $i$. Note that the subgraph
$G[V_{\\_}i]$ of $G$ induced by each layer $V_{\\_}i$ has treewidth at most
$k-1$.333This is clear for $i=0$ (since $k\geqslant 1$), and for $i\geqslant
1$ this follows from the fact that the graph $G[V_{\\_}i]$ plus a universal
vertex is a minor of $G$ (contract $V_{\\_}0\cup\cdots\cup V_{\\_}{i-1}$ into
a single vertex and remove $V_{\\_}{i+1},V_{\\_}{i+2},\dots$), and thus has
treewidth at most $k$. Since removing a universal vertex decreases the
treewidth by exactly one, it follows that $G[V_{\\_}i]$ has treewidth at most
$k-1$. Thus the spanning subgraph $H$ of $G$ induced by all edges whose
endpoints have the same depth also has treewidth at most $k-1$. By the
induction hypothesis, $H$ has a strongly nonrepetitive colouring $\phi_{\\_}1$
with $4^{k-1}$ colours. The graph $P$ obtained from $G$ by contracting each
set $V_{\\_}i$ (which might not induce a connected graph) into a single vertex
$x_{\\_}i$ is a path, and thus, by Lemma 6, $P$ has a $4$-colouring
$\phi_{\\_}2$ such that every $\phi_{\\_}2$-repetitive walk is boring. For
each $i\geqslant 0$ and each vertex $u\in V_{\\_}i$, set
$\phi(u):=(\phi_{\\_}1(u),\phi_{\\_}2(x_{\\_}i))$. The colouring $\phi$ of $G$
uses at most $4\cdot 4^{k-1}=4^{k}$ colours.

We now prove that $\phi$ is strongly nonrepetitive. Let $W$ be a
$\phi$-repetitive lazy walk $v_{\\_}1,\ldots,v_{\\_}{2k}$. Our goal is to
prove that $v_{\\_}j=v_{\\_}{j+k}$ for some $j\in\\{1,\ldots,k\\}$. Let $d$ be
the minimum depth of a vertex in $W$.

Let $W^{\prime}$ be the sequence of vertices obtained from $W$ by removing all
vertices at depth greater than $d$. We claim that $W^{\prime}$ is a lazy walk.
To see this, consider vertices $v_{\\_}i,v_{\\_}{i+1},\ldots,v_{\\_}{i+t}$ of
$W$ such that $v_{\\_}i$ and $v_{\\_}{i+t}$ have depth $d$ but
$v_{\\_}{i+1},\ldots,v_{\\_}{i+t-1}$ all have depth greater than $d$; thus,
$v_{\\_}{i+1},\ldots,v_{\\_}{i+t-1}$ were removed when constructing
$W^{\prime}$. Then, the vertices $v_{\\_}{i+1},\ldots,v_{\\_}{i+t-1}$ lie in a
connected component of the graph induced by the vertices of depth greater than
$d$, thus it follows that $v_{\\_}i$ and $v_{\\_}{i+t}$ are adjacent or equal
by Lemma 5. This shows that $W^{\prime}$ is a lazy walk in $G[V_{\\_}d]$.

The projection of $W$ on $P$ is a $\phi_{\\_}2$-repetitive lazy walk in $P$,
and is thus boring by Lemma 6. It follows that the vertices $v_{\\_}j$ and
$v_{\\_}{j+k}$ of $W$ have the same depth for every $j\in\\{1,\dots,k\\}$. In
particular, $v_{\\_}j$ was removed from $W^{\prime}$ if and only if
$v_{\\_}{j+k}$ was. Hence, there are indices $1\leqslant
i_{\\_}1<i_{\\_}2<\cdots<i_{\\_}{\ell}\leqslant k$ such that
$W^{\prime}=v_{\\_}{i_{\\_}1},v_{\\_}{i_{\\_}2},\dots,v_{\\_}{i_{\\_}{\ell}},v_{\\_}{i_{\\_}1+k},v_{\\_}{i_{\\_}2+k},\dots,v_{\\_}{i_{\\_}{\ell}+k}$.
Since $W$ is $(\phi_{\\_}1,\phi_{\\_}2)$-repetitive, it follows that
$W^{\prime}$ is also $(\phi_{\\_}1,\phi_{\\_}2)$-repetitive and in particular
$W^{\prime}$ is $\phi_{\\_}1$-repetitive. By the definition of $\phi_{\\_}1$,
there is an index $i_{\\_}r$ such that
$v_{\\_}{i_{\\_}r}=v_{\\_}{i_{\\_}r+k}$, which completes the proof. ∎

###  2.4 Strong Products

The _strong product_ of graphs $A$ and $B$, denoted by $A\boxtimes B$, is the
graph with vertex set $V(A)\times V(B)$, where distinct vertices
$(v,x),(w,y)\in V(A)\times V(B)$ are adjacent if (1) $v=w$ and $xy\in E(B)$,
or (2) $x=y$ and $vw\in E(A)$, or (3) $vw\in E(A)$ and $xy\in E(B)$.
Nonrepetitive colourings of graph products have been studied in [36, 35, 7,
42]. Indeed, Kündgen and Pelsmajer [36] note that their method shows that the
strong product of $k$ paths is nonrepetitively $4^{k}$-colourable, which is a
precursor to the following results.

######  Lemma 8.

Let $H$ be a graph with an $\ell$-colouring $\phi_{\\_}2$ such that every
$\phi_{\\_}2$-repetitive lazy walk is boring. For every graph $G$, we have
$\pi^{*}(G\boxtimes H)\leqslant\ell\,\pi^{*}(G)$.

###### Proof.

Consider a strongly nonrepetitive colouring $\phi_{\\_}1$ of $G$ with
$\pi^{*}(G)$ colours. For any two vertices $u\in V(G)$ and $v\in V(H)$, we
define the colour $\phi(u,v)$ of the vertex $(u,v)\in V(G\boxtimes H)$ by
$\phi(u,v):=(\phi_{\\_}1(u),\phi_{\\_}2(v))$. We claim that this is a strongly
nonrepetitive colouring of $G\boxtimes H$. To see this, consider a
$\phi$-repetitive lazy walk
$W=(u_{\\_}1,v_{\\_}1),\ldots,(u_{\\_}{2k},v_{\\_}{2k})$ in $G\boxtimes H$. By
the definition of the strong product and the definition of $\phi$, the
projection $W_{\\_}G=u_{\\_}1,u_{\\_}2,\ldots,u_{\\_}{2k}$ of $W$ on $G$ is a
$\phi_{\\_}1$-repetitive lazy walk in $G$ and the projection
$W_{\\_}H=v_{\\_}1,v_{\\_}2,\ldots,v_{\\_}{2k}$ of $W$ on $H$ is a
$\phi_{\\_}2$-repetitive lazy walk in $H$. By the definition of $\phi_{\\_}1$,
there is an index $i$ such that $u_{\\_}i=u_{\\_}{i+k}$. By the definition of
$\phi_{\\_}2$, we have $v_{\\_}j=v_{\\_}{j+k}$ for every
$j\in\\{1,\dots,k\\}$. In particular, $v_{\\_}i=v_{\\_}{i+k}$ and
$(u_{\\_}i,v_{\\_}i)=(u_{\\_}{i+k},v_{\\_}{i+k})$, which completes the proof.
∎

Applying Lemma 6, we obtain the following immediate corollary.

######  Corollary 9.

For every graph $G$ and every path $P$, we have $\pi^{*}(G\boxtimes
P)\leqslant 4\pi^{*}(G)$.

By taking $H=K_{\\_}\ell$ and a proper $\ell$-colouring $\phi_{\\_}2$ of
$K_{\\_}\ell$, we obtain the following corollary of Lemma 8.

######  Corollary 10.

For every graph $G$ and every integer $\ell\geqslant 1$, we have
$\pi^{*}(G\boxtimes K_{\\_}{\ell})\leqslant\ell\,\pi^{*}(G)$.

##  3 Planar Graphs and Graphs of Bounded Genus

The following recent result by Dujmović et al. [18] is a key theorem.

######  Theorem 11 ([18]).

Every planar graph is a subgraph of $H\boxtimes P\boxtimes K_{\\_}{3}$ for
some graph $H$ with treewidth at most $3$ and some path $P$.

Corollaries 9, 7 and 11 imply that for every planar graph $G$,

$\pi(G)\leqslant\pi^{*}(G)\leqslant\pi^{*}(H\boxtimes P\boxtimes
K_{\\_}{3})\leqslant 3\,\pi^{*}(H\boxtimes P)\leqslant 3\cdot
4\,\pi^{*}(H)\leqslant 3\cdot 4\cdot 4^{3}=768,$

which proves Theorem 1.

For graphs of bounded Euler genus, Dujmović et al. [18] proved the following
strengthening of Theorem 11.

######  Theorem 12 ([18]).

Every graph $G$ of Euler genus $g$ is a subgraph of $H\boxtimes P\boxtimes
K_{\\_}{\max\\{2g,3\\}}$ for some graph $H$ with treewidth at most $3$ and
some path $P$.

Corollaries 9, 7 and 12 imply that for every graph $G$ with Euler genus $g$,

$\displaystyle\pi(G)\leqslant\pi^{*}(G)\leqslant\pi^{*}(H\boxtimes P\boxtimes
K_{\\_}{\max\\{2g,3\\}})\leqslant\max\\{2g,3\\}\cdot\pi^{*}(H\boxtimes P)$
$\displaystyle\leqslant\max\\{2g,3\\}\cdot 4\cdot\pi^{*}(H)$
$\displaystyle\leqslant\max\\{2g,3\\}\cdot 4^{4}$
$\displaystyle=256\max\\{2g,3\\},$

which proves Theorem 2.

##  4 Excluded Minors

Our results for graphs excluding a minor depend on the following version of
the graph minor structure theorem of Robertson and Seymour [47]. A tree-
decomposition $(B_{\\_}x:x\in V(T))$ of a graph $G$ is _$r$ -rich_ if
$B_{\\_}x\cap B_{\\_}y$ is a clique in $G$ on at most $r$ vertices, for each
edge $xy\in E(T)$.

######  Theorem 13 ([20]).

For every graph $X$, there are integers $r\geqslant 1$ and $k\geqslant 1$ such
that every $X$-minor-free graph $G_{\\_}0$ is a spanning subgraph of a graph
$G$ that has an $r$-rich tree-decomposition such that each bag induces a
$k$-almost-embeddable subgraph of $G$.

We omit the definition of $k$-almost embeddable from this paper, since we do
not need it. All we need to know is the following theorem of Dujmović et al.
[18], where $A+B$ is the complete join of graphs $A$ and $B$.

######  Theorem 14 ([18]).

Every $k$-almost embeddable graph is a subgraph of $K_{\\_}k+(H\boxtimes
P\boxtimes K_{\\_}{\max\\{6k,1\\}})$ for some graph $H$ with treewidth at most
$11k+10$.

Observe that $\pi^{*}(G+K_{\\_}k)=\pi^{*}(G)+k$ for every graph $G$ and
integer $k\geqslant 0$. Thus Theorems 14, 9 and 7 imply that for every
$k$-almost embeddable graph $G$,

$\pi(G)\leqslant\pi^{*}(G)\leqslant\pi^{*}(K_{\\_}k+(H\boxtimes P\boxtimes
K_{\\_}{\max\\{6k,1\\}}))\leqslant k+6k\,\pi^{*}(H\boxtimes P)\leqslant
k+6k\cdot 4\pi^{*}(H)\leqslant k+6k\cdot 4^{11(k+1)}.$ (1)

Dujmović et al. [20] proved the following lemma, which generalises a result of
Kündgen and Pelsmajer [36].

######  Lemma 15 ([20]).

Let $G$ be a graph that has an $r$-rich tree-decomposition such that the
subgraph induced by each bag is nonrepetitively $c$-colourable. Then
$\pi(G)\leqslant c\,4^{r}$.

Theorems 13 and 15 and (1) with $c=k+6k\cdot 4^{11(k+1)}$ imply that for every
graph $X$ and every $X$-minor-free graph $G$,

$\pi(G)\leqslant\pi^{*}(G)\leqslant(k+6k\cdot 4^{11(k+1)})4^{r},$

which implies Theorem 3 since $k$ and $r$ depend only on $X$.

To obtain our result for graphs excluding a fixed topological minor, we use
the following version of the structure theorem of Grohe and Marx [24].

######  Theorem 16 ([20]).

For every graph $X$, there are integers $r\geqslant 1$ and $k\geqslant 1$ such
that every $X$-topological-minor-free graph $G_{\\_}0$ is a spanning subgraph
of a graph $G$ that has an $r$-rich tree-decomposition such that the subgraph
induced by each bag is $k$-almost-embeddable or has at most $k$ vertices with
degree greater than $k$.

Alon et al. [3] proved that graphs with maximum degree $\Delta$ are
nonrepetitively $O(\Delta^{2})$-colourable. The best known bound is due to
Dujmović et al. [17].

######  Theorem 17 ([17]).

Every graph with maximum degree $\Delta\geqslant 2$ is nonrepetitively
$(\Delta^{2}+O(\Delta^{5/3}))$-colourable.

Theorem 17 implies that if a graph has at most $k$ vertices with degree
greater than $k$, then it is nonrepetitively $c^{\prime}$-colourable for some
constant $c^{\prime}=k^{2}+O(k^{5/3})+k$. Theorems 16 and 15 and (1) with
$c=\max\\{k+6k\cdot 4^{11(k+1)},c^{\prime}\\}$ imply that for every graph $X$,
every $X$-topological-minor-free graph $G$ satisfies
$\pi(G)\leqslant\pi^{*}(G)\leqslant c\cdot 4^{r}$, which implies Theorem 4,
since $c$ and $r$ depend only on $X$.

## Acknowledgements

This research was completed at the Workshop on Graph Theory held at Bellairs
Research Institute in April 2019. Thanks to the other workshop participants
for creating a productive working atmosphere. Thanks to André Kündgen and
Jarosław Grytczuk for helpful comments on an early draft.

## References

  * Alon and Grytczuk [2005] Noga Alon and Jarosław Grytczuk.  Nonrepetitive colorings of graphs.  _Electronic Notes in Discrete Math._ , 22:353–355, 2005.  10.1016/j.endm.2005.06.077.
  * Alon and Grytczuk [2008] Noga Alon and Jarosław Grytczuk.  Breaking the rhythm on graphs.  _Discrete Math._ , 308:1375–1380, 2008.  10.1016/j.disc.2007.07.063.  MR: https://www.ams.org/mathscinet-getitem?mr=MR23920542392054.
  * Alon et al. [2002] Noga Alon, Jarosław Grytczuk, Mariusz Hałuszczak, and Oliver Riordan.  Nonrepetitive colorings of graphs.  _Random Structures Algorithms_ , 21(3–4):336–346, 2002.  10.1002/rsa.10057.  MR: https://www.ams.org/mathscinet-getitem?mr=MR19453731945373.
  * Barát and Czap [2013] János Barát and Július Czap.  Facial nonrepetitive vertex coloring of plane graphs.  _J. Graph Theory_ , 74(1):115–121, 2013.  10.1002/jgt.21695.
  * Barát and Varjú [2007] János Barát and Péter P. Varjú.  On square-free vertex colorings of graphs.  _Studia Sci. Math. Hungar._ , 44(3):411–422, 2007.  10.1556/SScMath.2007.1029.  MR: https://www.ams.org/mathscinet-getitem?mr=MR23616852361685.
  * Barát and Varjú [2008] János Barát and Péter P. Varjú.  On square-free edge colorings of graphs.  _Ars Combin._ , 87:377–383, 2008.  MR: https://www.ams.org/mathscinet-getitem?mr=MR24140292414029.
  * Barát and Wood [2008] János Barát and David R. Wood.  Notes on nonrepetitive graph colouring.  _Electron. J. Combin._ , 15:R99, 2008.  https://doi.org/10.37236/823.  MR: https://www.ams.org/mathscinet-getitem?mr=MR24261622426162.
  * Bose et al. [2017] Prosenjit Bose, Vida Dujmović, Pat Morin, and Lucas Rioux-Maldague.  New bounds for facial nonrepetitive colouring.  _Graphs Combin._ , 33(4):817–832, 2017.  10.1007/s00373-017-1816-1.
  * Brešar et al. [2007] Boštjan Brešar, Jarosław Grytczuk, Sandi Klavžar, Stanisław Niwczyk, and Iztok Peterin.  Nonrepetitive colorings of trees.  _Discrete Math._ , 307(2):163–172, 2007.  10.1016/j.disc.2006.06.017.  MR: https://www.ams.org/mathscinet-getitem?mr=MR22851862285186.
  * Brešar and Klavžar [2004] Boštjan Brešar and Sandi Klavžar.  Square-free colorings of graphs.  _Ars Combin._ , 70:3–13, 2004.  MR: https://www.ams.org/mathscinet-getitem?mr=MR20230572023057.
  * Cheilaris et al. [2010] Panagiotis Cheilaris, Ernst Specker, and Stathis Zachos.  Neochromatica.  _Comment. Math. Univ. Carolin._ , 51(3):469–480, 2010.  http://www.dml.cz/dmlcz/140723.  MR: https://www.ams.org/mathscinet-getitem?mr=MR27418802741880.
  * Currie [2002] James D. Currie.  There are ternary circular square-free words of length $n$ for $n\geqslant 18$.  _Electron. J. Combin._ , 9(1):#N10, 2002.  https://doi.org/10.37236/1671.  MR: https://www.ams.org/mathscinet-getitem?mr=MR19368651936865.
  * Currie [2005] James D. Currie.  Pattern avoidance: themes and variations.  _Theoret. Comput. Sci._ , 339(1):7–18, 2005.  10.1016/j.tcs.2005.01.004.  MR: https://www.ams.org/mathscinet-getitem?mr=MR21420702142070.
  * Czerwiński and Grytczuk [2007] Sebastian Czerwiński and Jarosław Grytczuk.  Nonrepetitive colorings of graphs.  _Electronic Notes in Discrete Math._ , 28:453–459, 2007.  10.1016/j.endm.2007.01.063.  MR: https://www.ams.org/mathscinet-getitem?mr=MR23240512324051.
  * Diestel [2010] Reinhard Diestel.  _Graph theory_ , vol. 173 of _Graduate Texts in Mathematics_.  Springer, 4th edn., 2010.  http://diestel-graph-theory.com/.  MR: https://www.ams.org/mathscinet-getitem?mr=MR27448112744811.
  * Dujmović et al. [2013] Vida Dujmović, Fabrizio Frati, Gwenaël Joret, and David R. Wood.  Nonrepetitive colourings of planar graphs with ${O}(\log n)$ colours.  _Electron. J. Combin._ , 20(1):#P51, 2013.  https://doi.org/10.37236/3153.
  * Dujmović et al. [2016] Vida Dujmović, Gwenaël Joret, Jakub Kozik, and David R. Wood.  Nonrepetitive colouring via entropy compression.  _Combinatorica_ , 36(6):661–686, 2016.  10.1007/s00493-015-3070-6.
  * Dujmović et al. [2019] Vida Dujmović, Gwenaël Joret, Piotr Micek, Pat Morin, Torsten Ueckerdt, and David R. Wood.  Planar graphs have bounded queue-number.  In _Proc. 60th Annual Symp. Foundations Comput. Sci._ (FOCS ’19), pp. 862–875. 2019.  10.1109/FOCS.2019.00056.  To appear in _J. ACM_ , arXiv: https://arxiv.org/abs/1904.047911904.04791.
  * Dujmović et al. [2005] Vida Dujmović, Pat Morin, and David R. Wood.  Layout of graphs with bounded tree-width.  _SIAM J. Comput._ , 34(3):553–579, 2005.  10.1137/S0097539702416141.  MR: https://www.ams.org/mathscinet-getitem?mr=MR21370792137079.
  * Dujmović et al. [2017] Vida Dujmović, Pat Morin, and David R. Wood.  Layered separators in minor-closed graph classes with applications.  _J. Combin. Theory Ser. B_ , 127:111–147, 2017.  10.1016/j.jctb.2017.05.006.  MR: https://www.ams.org/mathscinet-getitem?mr=MR37046583704658.
  * Fiorenzi et al. [2011] Francesca Fiorenzi, Pascal Ochem, Patrice Ossona de Mendez, and Xuding Zhu.  Thue choosability of trees.  _Discrete Applied Math._ , 159(17):2045–2049, 2011.  10.1016/j.dam.2011.07.017.  MR: https://www.ams.org/mathscinet-getitem?mr=MR28323292832329.
  * Gagol et al. [2016] Adam Gagol, Gwenaël Joret, Jakub Kozik, and Piotr Micek.  Pathwidth and nonrepetitive list coloring.  _Electron. J. Comb._ , 23(4):P4.40, 2016.  https://doi.org/10.37236/5855.
  * Gonçalves et al. [2014] Daniel Gonçalves, Mickaël Montassier, and Alexandre Pinlou.  Entropy compression method applied to graph colorings, 2014.  arXiv: https://arxiv.org/abs/1406.43801406.4380.
  * Grohe and Marx [2015] Martin Grohe and Dániel Marx.  Structure theorem and isomorphism test for graphs with excluded topological subgraphs.  _SIAM J. Comput._ , 44(1):114–159, 2015.  10.1137/120892234.  MR: https://www.ams.org/mathscinet-getitem?mr=MR33135693313569.
  * Grytczuk [2002] Jarosław Grytczuk.  Thue-like sequences and rainbow arithmetic progressions.  _Electron. J. Combin._ , 9(1):R44, 2002.  https://doi.org/10.37236/1660.  MR: https://www.ams.org/mathscinet-getitem?mr=MR19461461946146.
  * Grytczuk [2004] Jarosław Grytczuk.  Thue type colorings of graphs.  In _Graph Theory 2004: A conference in memory of Claude Berge_. 2004\.
  * Grytczuk [2007] Jarosław Grytczuk.  Nonrepetitive colorings of graphs—a survey.  _Int. J. Math. Math. Sci._ , 74639, 2007.  10.1155/2007/74639.  MR: https://www.ams.org/mathscinet-getitem?mr=MR22723382272338.
  * Grytczuk [2008] Jarosław Grytczuk.  Thue type problems for graphs, points, and numbers.  _Discrete Math._ , 308(19):4419–4429, 2008.  10.1016/j.disc.2007.08.039.  MR: https://www.ams.org/mathscinet-getitem?mr=MR24337692433769.
  * Grytczuk et al. [2016] Jarosław Grytczuk, Karol Kosiński, and Michał Zmarz.  Nonrepetitive colorings of line arrangements.  _Eur. J. Combin._ , 51:275–279, 2016.  10.1016/j.ejc.2015.05.013.
  * Grytczuk et al. [2013] Jarosław Grytczuk, Jakub Kozik, and Piotr Micek.  A new approach to nonrepetitive sequences.  _Random Structures Algorithms_ , 42(2):214–225, 2013.  10.1002/rsa.20411.
  * Grytczuk et al. [2011] Jarosław Grytczuk, Jakub Przybyło, and Xuding Zhu.  Nonrepetitive list colourings of paths.  _Random Structures Algorithms_ , 38(1-2):162–173, 2011.  10.1002/rsa.20347.  MR: https://www.ams.org/mathscinet-getitem?mr=MR27688882768888.
  * Haranta and Jendro’l [2012] Jochen Haranta and Stanislav Jendro’l.  Nonrepetitive vertex colorings of graphs.  _Discrete Math._ , 312(2):374–380, 2012.  10.1016/j.disc.2011.09.027.  MR: https://www.ams.org/mathscinet-getitem?mr=MR28525952852595.
  * Havet et al. [2011] Frédéric Havet, Stanislav Jendro’l, Roman Soták, and Erika Škrabu’láková.  Facial non-repetitive edge-coloring of plane graphs.  _J. Graph Theory_ , 66(1):38–48, 2011.  10.1002/jgt.20488.
  * Jendro’l and Škrabu’láková [2009] Stanislav Jendro’l and Erika Škrabu’láková.  Facial non-repetitive edge colouring of semiregular polyhedra.  _Acta Univ. M. Belii Ser. Math._ , 15:37–52, 2009.  http://actamath.savbb.sk/acta1503.shtml.  MR: https://www.ams.org/mathscinet-getitem?mr=MR25896692589669.
  * Keszegh et al. [2014] Balázs Keszegh, Balázs Patkós, and Xuding Zhu.  Nonrepetitive colorings of lexicographic product of graphs.  _Discrete Math. Theor. Comput. Sci._ , 16(2):97–110, 2014.  http://dmtcs.episciences.org/2077.
  * Kündgen and Pelsmajer [2008] André Kündgen and Michael J. Pelsmajer.  Nonrepetitive colorings of graphs of bounded tree-width.  _Discrete Math._ , 308(19):4473–4478, 2008.  10.1016/j.disc.2007.08.043.  MR: https://www.ams.org/mathscinet-getitem?mr=MR24337742433774.
  * Kündgen and Talbot [2017] André Kündgen and Tonya Talbot.  Nonrepetitive edge-colorings of trees.  _Discrete Math. Theor. Comput. Sci._ , 19(1), 2017.  http://dmtcs.episciences.org/3724.
  * Marx and Schaefer [2009] Dániel Marx and Marcus Schaefer.  The complexity of nonrepetitive coloring.  _Discrete Appl. Math._ , 157(1):13–18, 2009.  10.1016/j.dam.2008.04.015.  MR: https://www.ams.org/mathscinet-getitem?mr=MR24793742479374.
  * Mohar and Thomassen [2001] Bojan Mohar and Carsten Thomassen.  _Graphs on surfaces_.  Johns Hopkins University Press, 2001.  MR: https://www.ams.org/mathscinet-getitem?mr=MR18444491844449.
  * Nešetřil et al. [2011] Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R. Wood.  Characterisations and examples of graph classes with bounded expansion.  _Eur. J. Combin._ , 33(3):350–373, 2011.  10.1016/j.ejc.2011.09.008.  MR: https://www.ams.org/mathscinet-getitem?mr=MR28644212864421.
  * Pegden [2011] Wesley Pegden.  Highly nonrepetitive sequences: winning strategies from the local lemma.  _Random Structures Algorithms_ , 38(1-2):140–161, 2011.  10.1002/rsa.20354.  MR: https://www.ams.org/mathscinet-getitem?mr=MR27688872768887.
  * Peterin et al. [2018] Iztok Peterin, Jens Schreyer, Erika Fecková Škrabu’láková, and Andrej Taranenko.  A note on the Thue chromatic number of lexicographic products of graphs.  _Discuss. Math. Graph Theory_ , 38(3):635–643, 2018.  10.7151/dmgt.2032.  MR: https://www.ams.org/mathscinet-getitem?mr=MR38119583811958.
  * Pezarski and Zmarz [2009] Andrzej Pezarski and Michał Zmarz.  Non-repetitive 3-coloring of subdivided graphs.  _Electron. J. Combin._ , 16(1):N15, 2009.  https://doi.org/10.37236/253.  MR: https://www.ams.org/mathscinet-getitem?mr=MR25157552515755.
  * Przybyło [2014] Jakub Przybyło.  On the facial Thue choice index via entropy compression.  _J. Graph Theory_ , 77(3):180–189, 2014.  10.1002/jgt.21781.
  * Przybyło et al. [2016] Jakub Przybyło, Jens Schreyer, and Erika Škrabu’láková.  On the facial Thue choice number of plane graphs via entropy compression method.  _Graphs Combin._ , 32(3):1137–1153, 2016.  10.1007/s00373-015-1642-2.
  * Robertson and Seymour [1986] Neil Robertson and Paul Seymour.  Graph minors. II. Algorithmic aspects of tree-width.  _J. Algorithms_ , 7(3):309–322, 1986.  10.1016/0196-6774(86)90023-4.  MR: https://www.ams.org/mathscinet-getitem?mr=MR08555590855559.
  * Robertson and Seymour [2003] Neil Robertson and Paul Seymour.  Graph minors. XVI. Excluding a non-planar graph.  _J. Combin. Theory Ser. B_ , 89(1):43–76, 2003.  10.1016/S0095-8956(03)00042-X.  MR: https://www.ams.org/mathscinet-getitem?mr=MR19997361999736.
  * Schreyer and Škrabu’láková [2012] Jens Schreyer and Erika Škrabu’láková.  On the facial Thue choice index of plane graphs.  _Discrete Math._ , 312(10):1713–1721, 2012.  10.1016/j.disc.2012.01.023.
  * Schreyer and Škrabu’láková [2015] Jens Schreyer and Erika Škrabu’láková.  Total Thue colourings of graphs.  _Eur. J. Math._ , 1(1):186–197, 2015.  10.1007/s40879-014-0016-2.  MR: https://www.ams.org/mathscinet-getitem?mr=MR33862333386233.
  * Škrabu’láková [2015] Erika Škrabu’láková.  The Thue choice number versus the Thue chromatic number of graphs, 2015.  arXiv: https://arxiv.org/abs/1508.025591508.02559.
  * Thue [1906] Axel Thue.  Über unendliche Zeichenreihen.  _Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania_ , 7:1–22, 1906\.
  * Wenus and Wesek [2016] Przemysław Wenus and Krzysztof Wesek.  Nonrepetitive and pattern-free colorings of the plane.  _Eur. J. Combin._ , 54:21–34, 2016.  10.1016/j.ejc.2015.12.002.
  * Wollan and Wood [2019] Paul Wollan and David R. Wood.  Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor.  _J. Graph Theory_ , 91(3):259–266, 2019.  10.1002/jgt.22430.
  * Zhao and Zhu [2016] Huanhua Zhao and Xuding Zhu.  (2+$\epsilon$)-nonrepetitive list colouring of paths.  _Graphs Combin._ , 32(4):1635–1640, 2016.  10.1007/s00373-015-1652-0.

[vd] Vida Dujmović
School of Computer Science and Electrical Engineering
University of Ottawa
Ottawa, Canada
<EMAIL_ADDRESS>
http://cglab.ca/ vida/ [le] Louis Esperet
Laboratoire G-SCOP
(CNRS, Univ. Grenoble Alpes)
Grenoble, France
<EMAIL_ADDRESS>
https://oc.g-scop.grenoble-inp.fr/esperet/ [gj] Gwenaël Joret
Département d’Informatique
Université Libre de Bruxelles
Brussels, Belgium
<EMAIL_ADDRESS>
http://di.ulb.ac.be/algo/gjoret/ [bw] Bartosz Walczak
Department of Theoretical Computer Science
Faculty of Mathematics and Computer Science
Jagiellonian University
Kraków, Poland
<EMAIL_ADDRESS>
http://www.tcs.uj.edu.pl/walczak [dw] David R. Wood
School of Mathematics
Monash University
Melbourne, Australia
<EMAIL_ADDRESS>
http://users.monash.edu/ davidwo/