# Defective and Clustered Colouring
of Graphs with Given Girth

Marcin Briański 333Department of Theoretical Computer Science, Jagiellonian
University, Kraków, Poland (marcin.brianski@doctoral.uj.edu.pl). M. Briański
was partially supported by a Polish National Science Center grant (BEETHOVEN;
UMO-2018/31/G/ST1/03718). Robert Hickingbotham 222School of Mathematics,
Monash University, Melbourne, Australia ({robert.hickingbotham,
david.wood}@monash.edu). Research of Wood supported by the Australian Research
Council. Research of Hickingbotham supported by Australian Government Research
Training Program Scholarship. David R. Wood 222School of Mathematics, Monash
University, Melbourne, Australia ({robert.hickingbotham,
david.wood}@monash.edu). Research of Wood supported by the Australian Research
Council. Research of Hickingbotham supported by Australian Government Research
Training Program Scholarship.

###### Abstract

The _defective chromatic number_ of a graph class $\mathcal{G}$ is the minimum
integer $k$ such that for some integer $d$, every graph in $\mathcal{G}$ is
$k$-colourable such that each monochromatic component has maximum degree at
most $d$. Similarly, the _clustered chromatic number_ of a graph class
$\mathcal{G}$ is the minimum integer $k$ such that for some integer $c$, every
graph in $\mathcal{G}$ is $k$-colourable such that each monochromatic
component has at most $c$ vertices. This paper determines or establishes
bounds on the defective and clustered chromatic numbers of graphs with given
girth in minor-closed classes defined by the following parameters: Hadwiger
number, treewidth, pathwidth, treedepth, circumference, and feedback vertex
number. One striking result is that for any integer $k$, for the class of
triangle-free graphs with treewidth $k$, the defective chromatic number,
clustered chromatic number and chromatic number are all equal. The same result
holds for graphs with treedepth $k$, and generalises for graphs with no
$K_{\\_}p$ subgraph. We also show, via a result of Kühn and Osthus [2003],
that $K_{\\_}t$-minor-free graphs with girth $g\geqslant 5$ are properly
$O(t^{c_{\\_}g})$ colourable, where $c_{\\_}g\in(0,1)$ with $c_{\\_}g\to 0$,
thus asymptotically improving on Hadwiger’s Conjecture.

##  1 Introduction

This paper studies improper colourings of graphs in minor-closed classes with
given girth. First, we give the essential definitions. A _colouring_ of a
graph111We consider simple, finite, undirected graphs $G$ with vertex-set
${V(G)}$ and edge-set ${E(G)}$. See latter sections and [11] for graph-
theoretic definitions not given here. $G$ is a function that assigns one
colour to each vertex of $G$. For an integer $k\geqslant 1$, a _$k$
-colouring_ is a colouring using at most $k$ colours. A colouring of a graph
is _proper_ if each pair of adjacent vertices receives distinct colours. The
_chromatic number $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(G)$_ of a graph
$G$ is the minimum integer $k$ such that $G$ has a proper $k$-colouring. For a
graph class $\mathcal{G}$, the _chromatic number
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{G})$_ is
$\max\\{\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(G):G\in\mathcal{G}\\}$, and
is _unbounded_ if the maximum does not exist. A _monochromatic component_ with
respect to a colouring of a graph $G$ is a connected component of the subgraph
of $G$ induced by all the vertices assigned a single colour. A colouring has
_defect_ $d$ if every monochromatic component has maximum degree at most $d$.
A colouring has _clustering_ $c$ if every monochromatic component has at most
$c$ vertices. Note that a colouring with defect 0 or clustering 1 is precisely
a proper colouring. The _defective chromatic number
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})$_ of a graph
class $\mathcal{G}$ is the minimum integer $k$ for which there exists an
integer $d$ such that every graph in $\mathcal{G}$ is $k$-colourable with
defect $d$, and is _unbounded_ if no such $k$ exists. The _clustered chromatic
number $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})$_ of a
graph class $\mathcal{G}$ is the minimum integer $k$ for which there exists an
integer $c$ such that every graph in $\mathcal{G}$ is $k$-colourable with
clustering $c$, and is _unbounded_ if no such $k$ exists. By definition,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{G})$.
See [74] for an extensive survey on this topic.

We consider defective and clustered colouring of graphs with given girth,
where our aim is to minimise the number of colours rather than attain specific
defect or clustering bounds222Other papers that focus on specific defect or
clustering bounds for graphs of given girth include [7, 72, 62, 71, 6].. First
note that for any integer $g$, the class of graphs with girth at least $g$ has
unbounded defective chromatic number. To see this, suppose that for some $g$
and $k$, the class of graphs with girth at least $g$ has defective chromatic
number at most $k$. That is, for some $d$, every graph $G$ with girth at least
$g$ is $k$-colourable with defect at most $d$. Each monochromatic component is
properly $(d+1)$-colourable, so $G$ is properly $k(d+1)$-colourable. This
contradicts the result of Erdős [21], which states that graphs with girth $g$
have unbounded chromatic number. Hence the class of graphs with girth at least
$g$ has unbounded defective chromatic number, and thus has unbounded clustered
chromatic number. This negative result motivates studying defective and
clustered colourings of graphs with given girth and satisfying some other
structural assumptions. To obtain interesting results, it is not enough to
just consider degeneracy, since Kostochka and Nešetřil [38, Property 6] proved
that for all $k,d,g$ there is a $k$-degenerate graph with girth at least $g$
that is not $k$-colourable with defect $d$. Thus chromatic number, defective
chromatic number and clustered chromatic number of the class of $k$-degenerate
graphs with girth $g$ equals $k+1$.

Here we focus on minor-closed graph classes. Defective and clustered
colourings of graphs excluding a fixed minor are widely studied [14, 59, 44,
31, 56, 70, 47, 46, 48, 49, 30, 73, 20, 45, 29, 17, 57, 58, 7]. We focus on
the following minor-monotone parameters: treewidth $\operatorname{tw}(G)$,
pathwidth $\operatorname{pw}(G)$, treedepth $\operatorname{td}(G)$, feedback
vertex number $\operatorname{fvn}(G)$, circumference $\operatorname{circ}(G)$,
and Hadwiger number $\operatorname{had}(G)$. See Section 2 for these well-
known definitions. For now, note the following inequalities:

$\displaystyle\operatorname{had}(G)-1\leqslant\operatorname{tw}(G)$
$\displaystyle\leqslant\operatorname{pw}(G)\leqslant\operatorname{td}(G)-1$
(1) $\displaystyle\operatorname{had}(G)-1\leqslant\operatorname{tw}(G)$
$\displaystyle\leqslant\operatorname{fvn}(G)+1$ (2)
$\displaystyle\operatorname{had}(G)-1\leqslant\operatorname{tw}(G)$
$\displaystyle\leqslant\operatorname{circ}(G)-1.$ (3)

###  1.1 Defective Colouring of Bounded Treewidth Graphs

Here we summarise results on defective colouring of minor-closed graph
classes; refer to Tables 1 and 2. Original results in this paper are indicated
by $\ast$.

Table 1: Defective chromatic number of bounded treewidth classes with respect
to girth (ignoring lower order additive terms).

girth fvn $k$ circumference $k$ treedepth $k$ pathwidth $k$ treewidth $k$ 3
$3^{\ast}$ $\Theta(\log k)$ $k$ $k+1$ $k+1$ 4 $3^{\ast}$ $\Theta(\log
k)^{\ast}$ $\sqrt{2k}^{\ast},\dots,\lceil\frac{k+2}{2}\rceil^{\ast}$
$\sqrt{2k}^{\ast},\dots,\lceil\frac{k+3}{2}\rceil^{\ast}$
$\lceil\frac{k+3}{2}\rceil^{\ast}$ $\geqslant 5$ 2 2 2 2 2

First consider the case with no girth constraint (girth 3). Graphs with
treewidth $k$ are $k$-degenerate and thus properly $(k+1)$-colourable. This
implies that graphs with pathwidth $k$ are $(k+1)$-colourable, and graphs with
treedepth $k$ are properly $k$-colourable. Standard examples (see Section 3.1
and [74]) show that these bounds cannot be improved for defective or clustered
colouring. Mohar et al. [53] showed that graphs with circumference $k$ are
$O(\log k)$-colourable with clustering $k$, and thus with defect $k-1$. The
number of colours is tight up to the leading constant. Thus the defective and
clustered chromatic number of the class of graphs with circumference $k$ is in
$\Theta(\log k)$. Every graph $G$ with $\operatorname{fvn}(G)\leqslant k$ is
3-colourable with clustering $k$ and defect $k-1$: just properly 2-colour the
underlying forest and give a third colour to each apex vertex. Proposition 15
shows that three colours is best possible even for feedback vertex number 1.
Thus for each integer $k\geqslant 1$, the clustered and defective chromatic
number of the class of graphs $G$ with $\operatorname{fvn}(G)\leqslant k$
equals 3.

Now consider the triangle-free case (girth 4). Dvořák and Kawarabayashi [18]
proved the following important result.

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

For any $k\in\mathbb{N}$ the chromatic number of the class of triangle-free
graphs with treewidth $k$ equals $\lceil\frac{k+3}{2}\rceil$.

We extend their lower bound to prove that for the class of triangle-free
graphs with treewidth $k$, the defective chromatic number, the clustered
chromatic number, and the chromatic number all equal
$\lceil\frac{k+3}{2}\rceil$ (see Corollary 14 which in fact holds for any
fixed excluded complete subgraph). We prove the following similar result for
treedepth: for the class of triangle-free graphs with treedepth $k$, the
defective chromatic number, the clustered chromatic number, and the proper
chromatic number are all equal, and this value is between $(1-o(1))\sqrt{2k}$
and $\lceil\frac{k+2}{2}\rceil$ (see Corollary 11). The lower bound for
triangle-free graphs with treedepth $k$ also leads to a $\Omega(\log k)$ lower
bound for triangle-free graphs with circumference $k$ (see Corollary 12). So
the defective and clustered chromatic number of the class of triangle-free
graphs with circumference $k$ is in $\Theta(\log k)$. Finally, Proposition 15
shows that three colours is best possible even for triangle-free graphs with
feedback vertex number 1. Thus for each integer $k\geqslant 1$, the clustered
and defective chromatic number of the class of triangle-free graphs $G$ with
$\operatorname{fvn}(G)\leqslant k$ equals 3.

Now consider the girth at least 5 case. The following result of Ossona de
Mendez et al. [59] is paramount. Here $\nabla(G)$ is the maximum average
degree of a graph $H$ such that the 1-subdivision of $H$ is isomorphic to a
subgraph of $G$.

######  Theorem 2 ([59]).

Every $K_{\\_}{s,t}$-subgraph-free graph $G$ is $s$-colourable with defect at
most some function $f(s,t,\nabla(G))$.

We give a short proof of a result that is equivalent to Theorem 2 in Section
4.1.

Every graph with girth at least $5$ contains no $K_{\\_}{2,2}$ subgraph. Thus
Theorem 2 with $s=t=2$ implies that for any graph class $\mathcal{G}$ with
bounded $\nabla$ (which includes every minor-closed class), the graphs in
$\mathcal{G}$ with girth at least 5 are $2$-colourable with bounded defect.
Girth 5 here cannot be reduced to 4, even for graphs with bounded treedepth,
since we prove that the class of triangle-free graphs with treedepth $k$ has
defective chromatic number at least $\Omega(\sqrt{k})$ (see Theorem 10). By
(1), the same result holds with ‘treedepth’ replaced by ‘pathwidth’,
‘treewidth’ or ‘Hadwiger number’. For each of these parameters, there is a
qualitative change in behaviour from girth 4 to 5. For a class of graphs with
girth at least 5 and with any of these parameters bounded, the defective
chromatic number equals 2. On the other hand, for graphs with girth 4, the
defective chromatic number increases with the parameter.

###  1.2 Defective Colouring of General Minor-Closed Classes

Now consider defective colourings of planar graphs and more general minor-
closed classes; the results are summarised in Table 2.

Table 2: Defective chromatic number of minor-closed classes with respect to girth. girth | planar graphs | Euler genus $\gamma$ |  $(\gamma,k)$-apex | Hadwiger number $t$
---|---|---|---|---
3 | $3$ | $3$ | $4$ | $t$
4 | 2 or 3 | 2 or 3 | 2, 3 or 4 | $\lceil\frac{t+2}{2}\rceil^{\ast},\dots,t$
$\geqslant 5$ | $2$ | $2$ | 2 | 2

First consider the case with no girth constraint. Cowen et al. [9] proved that
planar graphs are 3-colourable with defect 2 (see [60, 19, 70] for various
strengthenings). More generally, Archdeacon [2] proved that graphs of Euler
genus $\gamma$ are 3-colourable with defect $O(\gamma)$, and Cowen et al. [8]
improved the defect bound to $O(\sqrt{\gamma})$, which is best possible.
Standard examples provide, for any integer $d\geqslant 0$, a planar graph that
is not 2-colourable with defect $d$ (see [74]). Thus for each integer
$\gamma\geqslant 0$, the defective chromatic number of the class of graphs
with Euler genus $\gamma$ equals $3$.

Now consider apex graphs. For integers $\gamma,k\geqslant 0$, a graph $G$ is
_$(\gamma,k)$ -apex_ if there exists $A\subseteq V(G)$ such that $|A|\leqslant
k$ and $G-A$ has Euler genus at most $\gamma$. A $(0,k)$-apex graph is called
_$k$ -apex_, in which case $G-A$ is planar. Every $(\gamma,k)$-apex graph is
4-colourable with defect $O(\max\\{\sqrt{\gamma},k\\})$: just apply the above
3-colour result for graphs of Euler genus $\gamma$, and use a fourth colour
for the $k$ apex vertices. Standard examples show that four colours is best
possible, even for $(0,1)$-apex graphs (see [74]).

Edwards et al. [20] proved that graphs $G$ with
$\operatorname{had}(G)\leqslant t$ are $t$-colourable with defect $O(t^{2}\log
t)$. Standard examples [74] provide a matching lower bound. Thus the defective
chromatic number of the class of graphs $G$ with
$\operatorname{had}(G)\leqslant t$ equals $t$. The defect bound in the above
result of Edwards et al. [20] was improved to $O(t)$ by van den Heuvel and
Wood [70].

Finally, consider the triangle-free (girth 4) case. Each of the upper bounds
in the triangle-free case of Table 2 follow from the analogous upper bounds
without the triangle-free assumption. The lower bounds of 2 are trivial. The
lower bound of $\lceil\frac{t+2}{2}\rceil$ for graphs with Hadwiger number $t$
follows from the fact that the defective chromatic number of the class of
triangle-free graphs with treewidth $k$ equals $\lceil\frac{k+3}{2}\rceil$ and
since $\operatorname{had}(G)\leqslant\operatorname{tw}(G)+1$ for every graph
$G$.

###  1.3 Clustered Colouring of Bounded Treewidth Graphs

Here we consider clustered colourings of various bounded treewidth graph
classes with respect to girth. Table 3 summarises the results.

Table 3: Clustered chromatic number of bounded treewidth classes with respect
to girth (ignoring lower order additive terms).

girth fvn $k$ circumference $k$ treedepth $k$ pathwidth $k$ treewidth $k$ 3 3
$\Theta(\log k)^{\ast}$ $k$ $k+1$ $k+1$ 4 3 $\Theta(\log k)^{\ast}$
$\sqrt{2k}^{\ast},\dots,\lceil\frac{k+2}{2}\rceil^{\ast}$
$\sqrt{2k}^{\ast},\dots,\lceil\frac{k+3}{2}\rceil^{\ast}$
$\lceil\frac{k+3}{2}\rceil^{\ast}$ 5 or 6 $3^{\ast}$ $2^{\ast}$ 2 3 3
$\geqslant 7$ $2^{\ast}$ 2 2 2 or 3 2 or 3 $\Omega(\log k)$ 2 2 2 $2^{\ast}$
$2^{\ast}$

Liu and Wood [46] proved the following analogue of Theorem 2 for clustered
colouring of bounded treewidth graphs.

######  Theorem 3 ([46]).

For any $s,t,k\in\mathbb{N}$, every $K_{\\_}{s,t}$-subgraph-free graph of
treewidth at most $k$ is $(s+1)$-colourable with clustering at most some
function $f(s,t,k)$.

As before, Theorem 3 with $s=t=2$ implies every graph with girth at least 5
and with treewidth at most $k$ is 3-colourable with clustering at most some
function $f(k)$. In both Theorems 3 and 4 the number of colours is best
possible, but the extremal examples have many triangles.

Consider the triangle-free case (girth 4). As mentioned above, we extend
Theorem 1 to show that the clustered chromatic number of triangle-free graphs
with treewidth $k$ equals $\lceil\frac{k+3}{2}\rceil$. This implies the same
upper bound for triangle-free graphs with pathwidth $k$, and an upper bound of
$\lceil\frac{k+2}{2}\rceil$ for triangle-free graphs with treedepth $k$. As
mentioned above, Mohar et al. [53] showed that graphs with circumference $k$
are $O(\log k)$-colourable with clustering $k$. We show that this bound on the
number of colours is best possible even for triangle-free graphs (see
Corollary 12). Thus the clustered chromatic number of the class of triangle-
free graphs with circumference $k$ is in $\Theta(\log k)$. For triangle-free
graphs with $\operatorname{fvn}(G)\leqslant k$ the upper bound of 3 is best
possible, even for $k=1$ (see Proposition 15).

Now consider the case of girth at least 5. Theorem 2 implies that graphs with
girth at least 5 and with bounded treedepth are 2-colourable with bounded
clustering, since in a graph of bounded treedepth, every path has bounded
length (see [55]). This observation in fact implies that for every graph class
$\mathcal{G}$ with bounded treedepth,
$\chi_{\\_}*(\mathcal{G})=\chi_{\\_}\Delta(\mathcal{G})$. Similarly, we
improve the number of colours from 3 to 2 in the case of graphs with girth at
least 5 and circumference $k$ (see Theorem 19), and in the case of graphs with
girth at least 7 and feedback vertex number $k$ (see Theorem 21). The upper
bound of 2 for graphs with treewidth $k$ and girth $\Omega(\log k)$ in Table 3
follows from our more general results for graphs with Hadwiger number $t$ and
with girth $\Omega(\log t)$ (see Section 5).

###  1.4 Clustered Colouring of General Minor-Closed Classes

Here we consider clustered colourings of various minor-closed graph classes
(with unbounded treewidth) with respect to girth. Table 4 summarises the
results.

Table 4: Clustered chromatic number of minor-closed classes with respect to girth. girth | planar graphs | Euler genus $\gamma$ |  $(\gamma,k)$-apex | Hadwiger number $t$
---|---|---|---|---
3 | $4$ | $4$ | $5$ | $t$
4 | $3$ | $3$ | 3 or 4 | $\lceil\frac{t+2}{2}\rceil^{\ast},\dots,t$
5 or 6 | $2$ | $2$ | $3^{\ast}$ | 3 or 4
7 or 8 | $2$ | $2$ |  $2^{\ast}$ or $3^{\ast}$ | 2, 3 or 4
$\geqslant 9$ | $2$ | $2$ | $2^{\ast}$ | 2, 3 or 4
$\Omega(\log t)$ | $2$ | $2$ | $2^{\ast}$ | $2^{\ast}$

First consider planar graphs. The 4-Colour Theorem says that planar graphs are
properly 4-colourable [61]. A much simpler proof by Cowen et al. [9] shows
that planar graphs are 4-colourable with clustering 2. Standard examples show
that the clustered chromatic number of the class of planar graphs equals 4
(see [74]). Similarly, Grotzsch’s Theorem [26, 68, 67, 63] says that triangle-
free planar graphs are properly 3-colourable. As a lower bound, for any
integer $d\geqslant 0$, Škrekovski [71] constructed triangle-free planar
graphs that are not 2-colourable with defect $d$; thus the defective and
clustered chromatic number of triangle-free planar graphs equals 3. (Note that
Lemma 5 below implies that triangle-free planar graphs are 3-colourable with
bounded clustering, without using Grotzsch’s Theorem).

Now consider girth $g\geqslant 5$. Liu and Wood [46] proved the following
analogue of Theorem 3.

######  Theorem 4 ([46]).

For any $s,t\in\mathbb{N}$ and for any graph $X$, every
$K_{\\_}{s,t}$-subgraph-free $X$-minor-free graph is $(s+2)$-colourable with
clustering at most some function $f(s,t,X)$.

As before, Theorem 4 with $s=t=2$ implies that every $X$-minor-free graph with
girth at least 5 is 4-colourable with clustering at most some function $f(X)$.

Now consider graphs embeddable on surfaces. Esperet and Ochem [22] and
Kawarabayashi and Thomassen [32] proved that graphs of bounded Euler genus are
5-colourable with bounded clustering. Improving these results, Dvořák and
Norin [17] showed that every graph with Euler genus $\gamma$ is 4-colourable
with clustering $O(\gamma)$. Hence the clustered chromatic number of the class
of graphs embeddable on any fixed surface equals 4. The proof is based on the
following lemma, which is proved using the so-called island method (see [74]
for a concise presentation).

######  Lemma 5 ([17]).

Let $\mathcal{G}$ be a hereditary graph class such that for some real numbers
$c,\varepsilon,\delta>0$ and some integers $k,n_{\\_}0\geqslant 2$, for all
$n\geqslant n_{\\_}0$, every $n$-vertex graph in $\mathcal{G}$ has a balanced
separator of order at most $cn^{1-\varepsilon}$, and has at most $(k-\delta)n$
edges. Then every graph in $\mathcal{G}$ is $k$-colourable with clustering at
most some function $f(k,c,\varepsilon,\delta,n_{\\_}0)$.

The balanced separator assumption in Lemma 5 is satisfied with
$\varepsilon=\frac{1}{2}$ for planar graphs [42, 43], for graphs of bounded
genus [23, 13], and for any minor-closed class [1].

The above-mentioned clustered 4-colour theorem of Dvořák and Norin [17] is
implied by Lemma 5 with $\delta=\frac{1}{2}$ and $n_{\\_}0:=6(\gamma-2)$,
since then it follows from Euler’s formula that every graph $G$ with
$n\geqslant 3$ vertices and Euler genus $\gamma$ satisfies $|E(G)|\leqslant
3(n+\gamma-2)\leqslant(4-\delta)n$ for $n\geqslant n_{\\_}0$. Similarly, every
triangle-free graph with $n\geqslant 3$ vertices and Euler genus $\gamma$ has
at most $2(n+\gamma-2)$ edges. Thus such graphs are 3-colourable with bounded
clustering by Lemma 5. More generally, every $n$-vertex graph with Euler genus
$\gamma$ and girth $g$ has at most $\frac{g}{g-2}(n+\gamma-2)$ edges. In
particular, if $g\geqslant 5$, then $G$ has at most $\frac{5}{3}(n+\gamma-2)$
edges, implying such graphs are 2-colourable with bounded clustering by Lemma
5. These results were mentioned by Wood [74].

Our results are summarised in Table 4. Every $(\gamma,k)$-apex graph $G$ is
5-colourable with bounded clustering: 4-colour $G-A$ using Lemma 5 and use one
new colour for $A$. Standard examples show that the clustered chromatic number
of $(0,1)$-apex graphs equals 5. Similarly, triangle-free $(\gamma,k)$-apex
graphs are 4-colourable with bounded clustering. Our other proofs for
$(\gamma,k)$-apex graphs are in Section 4.3. For $(0,5)$-apex graphs with
girth at least $6$, Proposition 16 implies that the clustered chromatic number
is at least $3$.

Finally, we mention the final rows in Tables 3 and 4, where the girth is
allowed to grow slowly with the excluded minor. In Section 5, we prove that
every graph with Hadwiger number at most $t$ and with girth $\Omega(\log t)$
are 2-colourable with clustering 2 (see Theorem 33). This section also
explores results on proper colouring of graphs with given Hadwiger number and
given girth. We show, via a result of Kühn and Osthus [41], that for every
integer $g\geqslant 5$ there exists $c_{\\_}g\in(0,1)$ with $c_{\\_}g\to 0$,
such that graphs with Hadwiger number $t$ and girth $g$ are properly
$O(t^{c_{\\_}g})$ colourable, thus asymptotically improving on Hadwiger’s
Conjecture for girth at least 5.

##  2 Definitions

We consider finite simple undirected graphs $G$ with vertex-set $V(G)$ and
edge-set $E(G)$. For a vertex $v\in V(G)$, let $N_{\\_}G(v):=\\{w\in
V(G):vw\in E(G)\\}$ and $N_{\\_}G[v]:=N_{\\_}G(v)\cup\\{v\\}$.

A _graph class_ $\mathcal{G}$ is a set of graphs closed under isomorphism. A
graph class $\mathcal{G}$ is _proper_ if some graph is not in $\mathcal{G}$. A
graph class $\mathcal{G}$ is _hereditary_ if it is closed under induced
subgraphs.

A graph $G$ is _$k$ -degenerate_ if every subgraph of $G$ has minimum degree
at most $k$. Such graphs are properly $(k+1)$-colourable by a greedy
algorithm.

A graph $H$ is a _minor_ of a graph $G$ if $H$ is isomorphic to a graph that
can be obtained from a subgraph of $G$ by contracting edges. A graph $G$ is
_$H$ -minor-free_ if $H$ is not a minor of $G$. The _Hadwiger number_ of a
graph $G$, denoted _$\operatorname{had}(G)$_ , is the maximum integer $t$ such
that $K_{\\_}t$ is a minor of $G$. A graph class $\mathcal{G}$ is _minor-
closed_ if for every graph $G\in\mathcal{G}$ every minor of $G$ is in
$\mathcal{G}$. Similarly, a graph parameter $f$ is _minor-monotone_ if
$f(H)\leqslant f(G)$ for every graph $G$ and every minor $H$ of $G$.

A _surface_ is a compact 2-dimensional manifold. For any fixed surface
$\Sigma$, the class of graphs embeddable on $\Sigma$ (without crossings) is
minor-closed. A surface with $h$ handles and $c$ cross-caps has _Euler genus_
$2h+c$. The _Euler genus_ of a graph $G$ is the minimum Euler genus of a
surface in which $G$ embeds. Euler genus is a minor-monotone graph parameter.
See [54] for more about graph embeddings in surfaces.

A _tree-decomposition_ of a graph $G$ is a collection
$\mathcal{T}=(B_{\\_}x:x\in V(T))$ of subsets of $V(G)$ (called _bags_)
indexed by the vertices of a tree $T$, such that (a) for every edge $uv\in
E(G)$, some bag $B_{\\_}x$ contains both $u$ and $v$, and (b) for every vertex
$v\in V(G)$, the set $\\{x\in V(T):v\in B_{\\_}x\\}$ induces a non-empty
(connected) subtree of $T$. The _width_ of $\mathcal{T}$ is
$\max\\{|B_{\\_}x|\colon x\in V(T)\\}-1$. The _treewidth_ of a graph $G$,
denoted _$\operatorname{tw}(G)$_ , is the minimum width of a tree-
decomposition of $G$.

A _path-decomposition_ is a tree-decomposition in which the underlying tree is
a path, simply denoted by the corresponding sequence of bags
$(B_{\\_}1,\dots,B_{\\_}n)$. The _pathwidth_ of a graph $G$, denoted
_$\operatorname{pw}(G)$_ , is the minimum width of a path-decomposition of
$G$. By definitition,

$\operatorname{tw}(G)\leqslant\operatorname{pw}(G).$

A tree $T$ with a distinguished vertex $r\in V(T)$ is said to be _rooted_ (at
$r$). The _depth_ of a vertex $v$ in $T$ is the number of vertices in the
$rv$-path in $T$. For distinct vertices $u,v$ in $T$, if $v$ is on the
$ur$-path in $T$, then $v$ is an _ancestor_ of $u$ and $u$ is a _descendant_
of $v$ in $T$. For each vertex $v$ in a rooted tree $T$, the subtree induced
by $v$ and all its descendents is the _subtree of $T$ rooted at_ $v$. A forest
is _rooted_ if each component tree is rooted. The _depth_ of a rooted forest
$F$ is the maximum depth of a vertex in $F$. The _closure_ of $F$ is the graph
with vertex set $V(F)$, where $vw$ is an edge if and only if $v$ is an
ancestor of $w$ or vice versa. The _treedepth_ of a graph $G$, denoted
_$\operatorname{td}(G)$_ , is the minimum depth of a rooted forest $F$ such
that $G$ is a spanning subgraph of the closure of $F$. It is well-known that
for every graph $G$,

$\operatorname{pw}(G)\leqslant\operatorname{td}(G)-1.$

To see this, introduce one bag for each root–leaf path, ordered left-to-right
according to a plane drawing of $F$, producing a path-decomposition of $G$.
Finally, if $G$ is a subgraph of the closure of a rooted tree $T$, and $v$ is
a vertex of $T$, then the _subgraph of $G$ rooted at_ $v$ is the subgraph of
$G$ induced by the vertices of the subtree of $T$ rooted at $v$.

For a graph $G$, a set $A\subseteq V(G)$ is a _feedback vertex set_ of $G$ if
$G-A$ is a forest. The _feedback vertex number_ of a graph $G$, denoted
_$\operatorname{fvn}(G)$_ , is the minimum number of vertices in a feedback
vertex set of $G$. Since a forest has treewidth at most 1,

$\operatorname{tw}(G)\leqslant\operatorname{fvn}(G)+1.$

The _circumference $\operatorname{circ}(G)$_ of a graph $G$ that is not a
forest is the length of the longest cycle in $G$. The _circumference_ of a
forest is 2. Birmelé [3] showed that

$\operatorname{tw}(G)\leqslant\operatorname{circ}(G)-1;$

see [52, 4] for related results.

It is well-known and easily seen that treewidth, pathwidth, treedepth,
feedback vertex number and circumference are minor-monotone.

##  3 Lower Bounds

###  3.1 Generalised Standard Examples

Many authors have noted that closures of rooted trees provide lower bounds on
the defective and clustered chromatic numbers [74, 28, 20, 59, 57, 70]. Such
graphs have been dubbed ‘standard examples’. The following definition and
theorem generalises these results.

Let $H$ be a graph equipped with a vertex ordering
$V(H)=\\{v_{\\_}1,\dots,v_{\\_}n\\}$. For an integer $d\geqslant 1$, let
$H^{(d)}$ be the following graph. Start with a complete $d$-ary tree $T$ of
vertex-height $n$. Let $V(H^{(d)}):=V(T)$, where for each root-leaf path
$(x_{\\_}1,\dots,x_{\\_}n)$ in $T$, $x_{\\_}ix_{\\_}j\in E(H^{(d)})$ if and
only if $v_{\\_}iv_{\\_}j\in E(H)$. For example, $K_{\\_}n^{(d)}$ is the
closure of the complete $d$-ary tree of height $n$. Numerous papers have noted
that $K_{\\_}n^{(d+1)}$ is not $(n-1)$-colourable with defect $d$ (see [74]).
Here we prove the following generalisation.

######  Theorem 6.

Let $H$ be a graph equipped with a vertex ordering
$V(H)=\\{v_{\\_}1,\dots,v_{\\_}n\\}$. Fix integers $d,k\geqslant 1$. Then the
following are equivalent:

  1. (1)

$H^{(d)}$ is $k$-colourable with defect $d-1$,

  2. (2)

$H^{(d)}$ is $k$-colourable with clustering $d$,

  3. (3)

$H^{(d)}$ is properly $k$-colourable,

  4. (4)

$H$ is properly $k$-colourable.

###### Proof.

We first prove that (4) $\Longrightarrow$ (3). Consider any proper
$k$-colouring of $H$. Let $T$ be the rooted tree underlying $H^{(d)}$. For
each root–leaf path $(x_{\\_}1,\dots,x_{\\_}n)$ of $T$, assign $x_{\\_}i$ the
colour assigned to $v_{\\_}i$. We obtain a proper $k$-colouring of $H^{(d)}$,
and (2) holds.

It is immediate that (3) $\Longrightarrow$ (2) $\Longrightarrow$ (1).

It remains to prove that (1) $\Longrightarrow$ (4). Suppose $H^{(d)}$ is
$k$-colourable with defect $d-1$. For each vertex $x$ of $H^{(d)}$, let
$T_{\\_}x$ be the subtree rooted at $x$ of the complete $d$-ary tree
underlying $H^{(d)}$. Let $x_{\\_}1$ be the root vertex. Say $x_{\\_}1$ is
blue. If each of the subtrees of $T$ rooted at the children of $x_{\\_}1$ has
a blue neighbour of $x_{\\_}1$, then $x_{\\_}1$ has monochromatic degree at
least $d$. Thus there is a child $x_{\\_}2$ of $x_{\\_}1$ such that no
neighbour of $x_{\\_}1$ in $T_{\\_}{x_{\\_}2}$ is blue. Repeating this
argument, we find a root-leaf path $x_{\\_}1,\dots,x_{\\_}n$ in $H^{(d)}$,
such that for each vertex $x_{\\_}i$, no neighbour of $x_{\\_}i$ in
$T_{\\_}{x_{\\_}{i+1}}$ is assigned the colour of $x_{\\_}i$. Thus the copy of
$H$ induced by $\\{x_{\\_}1,\dots,x_{\\_}n\\}$ is properly coloured with $k$
colours, and (4) holds. ∎

###  3.2 Triangle-Free Graphs

We now prove lower bounds for triangle-free graphs with given treedepth. By
construction, $H^{(d+1)}$ has treedepth at most $|V(H)|$, and if $H$ is
$K_{\\_}p$-subgraph-free, then so is $H^{(d+1)}$. Thus Theorem 6 implies:

######  Corollary 7.

The defective chromatic number of the class of $K_{\\_}p$-free graphs of
treedepth $k$ is at least the chromatic number of the class of $K_{\\_}p$-free
graphs on $k$ vertices.

Corollary 7 applies for triangle-free graphs, but not for girth at least 5
(since $H^{(d)}$ contains a 4-cycle whenever $d\geqslant 2$ and $H$ contains a
path $v_{\\_}iv_{\\_}kv_{\\_}j$ with $i<j<k$).

Kim [35] showed that the Ramsey number $R(3,t)\in\Omega(t^{2}/\log t)$. That
is, there exist triangle-free graphs $H$ on $n=\Omega(t^{2}/\log t)$ vertices
with $\alpha(H)<t$. Thus

$\chi(H)\geqslant n/\alpha(H)>n/t\geqslant\Omega(t/\log
t)\geqslant\Omega(\sqrt{n/\log n}).$

Corollary 7 with $p=3$ and Equation 1 thus imply:

######  Corollary 8.

The defective chromatic number of the class of triangle-free graphs with
treedepth $k$ (or pathwidth $k$ or treewidth $k$) is in $\Omega(\sqrt{k/\log
k})$.

######  Theorem 9.

Fix $p\geqslant 3$ and $k\geqslant 1$. Let $\mathcal{G}$ be the class of
$K_{\\_}p$-free graphs of treedepth $k$. Then the defective chromatic number,
the clustered chromatic number, and the chromatic number of $\mathcal{G}$ are
equal.

###### Proof.

Obviously, the defective chromatic number of $\mathcal{G}$ is at most the
clustered chromatic number of $\mathcal{G}$, which is at most the chromatic
number of $\mathcal{G}$. Let $c$ be the defective chromatic number of
$\mathcal{G}$. That is, for some $d$ every graph in $\mathcal{G}$ is
$c$-colourable with defect $d$. We now show that every graph in $\mathcal{G}$
is properly $c$-colourable.

Consider a graph $H\in\mathcal{G}$. So $H$ is a spanning subgraph of the
closure of some rooted tree with vertex-height $k$. Define $\widehat{H}$ as
follows. (This construction is an extension of the definition of $H^{(d)}$
above.) Initialise $\widehat{H}:=H$. We now make a sequence of changes to
$\widehat{H}$, where at each step, we maintain the property that $\widehat{H}$
is a spanning subgraph of the closure of some rooted tree with vertex-height
$k$. In particular, for $i=2,3,\dots,k$ and for each vertex $w$ at depth $i$
in $\widehat{H}$, replace the current subgraph $Q_{\\_}w$ of $\widehat{H}$
rooted at $w$ by $d+1$ copies of $Q_{\\_}w$ rooted at $w$, and for every edge
$xy$ where $x$ is an ancestor of $w$ and $y$ is a descendent of $w$ or equal
to $w$, add an edge between $x$ and the copy of $y$ in each of the $d+1$
copies of $Q_{\\_}w$. The final graph $\widehat{H}$ is in $\mathcal{G}$. By
assumption, $\widehat{H}$ is $c$-colourable with defect $d$.

We now show that $\widehat{H}$ contains a properly $c$-coloured induced
subgraph isomorphic to $H$. Let $T$ be the tree of vertex-height $k$ rooted at
$r$ such that $H$ is a subgraph of the closure of $T$. For each vertex $v$ in
$T$, we will choose exactly one vertex $v^{\prime}$ in $\widehat{H}$ to
represent $v$. Consider $w$ in non-decreasing order of
$\operatorname{dist}_{\\_}T(r,w)$. Let $r$ represent itself. Now assume $w\neq
r$. Let $v$ be the parent of $w$ in $T$. So some vertex $v^{\prime}$ in
$\widehat{H}$ is already chosen to represent $v$. Say $v^{\prime}$ is blue. In
$\widehat{H}$ there are $d+1$ copies $w_{\\_}1,\dots,w_{\\_}{d+1}$ of $w$ with
parent $v^{\prime}$. If for each $i\in\\{1,\dots,d+1\\}$, the subgraph of
$\widehat{H}$ rooted at $w_{\\_}i$ has a blue neighbour of $v^{\prime}$, then
$v^{\prime}$ has monochromatic degree at least $d+1$, which is a
contradiction. Thus for some $i\in\\{1,\dots,d+1\\}$, the subgraph of
$\widehat{H}$ rooted at $w_{\\_}i$ has no blue neighbour of $v^{\prime}$. Let
this vertex $w_{\\_}i$ represent $w$. By construction, the chosen vertices
induce a properly $c$-coloured subgraph of $\widehat{H}$ isomorphic to $H$.
Hence every graph in $\mathcal{G}$ is properly $c$-colourable. ∎

We now use a variant of the approach of Dvořák and Kawarabayashi [18] to
improve the lower bound on the chromatic number in Corollary 8 to
$(1-o(1))\sqrt{2k}$.

######  Theorem 10.

For any integer $k\geqslant 1$ there is a triangle-free graph with treedepth
$\binom{k+1}{2}$ and chromatic number at least $k$.

###### Proof.

Let $T$ be the tree rooted at a vertex $r$, and let $G$ be a subgraph of the
closure of $T$ defined as follows. For each vertex $v$ of $T$ considered in
non-decreasing order of $\operatorname{dist}_{\\_}T(r,v)$, if $P_{\\_}v$ is
the $rv$-path in $T$, then for each independent set $I$ of $G[V(P_{\\_}v)]$
introduce one child of $v$ with neighbourhood $I$. Consider any proper
colouring of $G$. Let $\operatorname{col}(v)$ be the colour assigned to each
vertex $v$. The following claim implies the theorem.

Claim. For each integer $k\geqslant 1$ there is a vertex $v$ in the first
$\binom{k+1}{2}$ layers of $G$ and there is an independent set of
$G[V(P_{\\_}v)]$ assigned at least $k$ distinct colours.

We proceed by induction on $k$. The $k=1$ case is true with $v=r$. Assume the
claim is true for some $k\geqslant 1$. Thus there is a vertex $w_{\\_}0$ in
the first $\binom{k+1}{2}$ layers of $G$ and there is an independent set $I$
of $G[V(P_{\\_}{w_{\\_}0})]$ assigned at least $k$ distinct colours.

By construction, there is a child $w_{\\_}1$ of $w_{\\_}0$ adjacent to no
vertices in $I$. If no vertex in $I$ is assigned the same colour as
$w_{\\_}1$, then $I\cup\\{w_{\\_}1\\}$ is an independent set of
$G[V(P_{\\_}{w_{\\_}1})]$ assigned at least $k+1$ distinct colours, and
$w_{\\_}1$ is in the first $\binom{k+1}{2}+1\leqslant\binom{k+2}{2}$ layers of
$G$. Now assume $\operatorname{col}(y_{\\_}1)=\operatorname{col}(w_{\\_}1)$
for some vertex $y_{\\_}1\in I$.

We now construct a sequence of distinct vertices $w_{\\_}1,\dots,w_{\\_}{k+1}$
in $T$ and a sequence of distinct vertices $y_{\\_}1,\dots,y_{\\_}k$ in $I$,
such that:

  * •

for each $j\in\\{1,\dots,k\\}$,
$\operatorname{col}(y_{\\_}j)=\operatorname{col}(w_{\\_}j)$

  * •

for each $j\in\\{1,\dots,k+1\\}$, $w_{\\_}j$ is a child of $w_{\\_}{j-1}$

  * •

for each $j\in\\{1,\dots,k+1\\}$, the vertex $w_{\\_}j$ is adjacent to each
vertex in $\\{y_{\\_}1,\dots,y_{\\_}{j-1}\\}$ and is adjacent to no vertex in
$(I\setminus\\{y_{\\_}1,\dots,y_{\\_}{j-1}\\})\cup\\{w_{\\_}1,\dots,w_{\\_}{j-1}\\}$.

These properties hold for $w_{\\_}1$ as shown above.

Assume that $w_{\\_}1,\dots,w_{\\_}j$ and $y_{\\_}1,\dots,y_{\\_}{j-1}$
satisfy these properties for some $j\in\\{1,\dots,k\\}$. Thus
$\operatorname{col}(w_{\\_}j)\neq\operatorname{col}(y_{\\_}i)=\operatorname{col}(w_{\\_}i)$
for all $i\in\\{1,\dots,j-1\\}$. If no vertex in
$I\setminus\\{y_{\\_}1,\dots,y_{\\_}{j-1}\\}$ is assigned the same colour as
$w_{\\_}j$, then
$(I\setminus\\{y_{\\_}1,\dots,y_{\\_}{j-1}\\})\cup\\{w_{\\_}1,\dots,w_{\\_}{j}\\}$
is an independent set of $G[V(P_{\\_}{w_{\\_}j})]$ assigned $k+1$ distinct
colours, where $w_{\\_}j$ is in the first
$\binom{k+1}{2}+j\leqslant\binom{k+2}{2}$ levels of $G$, and we are done. Thus
we may assume that $\operatorname{col}(y_{\\_}j)=\operatorname{col}(w_{\\_}j)$
for some vertex $y_{\\_}j$ in $I\setminus\\{y_{\\_}1,\dots,y_{\\_}{j-1}\\}$.
By the definition of $G$, there is a child $w_{\\_}{j+1}$ of $w_{\\_}j$ that
is adjacent only to the independent set
$\\{y_{\\_}1,y_{\\_}2,\dots,y_{\\_}j\\}$. This allows us to extend our
sequence.

Repeating this step constructs the desired sequences. In particular,
$\\{w_{\\_}1,\dots,w_{\\_}{k+1}\\}$ is an independent set of
$G[V(P_{\\_}{w_{\\_}{k+1}})]$ assigned at least $k+1$ distinct colours, and
$w_{\\_}{k+1}$ is in the first $\binom{k+1}{2}+k+1=\binom{k+2}{2}$ layers of
$G$, as claimed. ∎

Theorems 1, 9 and 10 imply:

######  Corollary 11.

For any integer $k\geqslant 1$ for the class of triangle-free graphs with
treedepth $k$, the chromatic number, defective chromatic number and clustered
chromatic number are equal, and are at least $(1-o(1))\sqrt{2k}$ and at most
$\lceil\frac{k+2}{2}\rceil$.

We have the following corollary of Theorem 10 for graphs of given
circumference, since $\operatorname{circ}(H)<2^{\operatorname{td}(H)}$ for
every graph $H$ (see [55, Proposition 6.2]).

######  Corollary 12.

The chromatic number, defective chromatic number and clustered chromatic
number of the class of triangle-free graphs with circumference $k$ is in
$\Omega(\log k)$.

Now consider triangle-free graphs with given treewidth.

######  Theorem 13.

Fix $p\geqslant 3$ and $k\geqslant 1$. Let $\mathcal{G}$ be the class of
$K_{\\_}p$-free graphs of treewidth $k$. Then the defective chromatic number,
the clustered chromatic number, and the chromatic number of $\mathcal{G}$ are
equal.

###### Proof.

Obviously, the defective chromatic number of $\mathcal{G}$ is at most the
clustered chromatic number of $\mathcal{G}$, which is at most the chromatic
number of $\mathcal{G}$. Let $c$ be the defective chromatic number of
$\mathcal{G}$. That is, for some $d$ every graph in $\mathcal{G}$ is
$c$-colourable with defect $d$. We now show that every graph in
$G\in\mathcal{G}$ is properly $c$-colourable.

Consider a tree-decomposition $(B_{\\_}x:x\in V(T))$ of $G$ with width at most
$k$. Root $T$ at a node $r$. Normalise the tree-decomposition so that for each
edge $xy\in E(T)$ with $x$ the parent of $y$, $|B_{\\_}y\setminus
B_{\\_}x|=1$, and for each vertex $v$ of $G$ there is an edge $xy\in E(T)$
with $x$ the parent of $y$, such that $B_{\\_}y\setminus B_{\\_}x=\\{v\\}$. In
this case, let $h(v):=y$ (the ‘home’ of $v$). Let $\preceq$ be the partial
order on $V(G)$, where $v\prec w$ if and only if $h(v)$ is an ancestor of
$h(w)$ in $T$. The _depth_ of $v$ is $\operatorname{dist}_{\\_}T(r,h(v))$.

We now define a sequence of $K_{\\_}p$-free graphs
$G_{\\_}1,G_{\\_}2,\dots,G_{\\_}m$, each with a rooted normalised tree-
decomposition $(B_{\\_}x:x\in V(T_{\\_}i))$ of width at most $k$, where
$G_{\\_}1:=G$. In each graph $G_{\\_}i$, each vertex will be ‘processed’ or
‘unprocessed’. Initially, all vertices in $G_{\\_}1$ are unprocessed. Suppose
that $G_{\\_}1,\dots,G_{\\_}i$ are defined, and some vertex in $G_{\\_}i$ is
unprocessed. Let $v$ be an unprocessed vertex in $G_{\\_}i$ at minimum depth.
Let $y:=h(v)\in V(T_{\\_}i)$. Let $U_{\\_}1,\dots,U_{\\_}m$ be the subtrees of
$T_{\\_}i$ rooted at the children of $y$. Let $V_{\\_}j$ be the set of
vertices $w\in V(G_{\\_}i)$ where $h(w)\in V(U_{\\_}j)$. Let
$U:=\bigcup_{\\_}{j=1}^{m}V_{\\_}j$. Let $G_{\\_}{i+1}$ be obtained from
$G_{\\_}i$ by making $d+1$ copies of each vertex in $U$. For each edge $pq$ of
$G[U]$, add an edge to $G_{\\_}{i+1}$ between the $\ell$-th copy of $p$ and
the $\ell$-th copy of $q$, for each $\ell$. For each edge $wp\in E(G_{\\_}i)$
where $w\in B_{\\_}y$ and $p\in U$, add an edge between $p$ and the $\ell$-th
copy of $p$, for each $\ell$. This includes the case $w=v$. Construct a
normalised tree-decomposition of $G_{\\_}{i+1}$ as follows. Let $T_{\\_}{i+1}$
be obtained from $T_{\\_}i$ by taking $d+1$ copies of each $U_{\\_}j$, where
the root of each copy is a child of $y$. For each vertex $p\in U$, if $p\in
B_{\\_}x$ then place the $\ell$-th copy of $p$ in the bag corresponding to the
$\ell$-th copy of $x$ in $T_{\\_}{i+1}$. We obtain a normalised tree-
decomposition $(B^{\prime}_{\\_}x:x\in V(T_{\\_}{i+1}))$ of $G_{\\_}{i+1}$,
such that for each vertex $w\in U$, if $h(w)=x$ then the home bags of the
$d+1$ copies of $w$ are the $d+1$ copies of $x$. In $G_{\\_}{i+1}$ say that
$v$ is processed. We now show that $G_{\\_}{i+1}$ is $K_{\\_}p$-free. Suppose
that $X$ is a set of vertices in $G_{\\_}{i+1}$ that induce $K_{\\_}p$. By the
Helly property, $X$ is a subset of some bag $B^{\prime}_{\\_}x$. By
construction, $G_{\\_}{i+1}[B^{\prime}_{\\_}x]$ is isomorphic to the subgraph
of $G_{\\_}i$ induced by some bag $B_{\\_}x$, implying that $G_{\\_}i$
contains $K_{\\_}p$. This contradiction shows that $G_{\\_}{i+1}$ is
$K_{\\_}p$-free.

This completes the definition of $G_{\\_}1,G_{\\_}2,\dots$. Note that for each
vertex $v$ of $G$ the depth of each copy of $v$ always equals the original
depth of $v$. In $G_{\\_}i$, let $d_{\\_}i$ be the minimum depth of an
unprocessed vertex, and let $n_{\\_}i$ be the number of processed vertices in
$G_{\\_}i$ at depth $d_{\\_}i$. By construction, $(d_{\\_}{i+1},n_{\\_}{i+1})$
is lexicographically greater than $(d_{\\_}i,n_{\\_}i)$. Thus the sequence
$G_{\\_}1,G_{\\_}2,\dots$ is finite. Let $G_{\\_}n$ be the final graph, in
which every vertex is processed. By construction, $G_{\\_}n$ has treewidth at
most $k$ and is $K_{\\_}p$-free.

Consider a $c$-colouring of $G_{\\_}n$ with defect $d$. We now show that
$G_{\\_}n$ contains a properly $c$-coloured induced subgraph isomorphic to
$G$. Say $v$ is the unprocessed vertex in $G_{\\_}i$ chosen by the above
process. Use the notation above. Let $y:=h(v)\in V(T_{\\_}i)$. Let
$U_{\\_}1,\dots,U_{\\_}m$ be the subtrees of $T_{\\_}i$ rooted at the children
$z_{\\_}1,\dots,z_{\\_}m$ of $y$. Let $V_{\\_}j$ be the set of vertices $w\in
V(G_{\\_}i)$ where $h(w)\in V(U_{\\_}j)$. Say $v$ is blue. For each
$j\in\\{1,\dots,m\\}$, if each of the $d+1$ copies of $V_{\\_}j$ in
$G_{\\_}{i+1}$ has a blue neighbour of $v$, then $v$ has defect $d+1$, which
is a contradiction. So some copy of $V_{\\_}j$ in $G_{\\_}{i+1}$ has no blue
neighbour of $v$. Say that this copy of $V_{\\_}j$ and the corresponding edge
of $T_{\\_}{i+1}$ is ‘chosen’ by $v$. This chosen edge remains in $T_{\\_}n$.
By construction, the union of the bags in $(B_{\\_}x:x\in V(T_{\\_}n))$ at
nodes that are endpoints of the chosen edges in $T_{\\_}n$ contains a properly
$c$-coloured induced subgraph isomorphic to $G$. Therefore every graph in
$\mathcal{G}$ is properly $c$-colourable. ∎

Theorems 1 and 13 imply:

######  Corollary 14.

Let $\mathcal{G}$ be the class of triangle-free graphs with treewidth at most
$k$. Then the defective chromatic number of $\mathcal{G}$, the clustered
chromatic of $\mathcal{G}$, and the proper chromatic number of $\mathcal{G}$
all equal $\lceil\frac{k+3}{2}\rceil$.

###  3.3 Feedback Vertex Number

We now prove two lower bounds on the clustered chromatic number of graphs with
given feedback vertex number and given girth.

######  Proposition 15.

For each integer $d\geqslant 0$, there is a triangle-free graph $G$ with
$\operatorname{fvn}(G)=1$ that is not 2-colourable with defect $d$.

###### Proof.

As illustrated in Figure 1, let $T_{\\_}0$ be the $(d+1)$-leaf star. Let $T$
be obtained from $T_{\\_}0$ by adding, for each vertex $v$ in $T_{\\_}0$, a
set $L_{\\_}v$ of $2d+1$ leaves adjacent to $v$. Let $G$ be obtained from $T$
by adding one vertex $\alpha$ adjacent to all the leaves of $T$. So
$\operatorname{fvn}(G)=1$ and $G$ is triangle-free (since $N_{\\_}G(\alpha)$
is an independent set). Suppose that $G$ is 2-colourable with defect $d$. Say
$\alpha$ is blue, and the other colour is red. For each vertex $v$ in
$T_{\\_}0$, at most $d$ vertices in $L_{\\_}v$ are blue (since they are all
adjacent to $\alpha$). So at least $d+1$ vertices in $L_{\\_}v$ are red,
implying $v$ is blue. Thus every vertex in $T_{\\_}0$ is blue, which is a
contradiction since $T_{\\_}0$ has a vertex of degree $d+1$. Hence $G$ is not
2-colourable with defect $d$. ∎

Figure 1: Construction in Proposition 15.

######  Proposition 16.

For any $c\geqslant 1$ there is a graph $G$ with girth $6$ and
$\operatorname{fvn}(G)\leqslant 7$, and
$\operatorname{tw}(G)\leqslant\operatorname{pw}(G)\leqslant 8$, such that $G$
has no 2-colouring with clustering $c$.

###### Proof.

As illustrated in Figure 2, let $V$ be a set of 7 vertices. Let
$n:=4c^{2}+4c+1$. For each set $S\in\binom{V}{4}$, add a path $P_{\\_}S$ of
length $n$ to $G$ (disjoint from $V$), where $P_{\\_}S$ and $P_{\\_}T$ are
disjoint for distinct $S,T\in\binom{V}{4}$. Consider $S\in\binom{V}{4}$. For
each vertex $x$ in $P_{\\_}S$ add an edge to $G$ from $x$ to one vertex $v\in
S$, so that for any distinct vertices $x,y\in V(P_{\\_}S)$, if $xv,yv\in E(G)$
then $\operatorname{dist}_{\\_}{P_{\\_}S}(x,y)\geqslant 4$. This is possible
since $|S|=4$. By construction, $\operatorname{fvn}(G)\leqslant 7$. In fact,
$G-V$ is a forest of paths. Thus
$\operatorname{tw}(G)\leqslant\operatorname{pw}(G)\leqslant 8$.

Figure 2: Construction in Proposition 16.

Suppose for the sake of contradiction that $G$ has a cycle $C$ of length at
most 5. Since $G-V$ is acyclic, $C\cap V\neq\varnothing$. Since $V$ is an
independent set in $G$, $|C\cap V|\leqslant 2$. First suppose that $C\cap
V=\\{v\\}$. Say $C=(v,a,b,c,d)$. Thus $(a,b,c,d)$ is a subpath of some
$P_{\\_}S$, and $\operatorname{dist}_{\\_}{P_{\\_}S}(a,d)\leqslant 3$, which
contradicts the construction. Hence $|C\cap V|=2$, say $C\cap V=\\{v,w\\}$.
Since $V$ is an independent set, $v$ and $w$ are not consecutive in $C$. Thus
$v$ and $w$ have a common neighbour in $C$, which must be in some $P_{\\_}S$,
but no vertex in $P_{\\_}S$ is adjacent to two vertices in $V$, which is the
desired contradiction. Hence $G$ has girth at least 6. In fact, $G$ has girth
6.

Suppose that $G$ has a 2-colouring with clustering $c$. There is a
monochromatic subset $S$ of $V$ of size 4. Say $S$ is white. For each $v\in S$
there are less than $c$ white vertices in $P_{\\_}S$ adjacent to $v$. Each
vertex in $P_{\\_}S$ is adjacent to some vertex in $S$. Thus there are less
than $4c$ white vertices in $P_{\\_}S$. The black subgraph of $P_{\\_}S$ has
at most $4c$ components. Hence $P_{\\_}S$ contains a black subpath on
$(n-4c)/4c>c$ vertices. This contradiction shows that $G$ has no 2-colouring
with clustering $c$. ∎

Note the following concerning the graph $G$ in Proposition 16. Since $G-V$ is
a forest of paths, it follows that for any $v,w\in V$, $G-(V\setminus\\{v\\})$
is outerplanar and so $G-(V\setminus\\{v,w\\})$ is planar. So $G$ is $5$-apex,
which shows that $(\gamma,k)$-apex graphs with girth at most 6 have clustered
chromatic number at least 3 (for $\gamma\geqslant 0$ and $k\geqslant 5$).

##  4 Upper Bounds

###  4.1 Defective Colouring via Strong Colouring Numbers

Kierstead and Yang [34] introduced the following definition. For a graph $G$,
a total order $\preceq$ of $V(G)$, and $r\in\mathbb{N}$, a vertex $w\in V(G)$
is _$r$ -reachable_ from a vertex $v\in V(G)$ if there is a path
$v=w_{\\_}0,w_{\\_}1,\dots,w_{\\_}{r^{\prime}}=w$ of length
$r^{\prime}\in[0,r]$ such that $w\preceq v$ and $v\prec w_{\\_}i$ for all
$i\in[r^{\prime}-1]$. For a graph $G$ and integer $r\in\mathbb{N}$, the _$r$
-strong colouring number_ $\operatorname{col}_{\\_}r(G)$ is the minimum
integer such that there is a total order $\preceq$ of $V(G)$ such that at most
$\operatorname{col}_{\\_}r(G)$ vertices are $r$-reachable from each vertex of
$G$.

An attractive aspect of strong colouring numbers is that they interpolate
between degeneracy and treewidth [40]. Indeed, it follows from the definition
that $\operatorname{col}_{\\_}1(G)$ equals the degeneracy of $G$ plus 1,
implying $\chi(G)\leqslant\operatorname{col}_{\\_}1(G)$. At the other extreme,
Grohe et al. [24] showed that
$\operatorname{col}_{\\_}r(G)\leqslant\operatorname{tw}(G)+1$ for all
$r\in\mathbb{N}$, and indeed

$\lim_{\\_}{r\to\infty}\operatorname{col}_{\\_}r(G)=\operatorname{tw}(G)+1.$

Strong colouring numbers provide upper bounds on several graph parameters of
interest, including acyclic chromatic number [34], game chromatic number [33,
34], Ramsey numbers [5], oriented chromatic number [39], arrangeability [5],
etc. Strong colouring numbers are important also because they characterise
bounded expansion classes [75], they characterise nowhere dense classes [24],
and have several algorithmic applications such as the constant-factor
approximation algorithm for domination number by Dvořák [16], and the almost
linear-time model-checking algorithm of Grohe et al. [25].

Van den Heuvel et al. [69] proved the following linear bounds on
$\operatorname{col}_{\\_}r(G)$ (always for every $r\in\mathbb{N}$): Every
finite planar graph $G$ satisfies $\operatorname{col}_{\\_}r(G)\leqslant
5r+1$. More generally, every finite graph $G$ with Euler genus $\gamma$
satisfies $\operatorname{col}_{\\_}r(G)\leqslant(4\gamma+5)r+2\gamma+1$. Even
more generally, for $t\geqslant 4$, every $K_{\\_}t$-minor-free graph $G$
satisfies $\operatorname{col}_{\\_}r(G)\leqslant\binom{t-1}{2}(2r+1)$.

######  Theorem 17.

Every $K_{\\_}{s,t}$-subgraph-free graph is $s$-colourable with defect at most
$\operatorname{col}_{\\_}2(G)+(t-1)\binom{\operatorname{col}_{\\_}2(G)}{s-1}$.

###### Proof.

Let $\preceq$ be a total ordering of $V(G)$ witnessing
$\operatorname{col}_{\\_}2(G)$. Consider each $v\in V(G)$ in the order given
by $\preceq$, and choose $\operatorname{col}(v)\in\\{1,\dots,s\\}$ distinct
from the colour assigned to the $s-1$ leftmost neighbours of $v$. Suppose that
$v$ has monochromatic degree at least
$\operatorname{col}_{\\_}2(G)+(t-1)\binom{\operatorname{col}_{\\_}2(G)}{s-1}+1$.
At most $\operatorname{col}_{\\_}2(G)$ neighbours of $v$ are to the left of
$v$. Thus there is a set $W$ of $t\binom{\operatorname{col}_{\\_}2(G)}{s-1}+1$
neighbours $w$ of $v$ with $\operatorname{col}(w)=\operatorname{col}(v)$ and
$v\prec w$ for each $w\in W$. For each $w\in W$, by the choice of
$\operatorname{col}(w)$, there is a set $A_{\\_}w$ of $s-1$ neighbours of $w$
to the left of $v$. Thus $A:=\bigcup_{\\_}{w\in W}A_{\\_}w$ is 2-reachable
from $v$. Hence $|A|\leqslant\operatorname{col}_{\\_}2(G)$. For each
$(s-1)$-subset $A^{\prime}$ of $A$ there are at most $t-1$ vertices $w\in W$
with $A_{\\_}w=A^{\prime}$, as otherwise with $v$ there would be a
$K_{\\_}{s,t}$-subgraph in $G$. Hence
$|W|\leqslant(t-1)\binom{\operatorname{col}_{\\_}2(G)}{s-1}$, which is the
desired contradiction. Thus each vertex $v$ has monochromatic degree at most
$\operatorname{col}_{\\_}2(G)+(t-1)\binom{\operatorname{col}_{\\_}2(G)}{s-1}$.
Hence $G$ is $s$-colourable with defect at most
$\operatorname{col}_{\\_}2(G)+(t-1)\binom{\operatorname{col}_{\\_}2(G)}{s-1}$.
∎

Zhu [75] proved that $\nabla(G)$ and $\operatorname{col}_{\\_}2(G)$ are tied.
So Theorem 17 and Theorem 2 are equivalent (up to the defect term). Note that
Theorems 2 and 17 both hold in the choosability setting.

We now give an application of Theorem 17 for graphs of given circumference. We
need the following tweak to Theorem 17. In a coloured graph $G$ a vertex $v$
is _properly coloured_ if $\operatorname{col}(v)\neq\operatorname{col}(w)$ for
each edge $vw\in E(G)$; that is, $v$ is the only vertex in the monochromatic
component containing $v$.

######  Lemma 18.

For any integer $t\geqslant s\geqslant 2$, for any $K_{\\_}{s,t}$-subgraph-
free graph $G$ and vertex $v\in V(G)$, there is an $s$-colouring of $G$ with
defect at most
$\operatorname{col}_{\\_}2(G)+1+(t-1)\binom{\operatorname{col}_{\\_}2(G)+1}{s-1}$,
such that $v$ is properly coloured.

###### Proof.

Let $\preceq$ be the total order of $V(G)$ witnessing
$\operatorname{col}_{\\_}2(G)$. Let $\preceq^{\prime}$ be the total order of
$V(G)$ obtained from $\preceq$ by putting $v$ first. For each vertex $x\in
V(G)$, the only vertex that is $2$-reachable from $x$ in $\preceq^{\prime}$
but not in $\preceq$ is $v$. Thus at most $\operatorname{col}_{\\_}2(G)+1$
vertices are 2-reachable from $x$ in $\preceq^{\prime}$. Apply the colouring
procedure from the proof of Theorem 17 to $\preceq^{\prime}$. So $v$ will be
the first vertex coloured. (In fact, $v$ can be pre-assigned any element of
$L(v)$.) If $vx\in E(G)$ then $v$ will be one of the $s-1$ leftmost neighbours
of $x$, so $x$ will be assigned a colour distinct from the colour of $v$. That
is, $v$ is properly coloured. The proof for the bound on the defect is the
same as in Theorem 17. ∎

######  Theorem 19.

For every graph $G$ with circumference $k$ and girth at least 5, for every
vertex $v$ of $G$, there is a 2-colouring of $G$ with clustering
$(4k^{2})^{k^{2}}$ such that $v$ is properly coloured.

###### Proof.

We proceed by induction on $|V(G)|$. We may assume that $G$ is connected. If
$G$ is not 2-connected, then $G$ has a separation $(G_{\\_}1,G_{\\_}2)$ with
$V(G_{\\_}1\cap G_{\\_}2)=\\{w\\}$ for some vertex $w$. Without loss of
generality, $v\in V(G_{\\_}1)$. By induction, there is a 2-colouring of
$G_{\\_}1$ with clustering $c$ such that $v$ is properly coloured. By
induction, there is a 2-colouring of $G_{\\_}2$ with clustering $c$ such that
$w$ is properly coloured. Permute the colours in $G_{\\_}2$ so that $w$ is
assigned the same colour in $G_{\\_}1$ and $G_{\\_}2$. We obtain a 2-colouring
of $G$ with clustering $c$ such that $v$ is properly coloured.

Now assume that $G$ is 2-connected. So $G$ has finite girth. As mentioned
above,
$\operatorname{col}_{\\_}2(G)\leqslant\operatorname{tw}(G)+1\leqslant\operatorname{circ}(G)\leqslant
k$. By Lemma 18 with $s=t=2$, $G$ is 2-colourable with defect
$\operatorname{col}_{\\_}2(G)+1+(t-1)\binom{\operatorname{col}_{\\_}2(G)+1}{s-1}\leqslant
2k+2$ such that $v$ is properly coloured. Dirac [12] showed that every path in
$G$ has length less than $k^{2}$ (using 2-connectivity). (In fact, Briański et
al. [4] showed that $G$ has treedepth at most $k$.) Hence each monochromatic
component has less than $(4k^{2})^{k^{2}}$ vertices. ∎

###  4.2 Feedback Vertex Number

We now prove upper bounds on the clustered chromatic number of graphs with
given feedback vertex number and given girth.

######  Proposition 20.

Every graph $G$ with $\operatorname{fvn}(G)\leqslant 1$ and girth at least 5
is 2-colourable with clustering $2$.

###### Proof.

Let $v$ be a vertex of $G$ such that $G-v$ is a forest. Suppose that some leaf
$\ell$ of $G-v$ is not adjacent to $v$. So $\deg_{\\_}G(\ell)\leqslant 1$. By
induction, $G-\ell$ is 2-colourable with clustering $2$. Assign $\ell$ a
colour different from its neighbour. Now $G$ is 2-coloured with clustering
$2$. Now assume that every leaf of $G-v$ is adjacent to $v$. Fix a root vertex
$r$ of $G-v$. Let $\ell$ be a vertex in the same component of $G-v$ as $r$ at
maximum distance from $r$. So $\ell$ is a leaf in $G-v$. Let $p$ be the parent
of $\ell$ in $G-v$. So $pv\not\in E(G)$ as otherwise $(p,v,\ell)$ would be a
3-cycle in $G$. If $p$ has another child $\ell^{\prime}$ (in addition to
$\ell$), then $\ell^{\prime}$ is a leaf by the choice of $\ell$, implying that
$(\ell,p,\ell^{\prime},v)$ is a 4-cycle in $G$. Hence $\ell$ is the only child
of $p$, and $p$ has degree at most 2 in $G$. By induction, $G-\ell-p$ is
2-colourable with clustering 2. Assign $\ell$ a colour distinct from the
colour assigned to $v$, and assign $p$ a colour distinct from the colour of
the neighbour of $p$ other than $\ell$. Every monochromatic component created
is contained in $\\{\ell,p\\}$. Thus the clustering is at most 2. ∎

######  Theorem 21.

Every graph $G$ with $\operatorname{fvn}(G)\leqslant k$ and girth at least 7
is 2-colourable with clustering $\binom{k}{2}+k$.

###### Proof.

Let $A$ be a set of at most $k$ vertices in $G$ such that $G-A$ is acyclic.
Colour each vertex in $A$ white. Let $N:=N_{\\_}G(A)$. Colour each vertex in
$N$ black. Thus each monochromatic component intersecting $A$ is contained in
$A$. Let $E:=E(G[N])$. For each edge $vw\in E$ there is a pair
$\\{a,b\\}\in\binom{A}{2}$ such that $va,wb\in E(G)$; charge $vw$ to
$\\{a,b\\}$. If distinct edges $v_{\\_}1w_{\\_}1,v_{\\_}2w_{\\_}2\in E$ are
charged to the same pair $\\{a,b\\}\in\binom{A}{2}$, then
$G[\\{v_{\\_}1,w_{\\_}1,v_{\\_}2,w_{\\_}2,a,b\\}]$ contains a cycle,
contradicting that $G$ has girth at least 7. Thus no two distinct edges in $E$
are charged to the same pair in $\binom{A}{2}$. Hence
$|E|\leqslant\binom{|A|}{2}$.

By assumption, $G-A$ is a forest. Root each component of $G-A$. Consider each
component $C$ of $G-A-N$. Let $r_{\\_}C$ be the root of $C$. Colour each
vertex of $C$ at even distance from $r_{\\_}C$ in $C$ white. Colour each
vertex of $C$ at odd distance from $r_{\\_}C$ in $C$ black. In particular,
$r_{\\_}C$ is white. Each monochromatic component of $C$ is a single vertex.
The parent of $r_{\\_}C$ in $G-A$ (if it exists) is in $N$, and is coloured
black, which is different from the colour of $r_{\\_}C$. No vertex in $C$ is
adjacent to a vertex in $A$. Thus the white vertices in $C$ are properly
coloured.

Consider a black vertex $v$ in $C$. If $v$ has at least $|A|+1$ neighbours in
$N$, then $v$ has two neighbours $x,y\in N$ both adjacent to the same vertex
$a\in A$, implying that $(v,x,a,y)$ is a 4-cycle in $G$, contradicting that
$G$ has girth at least 7. Hence $v$ has at most $|A|$ neighbours in $N$ which
will be in the same monochromatic component as $v$.

For each vertex $w\in N$ (which is black), any children of $w$ in $G-A$ are
the root vertex of their component of $G-A-N$, and are thus white. Hence the
parent of $w$ is the only possible black neighbour of $w$ in $G-A-N$. The only
other black neighbours of $w$ are also in $N$.

Hence each black component $B$ of $G$ consists of at most $\binom{|A|}{2}$
edges in $E$, which are incident to at most $\binom{|A|}{2}+1$ vertices in
$N$, plus, for each such vertex $w$ in $B\cap N$, the parent $v$ of $w$ (if it
is black), and the at most $|A|-1$ children of $v$ in $N$ distinct from $w$.
In total, $B$ has at most $\binom{|A|}{2}+|A|$ vertices.

Thus this 2-colouring of $G$ has clustering at most
$\binom{|A|}{2}+|A|\leqslant\binom{k}{2}+k$. ∎

###  4.3 Apex Graphs

Here we prove clustered colouring results for $(\gamma,k)$-apex graphs with
given girth.

######  Theorem 22.

Every $(\gamma,k)$-apex graph with girth at least 9 is 2-colourable with
clustering at most some function $f(\gamma,k)$.

###### Proof.

Let $G$ be an $n$-vertex $(\gamma,k)$-apex graph, where $n\geqslant
n_{\\_}0:=14(\tfrac{9}{7}\gamma+(k+2)\tbinom{k}{2})$. By Lemma 23 below,
$|E(G)|\leqslant\tfrac{25}{14}n+\tfrac{9}{7}\gamma+(k+2)\tbinom{k}{2}\leqslant\tfrac{13}{7}n$.
By a result of Alon et al. [1], $G$ has a balanced separator of size
$cn^{1/2}$ for some $c=c(\gamma,k)$. The result now follows from Lemma 5 with
$\varepsilon=\frac{1}{2}$ and $\delta=\frac{1}{7}$ and $k=2$. ∎

######  Lemma 23.

For all integers $\gamma,k\geqslant 0$ every $n$-vertex $(\gamma,k)$-apex
graph with girth at least 9 has at most
$\tfrac{25}{14}n+\tfrac{9}{7}\gamma+(k+2)\tbinom{k}{2}$ edges.

###### Proof.

Let $G$ be an $n$-vertex $(\gamma,k)$-apex graph with girth at least 9. Thus
there exists $A\subseteq V(G)$ with $|A|\leqslant k$ such that $G-A$ has Euler
genus at most $\gamma$. By Euler’s formula, $G-A$ has at most
$\frac{9}{7}(n-|A|+\gamma-2)$ edges. Let $N$ be the set of vertices in $G-A$
adjacent to at least one vertex in $A$. Let $X$ be the set of vertices in $N$
adjacent to at least two vertices in $A$. Thus $|X|\leqslant\binom{k}{2}$, as
otherwise there exists two vertices in $X$ adjacent to the same two vertices
in $A$, implying that $G$ contains a 4-cycle. Let $Y$ be the set of vertices
in $N\setminus X$ that are at distance at most 2 in $G-A$ from another vertex
in $N$. For each $v\in Y$ there are vertices $a,b\in A$ and there are edges
$va,wb\in E(G)$ for some vertex $w\in N$ where
$\operatorname{dist}_{\\_}{G-A}(v,w)\leqslant 2$. In this case, charge $v\in
Y$ to the set $\\{a,b\\}$. No two vertices in $Y$ are charged to the same set
$\\{a,b\\}\in\binom{A}{2}$, as otherwise $G$ contains a cycle of length at
most 8. Thus $|Y|\leqslant\binom{k}{2}$. Let $Z:=N\setminus(X\cup Y)$. Every
pair of vertices in $Z$ are at distance at least 3 in $G-A$. For each vertex
$v\in Z$, if $v$ is isolated in $G-A$ then $\deg_{\\_}G(v)\leqslant 1$, and by
induction,

$\displaystyle|E(G)\leqslant|E(G-v)|+1\leqslant\tfrac{25}{14}(n-1)+\tfrac{9}{7}\gamma+(k+1)\tbinom{k}{2}+1\leqslant\tfrac{25}{14}n+\tfrac{9}{7}\gamma+(k+1)\tbinom{k}{2}.$

Now assume that no vertex in $Z$ is isolated in $G-A$. Thus
$|N_{\\_}{G-A}[v]|\geqslant 2$ for each vertex $v\in Z$, and
$N_{\\_}{G-A}[v]\cap N_{\\_}{G-A}[w]=\varnothing$ for all distinct $v,w\in Z$.
Hence $|Z|\leqslant\frac{1}{2}(n-|A|)$. Now,

$\displaystyle|E(G)|$ $\displaystyle\leqslant|E(G-A)|+|E(G[A])|+k|X|+|Y|+|Z|$
$\displaystyle\leqslant\tfrac{9}{7}(n-|A|+\gamma-2)+\tbinom{k}{2}+(k+1)\tbinom{k}{2}+\tfrac{1}{2}(n-|A|)$
$\displaystyle\leqslant\tfrac{25}{14}n+\tfrac{9}{7}\gamma+(k+2)\tbinom{k}{2},$

as desired. ∎

The next result shows that Lemma 5 cannot prove 2-colourability for 1-apex
graphs with girth 5.

######  Proposition 24.

For infinitely many values of $n$ there is an $n$-vertex $1$-apex graph with
girth 5 and with $(2-o(1))n$ edges.

###### Proof.

Let $G$ be an $n$-vertex planar square grid graph with vertices labelled by
their coordinates $(x,y)$. Let $G^{\prime}$ be the graph obtained from $G$ by
subdividing each edge $(x,y)(x,y+1)$ where $x+y$ is even once. Each face of
$G^{\prime}$ has size 5, and any two division vertices are at distance at
least 3 in $G^{\prime}$. Let $G^{\prime\prime}$ be obtained from $G^{\prime}$
by adding a vertex $v$ adjacent to every division vertex in $G^{\prime}$. By
construction, $G^{\prime\prime}$ is a $1$-apex graph. Moreover,
$G^{\prime\prime}$ has girth 5, since any two division vertices are at
distance at least 3 in $G^{\prime}$. Note that $G$ has $(2-o(1))n$ edges and
$(1-o(1))n$ faces. Thus $G^{\prime}$ has $n$ original vertices,
$(\frac{1}{2}-o(1))n$ division vertices, and $(\frac{5}{2}-o(1))n$ edges.
Hence $G^{\prime\prime}$ has $(\frac{3}{2}-o(1))n$ vertices and $(3-o(1))n$
edges. The result follows. ∎

The next result shows that Lemma 5 cannot prove 2-colourability for $k$-apex
graphs with girth 8.

######  Proposition 25.

For infinitely many values of $n$ there is an $n$-vertex $23$-apex graph with
girth 8 and with $(2-o(1))n$ edges.

###### Proof.

Let $G$ be an $n$-vertex planar square grid graph. Let $G^{\prime}$ be the
graph obtained from $G$ by subdividing each edge once. Each division vertex of
$G^{\prime}$ is at distance at most 5 from at most 22 other division vertices.
Thus each division vertex of $G^{\prime}$ can be coloured by one element of
$\\{1,\dots,23\\}$ so that any two vertices of the same colour are at distance
at least 6 in $G^{\prime}$. Let $G^{\prime\prime}$ be obtained from
$G^{\prime}$ by adding a set of vertices $A:=\\{v_{\\_}1,\dots,v_{\\_}{23}\\}$
where each $v_{\\_}i$ is adjacent to every vertex in $G^{\prime}$ coloured
$i$. By construction, $G^{\prime\prime}$ is a $23$-apex graph. We claim it has
girth 8. clearly, every cycle in $G$ has length at least 8. Consider a cycle
$C$ that intersects $A$. If $C\cap A=\\{v_{\\_}i\\}$, then $|C|\geqslant 8$
since vertices of $G^{\prime}$ coloured $i$ are at distance at least 6 in
$G^{\prime}$. If $C\cap A=\\{v_{\\_}i,v_{\\_}j\\}$, then $|C|\geqslant 8$
since vertices of $G^{\prime}$ coloured $i$ and $j$ are at distance at least 2
in $G^{\prime}$. Similarly, if $|C\cap A|\geqslant 3$ then $|C|\geqslant 12$.
Hence $G$ has girth 8. Note that $G$ has $(2-o(1))n$ edges. Thus $G^{\prime}$
has $n$ original vertices, $(2-o(1))n$ division vertices, and $(4-o(1))n$
edges. Hence $G^{\prime\prime}$ has $(3-o(1))n$ vertices and $(6-o(1))n$
edges. The result follows. ∎

######  Theorem 26.

Every $(\gamma,k)$-apex graph with girth at least 5 is 3-colourable with
clustering at most some function $f(\gamma,k)$.

###### Proof.

Let $G$ be an $n$-vertex $(\gamma,k)$-apex graph, where $n\geqslant
n_{\\_}0:=6(\tfrac{5}{3}\gamma+(k+1)\tbinom{k}{2})$. By Lemma 27 below,
$|E(G)|\leqslant\tfrac{8}{3}n+\tfrac{5}{3}\gamma+(k+1)\tbinom{k}{2}\leqslant\tfrac{17}{6}n$.
By a result of Alon et al. [1], $G$ has a balanced separator of size
$cn^{1/2}$ for some $c=c(\gamma,k)$. The result now follows from Lemma 5 with
$\varepsilon=\frac{1}{2}$ and $\delta=\frac{1}{6}$ and $k=3$. ∎

######  Lemma 27.

Every $n$-vertex $(\gamma,k)$-apex graph $G$ with girth at least 5 has at most
$\tfrac{8}{3}n+\tfrac{5}{3}\gamma+(k+1)\tbinom{k}{2}$ edges.

###### Proof.

By assumption, there exists $A\subseteq V(G)$ with $|A|\leqslant k$ such that
$G-A$ has Euler genus at most $\gamma$. By Euler’s formula, $G-A$ has at most
$\frac{5}{3}(n-|A|+\gamma-2)$ edges. Let $N$ be the set of vertices in $G-A$
adjacent to at least one vertex in $A$. Let $X$ be the set of vertices in $N$
adjacent to at least two vertices in $A$. Thus $|X|\leqslant\binom{k}{2}$, as
otherwise there exists two vertices in $X$ adjacent to the same two vertices
in $A$, implying that $G$ contains a 4-cycle. Now,

$\displaystyle|E(G)|\leqslant|E(G-A)|+|E(G[A])|+k|X|+|N|$
$\displaystyle\leqslant\tfrac{5}{3}(n-|A|+\gamma-2)+\tbinom{k}{2}+k\tbinom{k}{2}+n$
$\displaystyle\leqslant\tfrac{8}{3}n+\tfrac{5}{3}\gamma+(k+1)\tbinom{k}{2},$

as desired. ∎

##  5 Increasing Girth

Thomassen [66] first showed that graphs with minimum degree 3 and sufficiently
large girth contains a minor with large minimum degree. In particular, every
graph with minimum degree at least 3 and girth at least $4k-3$ contains a
minor with minimum degree $k$. Mader [51] improved the bounds substantially,
by showing that every graph with minimum degree at least 3 and girth at least
$8k+3$ contains a minor with minimum degree $2^{k}$. Kühn and Osthus [41]
improved the constant $8$ to $4$ as follows:

######  Lemma 28 ([41]).

For any integers $k\geqslant 1$ and $r\geqslant 3$ every graph $G$ of minimum
degree $r$ and girth at least $4k+3$ contains a minor of minimum degree at
least $\frac{1}{48}(r-1)^{k+1}$.

We use Lemma 28 and the following lemma independently due to Kostochka [36,
37] and Thomason [64, 65] to show that graphs excluding a fixed minor and with
large girth are properly 3-colourable.

######  Lemma 29 ([64, 65, 36, 37]).

Every $K_{\\_}t$-minor-free graph has minimum degree at most $ct\sqrt{\log t}$
for some absolute constant $c$.

######  Proposition 30.

Every $K_{\\_}t$-minor-free graph $G$ with girth at least
$(4+o(1))\log_{\\_}2t$ is 3-colourable.

###### Proof.

The precise girth bound we assume is $4k+3$ where
$k:=\lfloor\log_{\\_}2(48ct\sqrt{\log t})\rfloor$ and $c$ is from Lemma 29. We
claim that $G$ is 2-degenerate. Otherwise, $G$ has a subgraph with minimum
degree at least 3. By Lemma 28, we have $\frac{1}{48}2^{k+1}\leqslant
ct\sqrt{\log t}$, implying $k\leqslant\log_{\\_}2(48ct\sqrt{\log t})-1$, which
contradicts the definition of $k$. Hence $G$ is 2-degenerate and properly
3-colourable. ∎

Of course, three colours is best possible in Proposition 30 since odd cycles
are $K_{\\_}4$-minor-free with arbitrarily large girth.

Kühn and Osthus [41] used Lemma 28 and a variant of Lemma 29 with explicit
bounds on the constant $c$ to conclude that $K_{\\_}t$-minor-free graphs with
girth at least $19$ are properly $(t-1)$-colourable, thus satisfying
Hadwiger’s Conjecture. In fact, the method of Kühn and Osthus [41] gives
asymptotically stronger results for graphs of girth $g\geqslant 5$. To see
this, we use the following lemma of Kühn and Osthus [41], which is applicable
for girth at least 5 whereas Lemma 28 assumes girth at least 7.

######  Lemma 31 ([41]).

For any integers $k\geqslant 1$ and $r\geqslant\max\\{5k,2\,000\,000\\}$,
every graph $G$ of minimum degree at least $4r$ and girth at least $4k+1$
contains a minor of minimum degree at least $\frac{1}{288}r^{(2k+1)/2}$.

######  Proposition 32.

For any integer $k\geqslant 1$, every $K_{\\_}t$-minor-free graph $G$ with
girth at least $4k+1$ is properly $O((t\sqrt{\log t})^{2/(2k+1)})$-colourable.

###### Proof.

We claim that $G$ is $4r$-degenerate where

$r:=\max\\{\lfloor(288ct\sqrt{\log t})^{2/(2k+1)}\rfloor+1,5k,2\,000\,000\\}$

and $c$ is from Lemma 29. Suppose that a subgraph of $G$ has minimum degree at
least $4r$. By Lemmas 29 and 31, we have $\frac{1}{288}r^{(2k+1)/2}\leqslant
ct\sqrt{\log t}$, implying $r\leqslant(288ct\sqrt{\log t})^{2/(2k+1)}$, which
contradicts the definition of $r$. Hence $G$ is $4r$-degenerate and
$\chi(G)\leqslant 4r+1\in O((t\sqrt{\log t})^{2/(2k+1)})$. ∎

For example, Proposition 32 shows $\chi(G)\leqslant O((t\sqrt{\log t})^{2/3})$
for girth $5$, and $\chi(G)\leqslant O((t\sqrt{\log t})^{2/5})$ for girth $9$.

For clustered colouring, we show that two colours suffice if we allow the
smallest possible amount of clustering.

######  Theorem 33.

Every $K_{\\_}t$-minor-free graph with girth at least $(16+o(1))\log_{\\_}2t$
is 2-colourable with clustering 2.

###### Proof.

The precise girth lower bound we use is $16\log_{\\_}2(ct\sqrt{\log t})+11$,
where $c$ is from Lemma 29. We proceed by induction on $|V(G)|$. First suppose
that $\deg_{\\_}G(v)\leqslant 1$ for some vertex $v$. By induction, $G-v$ is
2-colourable with clustering at most 2. Colour $v$ by a colour not used by its
neighbour. So $G$ is 2-coloured with clustering at most 2. Now assume that $G$
has minimum degree at least 2. Suppose that $G$ has an edge $vw$ with
$\deg_{\\_}G(v)=\deg_{\\_}G(w)=2$. By induction, $G-v-w$ is 2-colourable with
clustering at most 2. Colour $v$ by a colour not used by its neighbour
different from $w$. Colour $w$ by a colour not used by its neighbour different
from $v$. So the monochromatic component containing $v$ or $w$ has at most two
vertices (namely, $v$ and $w$). Now $G$ is 2-coloured with clustering at most
2. Now assume that for each edge $vw$ of $G$, at least one of $v$ and $w$ has
degree at least 3. Let $g$ be the integer such that $G$ has girth in
$\\{8g+3,\dots,8g+10\\}$. By Lemma 34 below, there is a minor $G^{\prime}$ of
$G$ with minimum degree at least $2^{g/2}$. By Lemma 29, we have
$2^{g/2}\leqslant ct\sqrt{\log t}$. Hence $G$ has girth at most
$8g+10\leqslant 10+16\log_{\\_}2(ct\sqrt{\log t})$, which contradicts the
starting assumption. ∎

It remains to prove the following lemma, which is a variant of the above-
mentioned result of Mader [51].

######  Lemma 34.

Let $G$ be a graph with:

  * •

girth at least $8k+3$ for some integer $k\geqslant 1$,

  * •

minimum degree at least 2, and

  * •

no edge $vw$ with $\deg_{\\_}G(v)=\deg_{\\_}G(w)=2$.

Then $G$ has a minor with minimum degree at least $2^{k/2}$.

###### Proof.

Let $X$ be a maximal set of vertices in $G$ at pairwise distance at least
$2k+1$. For each $x\in X$, let $B_{\\_}x$ be the ball of radius $k$ around
$x$. So $B_{\\_}x\cap B_{\\_}y=\varnothing$ for all distinct $x,y\in X$. Since
$G$ has girth greater than $2k+1$, the induced subgraph $G[B_{\\_}x]$ is a
tree. By assumption, $G$ has minimum degree at least 2, and no edge $vw$ in
$G$ has $\deg_{\\_}G(v)=\deg_{\\_}G(w)=2$. Thus $G[B_{\\_}x]$ has at least
$2^{k/2}$ leaves. Let $V_{\\_}i:=\\{v\in
V(G):\operatorname{dist}_{\\_}G(v,X)=i\\}$. By the maximality of $X$, we have
$V(G)=\bigcup_{\\_}{i=0}^{2k}V_{\\_}i$. For each $x\in X$, let
$B^{\prime}_{\\_}x$ be a superset of $B_{\\_}x$ obtained as follows. For
$i=k+1,k+2,\dots,2k$ each vertex $v\in V_{\\_}i$ has a neighbour in
$V_{\\_}{i-1}\cap B^{\prime}_{\\_}x$ for some $x\in X$; add $v$ to
$B^{\prime}_{\\_}x$. Thus $B^{\prime}_{\\_}x$ is a subset of the ball of
radius $2k$ around $x$. Since $G$ has girth greater than $4k+1$, the induced
subgraph $G[B^{\prime}_{\\_}x]$ is a (connected) tree. By construction,
$\bigcup_{\\_}{x\in X}B^{\prime}_{\\_}x=V(G)$. Moreover, the number of edges
between $B^{\prime}_{\\_}x$ and $\bigcup_{\\_}{y\neq x}B^{\prime}_{\\_}y$ is
at least the number of leaves in $G[B_{\\_}x]$ which is at least $2^{k/2}$.
For all distinct $x,y\in X$ there is at most one edge between
$B^{\prime}_{\\_}x$ and $B^{\prime}_{\\_}y$, since otherwise $G$ would contain
a cycle of length at most $8k+2$. Let $G^{\prime}$ be obtained from $G$ by
contracting each set $B^{\prime}_{\\_}x$ to a single vertex. Thus $G^{\prime}$
has minimum degree at least $2^{k/2}$. ∎

##  6 Open Problems

Closing the gaps in the lower and upper bounds in Tables 3 and 4 are natural
open problems that arise from this work. In particular:

(1) For the class of triangle-free graphs with treedepth $k$, Theorem 9 says
that the defective chromatic number, clustered chromatic number and chromatic
number are equal. But what is this value? The best known lower bound is
$(1-o(1))\sqrt{2k}$ (see Theorem 10). Theorem 1 provides an upper bound of
$\lceil\frac{k+1}{2}\rceil$. A $o(k)$ upper bound can be obtained as follows.
Dvořák and Kawarabayashi [18] showed that the maximum chromatic number of
triangle-free graphs with treewidth $k$ equals the maximum online chromatic
number of triangle-free graphs with pathwidth $k$. An analogous approach shows
that the maximum chromatic number of triangle-free graphs of treedepth $k$
equals the maximum online chromatic number of triangle-free graphs on $k$
vertices. This result holds with the triangle-free condition replaced by
$K_{\\_}p$-free for any fixed $p$. Results of Lovász et al. [50]
imply333Lovász et al. [50] describe an online algorithm that partitions an
$n$-vertex graph into $\lceil n/\log_{\\_}2\log_{\\_}2n\rceil$ independent
sets and at most $4n/\log_{\\_}2\log_{\\_}2n$ ‘residual’ sets, where each
residual set is a subset of the neighbourhood of a vertex. So for triangle-
free graphs, each residual set is independent. Hence the online chromatic
number of $n$-vertex triangle-free graphs is in $O(n/\log\log n)$. See [27]
for related work. that the online chromatic number of triangle-free graphs on
$k$ vertices is in $O(k/\log\log k)$. Thus, triangle-free graphs of treedepth
$k$ are $O(k/\log\log k)$-colourable. As far as we are aware, it is possible
that triangle-free graphs with treedepth $k$ are properly
$O(\sqrt{k})$-colourable. This would strengthen the fact that triangle-free
$k$-vertex graphs are properly $O(\sqrt{k})$-colourable, which is easily
proved as a consequence of Brooks’ Theorem.

(2) Are triangle-free $(\gamma,k)$-apex graphs 3-colourable with bounded
clustering? Note that $K_{\\_}{k+2,n}$ is a triangle-free $k$-apex graph with
$(k+2)n$ edges. So Lemma 5 does not help here.

(3) Are graphs with girth at least some constant $g$ (possibly 7) and with
bounded treewidth (or bounded pathwidth) 2-colourable with bounded clustering?
The answer is ‘yes’ for graphs $G$ with treewidth 2 and girth at least 5,
since such graphs are planar, so $|E(G)|<\frac{5}{3}|V(G)|$ by Euler’s
Formula, and the claim follows from Lemma 5. Perhaps Lemma 5 can be used to
answer the treewidth 3 case. But for larger values of treewidth, it seems a
more tailored approach is needed. Note that $g\geqslant 7$ by Proposition 16.

(4) Are $K_{\\_}t$-minor-free graphs with girth at least some constant $g$
(possibly 5) 3-colourable with bounded clustering? Note that $g\geqslant 5$ by
Corollary 11. In fact, 2 colours may suffice. Are $K_{\\_}t$-minor-free graphs
with girth at least some constant $g$ (possibly 7) 2-colourable with bounded
clustering? Here $g\geqslant 7$ by Proposition 16.

(5) What is the clustered chromatic number of the class of triangle-free
$K_{\\_}t$-minor-free graphs. Without the triangle-free assumption, the answer
is $t-1$, as proved by Dujmović et al. [15] (and announced earlier by Dvořák
and Norin [17]). The best lower bound is $\lceil\frac{t+1}{2}\rceil$, which
follows from Corollary 14 since graphs of treewidth $k$ are
$K_{\\_}{k+2}$-minor-free.

Note that for proper colourings of $K_{\\_}t$-minor-free graphs, improved
bounds are known when we additionally exclude a fixed triangle or fixed
complete graph. In particular, Delcourt and Postle [10] proved a $O(t)$ upper
bound for $K_{\\_}t$-minor-free graphs excluding any fixed complete subgraph.

## References

  * Alon et al. [1990] Noga Alon, Paul Seymour, and Robin Thomas.  A separator theorem for nonplanar graphs.  _J. Amer. Math. Soc._ , 3(4):801–808, 1990.
  * Archdeacon [1987] Dan Archdeacon.  A note on defective colorings of graphs in surfaces.  _J. Graph Theory_ , 11(4):517–519, 1987.
  * Birmelé [2003] Etienne Birmelé.  Tree-width and circumference of graphs.  _J. Graph Theory_ , 43(1):24–25, 2003.
  * Briański et al. [2023] Marcin Briański, Gwenaël Joret, Konrad Majewski, Piotr Micek, Michał T. Seweryn, and Roohani Sharma.  Treedepth vs circumference.  _Combinatorica_ , 43:659–664, 2023.  arXiv:2211.11410.
  * Chen and Schelp [1993] Guantao Chen and Richard H. Schelp.  Graphs with linearly bounded Ramsey numbers.  _J. Combin. Theory Ser. B_ , 57(1):138–149, 1993.
  * Choi et al. [2017] Hojin Choi, Ilkyoo Choi, Jisu Jeong, and Geewon Suh.  $(1,k)$-coloring of graphs with girth at least five on a surface.  _J. Graph Theory_ , 84(4):521–535, 2017.
  * Choi and Esperet [2019] Ilkyoo Choi and Louis Esperet.  Improper coloring of graphs on surfaces.  _J. Graph Theory_ , 91(1):16–34, 2019.
  * Cowen et al. [1997] Lenore Cowen, Wayne Goddard, and C. Esther Jesurum.  Defective coloring revisited.  _J. Graph Theory_ , 24(3):205–219, 1997.
  * Cowen et al. [1986] Lenore J. Cowen, Robert Cowen, and Douglas R. Woodall.  Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency.  _J. Graph Theory_ , 10(2):187–195, 1986.
  * Delcourt and Postle [2021] Michelle Delcourt and Luke Postle.  Reducing linear Hadwiger’s conjecture to coloring small graphs.  2021, arXiv:2108.01633.
  * Diestel [2018] Reinhard Diestel.  Graph theory, vol. 173 of _Graduate Texts in Mathematics_.  Springer, 5th edn., 2018.
  * Dirac [1952] Gabriel A. Dirac.  Some theorems on abstract graphs.  _Proc. London Math. Soc. (3)_ , 2:69–81, 1952.
  * Djidjev [1985] Hristo N. Djidjev.  A separator theorem for graphs of fixed genus.  _Serdica_ , 11(4):319–329, 1985.
  * Dujmović et al. [2022] Vida Dujmović, Louis Esperet, Pat Morin, Bartosz Walczak, and David R. Wood.  Clustered 3-colouring graphs of bounded degree.  _Combin. Probab. Comput._ , 31(1):123–135, 2022.
  * Dujmović et al. [2023] Vida Dujmović, Louis Esperet, Pat Morin, and David R. Wood.  Proof of the clustered Hadwiger conjecture.  In _Proc. 64th IEEE Annual Symposium on Foundations of Computer Science(FOCS ’23)_, pp. 1921–1930. 2023.  arXiv:2306.06224.
  * Dvořák [2013] Zdeněk Dvořák.  Constant-factor approximation of the domination number in sparse graphs.  _European J. Comb._ , 34(5):833–840, 2013.
  * Dvořák and Norin [2017] Zdeněk Dvořák and Sergey Norin.  Islands in minor-closed classes. I. Bounded treewidth and separators.  2017, arXiv:1710.02727.
  * Dvořák and Kawarabayashi [2017] Zdeněk Dvořák and Ken-ichi Kawarabayashi.  Triangle-free graphs of tree-width $t$ are $\lceil(t+3)/2\rceil$-colorable.  _European J. Combin._ , 66:95–100, 2017.
  * Eaton and Hull [1999] Nancy Eaton and Thomas Hull.  Defective list colorings of planar graphs.  _Bull. Inst. Combin. Appl_ , 25:79–87, 1999.
  * Edwards et al. [2015] Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, and Paul Seymour.  A relative of Hadwiger’s conjecture.  _SIAM J. Discrete Math._ , 29(4):2385–2388, 2015.
  * Erdős [1959] Paul Erdős.  Graph theory and probability.  _Canad. J. Math._ , 11:34–38, 1959.
  * Esperet and Ochem [2016] Louis Esperet and Pascal Ochem.  Islands in graphs on surfaces.  _SIAM J. Discrete Math._ , 30(1):206–219, 2016.
  * Gilbert et al. [1984] John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan.  A separator theorem for graphs of bounded genus.  _J. Algorithms_ , 5(3):391–407, 1984.
  * Grohe et al. [2018] Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos.  Coloring and covering nowhere dense graphs.  _SIAM J. Discrete Math._ , 32(4):2467–2481, 2018.
  * Grohe et al. [2017] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz.  Deciding first-order properties of nowhere dense graphs.  _J. ACM_ , 64(3):Art. 17, 2017.
  * Grötzsch [5859] Herbert Grötzsch.  Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel.  _Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe_ , 8:109–120, 1958/59.
  * Gutowski et al. [2014] Grzegorz Gutowski, Jakub Kozik, Piotr Micek, and Xuding Zhu.  Lower bounds for on-line graphs colorings.  In _Algorithms and computation_ , vol. 8889 of _Lecture Notes in Comput. Sci._ , pp. 507–515. Springer, 2014.
  * Havet and Sereni [2006] Frédéric Havet and Jean-Sébastien Sereni.  Improper choosability of graphs and maximum average degree.  _J. Graph Theory_ , 52(3):181–199, 2006.
  * Kang and Oum [2019] Dong Yeap Kang and Sang-il Oum.  Improper coloring of graphs with no odd clique minor.  _Combin. Probab. Comput._ , 28(5):740–754, 2019.
  * Kawarabayashi [2008] Ken-ichi Kawarabayashi.  A weakening of the odd Hadwiger’s conjecture.  _Combin. Probab. Comput._ , 17(6):815–821, 2008.
  * Kawarabayashi and Mohar [2007] Ken-ichi Kawarabayashi and Bojan Mohar.  A relaxed Hadwiger’s conjecture for list colorings.  _J. Combin. Theory Ser. B_ , 97(4):647–651, 2007.
  * Kawarabayashi and Thomassen [2012] Ken-ichi Kawarabayashi and Carsten Thomassen.  From the plane to higher surfaces.  _J. Combin. Theory Ser. B_ , 102(4):852–868, 2012.
  * Kierstead and Trotter [1994] Hal A. Kierstead and William T. Trotter.  Planar graph coloring with an uncooperative partner.  _J. Graph Theory_ , 18(6):569–584, 1994.
  * Kierstead and Yang [2003] Hal A. Kierstead and Daqing Yang.  Orderings on graphs and game coloring number.  _Order_ , 20(3):255–264, 2003.
  * Kim [1995] Jeong Han Kim.  The Ramsey number $R(3,t)$ has order of magnitude $t^{2}/\log t$.  _Random Structures Algorithms_ , 7(3):173–207, 1995.
  * Kostochka [1982] Alexandr V. Kostochka.  The minimum Hadwiger number for graphs with a given mean degree of vertices.  _Metody Diskret. Analiz._ , 38:37–58, 1982.
  * Kostochka [1984] Alexandr V. Kostochka.  Lower bound of the Hadwiger number of graphs by their average degree.  _Combinatorica_ , 4(4):307–316, 1984.
  * Kostochka and Nešetřil [1999] Alexandr V. Kostochka and Jaroslav Nešetřil.  Properties of Descartes’ construction of triangle-free graphs with high chromatic number.  _Combin. Probab. Comput._ , 8(5):467–472, 1999.
  * Kostochka et al. [1997] Alexandr V. Kostochka, Éric Sopena, and Xuding Zhu.  Acyclic and oriented chromatic numbers of graphs.  _J. Graph Theory_ , 24(4):331–340, 1997.
  * Kreutzer et al. [2016] Stephan Kreutzer, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz.  The generalised colouring numbers on classes of bounded expansion.  In Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier, eds., _41st Int’l Symp. on Mathematical Foundations of Comput. Sci. (MFCS ’16)_ , vol. 58 of _Leibniz Int. Proc. Inform._ , pp. 85:1–85:13. Schloss Dagstuhl, 2016.
  * Kühn and Osthus [2003] Daniela Kühn and Deryk Osthus.  Minors in graphs of large girth.  _Random Structures Algorithms_ , 22(2):213–225, 2003.
  * Lipton and Tarjan [1979] Richard J. Lipton and Robert E. Tarjan.  A separator theorem for planar graphs.  _SIAM J. Appl. Math._ , 36(2):177–189, 1979.
  * Lipton and Tarjan [1980] Richard J. Lipton and Robert E. Tarjan.  Applications of a planar separator theorem.  _SIAM J. Comput._ , 9(3):615–627, 1980.
  * Liu [pear] Chun-Hung Liu.  Defective coloring is perfect for minors.  _Combinatorica_ , to appear.  arXiv:2208.10729.
  * Liu and Oum [2018] Chun-Hung Liu and Sang-il Oum.  Partitioning $H$-minor free graphs into three subgraphs with no large components.  _J. Combin. Theory Ser. B_ , 128:114–133, 2018.
  * Liu and Wood [2019a] Chun-Hung Liu and David R. Wood.  Clustered coloring of graphs excluding a subgraph and a minor.  2019a, arXiv:1905.09495.
  * Liu and Wood [2019b] Chun-Hung Liu and David R. Wood.  Clustered graph coloring and layered treewidth.  2019b, arXiv:1905.08969.
  * Liu and Wood [2022] Chun-Hung Liu and David R. Wood.  Clustered variants of Hajós’ conjecture.  _J. Combin. Theory Ser. B_ , 152:27–54, 2022.
  * Liu and Wood [2023] Chun-Hung Liu and David R. Wood.  Clustered coloring of graphs with bounded layered treewidth and bounded degree.  _European J. Combin._ , p. 103730, 2023.
  * Lovász et al. [1989] László Lovász, Michael E. Saks, and William T. Trotter.  An on-line graph coloring algorithm with sublinear performance ratio.  _Discret. Math._ , 75(1-3):319–325, 1989.
  * Mader [1998] Wolfgang Mader.  Topological subgraphs in graphs of large girth.  _Combinatorica_ , 18(3):405–412, 1998.
  * Marshall and Wood [2015] Emily Abernethy Marshall and David R. Wood.  Circumference and pathwidth of highly connected graphs.  _J. Graph Theory_ , 79(3):222–232, 2015.
  * Mohar et al. [2017] Bojan Mohar, Bruce Reed, and David R. Wood.  Colourings with bounded monochromatic components in graphs of given circumference.  _Australas. J. Combin._ , 69(2):236–242, 2017.
  * Mohar and Thomassen [2001] Bojan Mohar and Carsten Thomassen.  Graphs on surfaces.  Johns Hopkins University Press, 2001.
  * Nešetřil and Ossona de Mendez [2012] Jaroslav Nešetřil and Patrice Ossona de Mendez.  Sparsity, vol. 28 of _Algorithms and Combinatorics_.  Springer, 2012.
  * Norin [2015] Sergey Norin.  Conquering graphs of bounded treewidth.  2015\.  Unpublished manuscript.
  * Norin et al. [2019] Sergey Norin, Alex Scott, Paul Seymour, and David R. Wood.  Clustered colouring in minor-closed classes.  _Combinatorica_ , 39(6):1387–1412, 2019.
  * Norin et al. [2023] Sergey Norin, Alex Scott, and David R. Wood.  Clustered colouring of graph classes with bounded treedepth or pathwidth.  _Combin. Probab. Comput._ , 32:122–133, 2023.
  * Ossona de Mendez et al. [2019] Patrice Ossona de Mendez, Sang-il Oum, and David R. Wood.  Defective colouring of graphs excluding a subgraph or minor.  _Combinatorica_ , 39(2):377–410, 2019.
  * Poh [1990] Roger K. S. Poh.  On the linear vertex-arboricity of a planar graph.  _J. Graph Theory_ , 14(1):73–75, 1990.
  * Robertson et al. [1997] Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas.  The four-colour theorem.  _J. Combin. Theory Ser. B_ , 70(1):2–44, 1997.
  * Škrekovski [1999] Riste Škrekovski.  A Grötzsch-type theorem for list colourings with impropriety one.  _Combin. Probab. Comput._ , 8(5):493–507, 1999.
  * Steinberg and Younger [1989] Richard Steinberg and D. H. Younger.  Grötzsch’s theorem for the projective plane.  _Ars Combin._ , 28:15–31, 1989.
  * Thomason [1984] Andrew Thomason.  An extremal function for contractions of graphs.  _Math. Proc. Cambridge Philos. Soc._ , 95(2):261–265, 1984.
  * Thomason [2001] Andrew Thomason.  The extremal function for complete minors.  _J. Combin. Theory Ser. B_ , 81(2):318–338, 2001.
  * Thomassen [1983] Carsten Thomassen.  Girth in graphs.  _J. Combin. Theory Ser. B_ , 35(2):129–141, 1983.
  * Thomassen [1994] Carsten Thomassen.  Grötzsch’s $3$-color theorem and its counterparts for the torus and the projective plane.  _J. Combin. Theory Ser. B_ , 62(2):268–279, 1994.
  * Thomassen [2003] Carsten Thomassen.  A short list color proof of Grötzsch’s theorem.  _J. Combin. Theory Ser. B_ , 88(1):189–192, 2003.
  * van den Heuvel et al. [2017] Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz.  On the generalised colouring numbers of graphs that exclude a fixed minor.  _European J. Combin._ , 66:129–144, 2017.
  * van den Heuvel and Wood [2018] Jan van den Heuvel and David R. Wood.  Improper colourings inspired by Hadwiger’s conjecture.  _J. London Math. Soc._ , 98:129–148, 2018.  arXiv:1704.06536.
  * Škrekovski [1999] Riste Škrekovski.  List improper colourings of planar graphs.  _Combin. Probab. Comput._ , 8(3):293–299, 1999.
  * Škrekovski [2000] Riste Škrekovski.  List improper colorings of planar graphs with prescribed girth.  _Discrete Math._ , 214(1-3):221–233, 2000.
  * Wood [2010] David R. Wood.  Contractibility and the Hadwiger conjecture.  _European J. Combin._ , 31(8):2102–2109, 2010.
  * Wood [2018] David R. Wood.  Defective and clustered graph colouring.  _Electron. J. Combin._ , DS23, 2018.  Version 1.
  * Zhu [2009] Xuding Zhu.  Colouring graphs with bounded generalized colouring number.  _Discrete Math._ , 309(18):5562–5568, 2009.