Defective and Clustered Graph Colouring*** © David R. Wood. Released under the
CC BY license (International 4.0).
This is a preliminary version of a dynamic survey to be published in the
_Electronic Journal of Combinatorics_ , #DS23,
http://www.combinatorics.org/DS23.

David R. Wood †††School of Mathematical Sciences, Monash University,
Melbourne, Australia (david.wood@monash.edu).
Research supported by the Australian Research Council.

_Abstract._ Consider the following two ways to colour the vertices of a graph
where the requirement that adjacent vertices get distinct colours is relaxed.
A colouring has _defect_ $d$ if each monochromatic component has maximum
degree at most $d$. A colouring has _clustering_ $c$ if each monochromatic
component has at most $c$ vertices. This paper surveys research on these types
of colourings, where the first priority is to minimise the number of colours,
with small defect or small clustering as a secondary goal. List colouring
variants are also considered. The following graph classes are studied:
outerplanar graphs, planar graphs, graphs embeddable in surfaces, graphs with
given maximum degree, graphs with given maximum average degree, graphs
excluding a given subgraph, graphs with linear crossing number, linklessly or
knotlessly embeddable graphs, graphs with given Colin de Verdière parameter,
graphs with given circumference, graphs excluding a fixed graph as an
immersion, graphs with given thickness, graphs with given stack- or queue-
number, graphs excluding $K_{t}$ as a minor, graphs excluding $K_{s,t}$ as a
minor, and graphs excluding an arbitrary graph $H$ as a minor. Several open
problems are discussed.

###### Contents

  1. 1 Introduction
    1. 1.1 History and Terminology
    2. 1.2 Definitions
    3. 1.3 Choosability
    4. 1.4 Standard Examples
    5. 1.5 Two Fundamental Observations
    6. 1.6 Related Topics
  2. 2 Greedy Approaches
    1. 2.1 Light Edges
    2. 2.2 Islands
  3. 3 Graphs on Surfaces
    1. 3.1 Outerplanar Graphs
    2. 3.2 Planar Graphs
    3. 3.3 Hex Lemma
    4. 3.4 Defective Colouring of Graphs on Surfaces
    5. 3.5 Clustered Colouring of Graphs on Surfaces
  4. 4 Maximum Degree
  5. 5 Maximum Average Degree
  6. 6 Excluding a Subgraph
  7. 7 Excluding a Shallow Minor
    1. 7.1 Excluding $K_{s,t}^{*}$
    2. 7.2 Linklessly Embeddable Graphs
    3. 7.3 Knotlessly Embeddable Graphs
    4. 7.4 Colin de Verdière Parameter
    5. 7.5 Crossings
    6. 7.6 Stack and Queue Layouts
    7. 7.7 Excluded Immersions
  8. 8 Minor-Closed Classes
    1. 8.1 Excluding a Minor and Bounded Degree
    2. 8.2 $K_{t}$-Minor-Free Graphs
    3. 8.3 $H$-Minor-Free Graphs
    4. 8.4 Conjectures
    5. 8.5 Circumference
  9. 9 Thickness
    1. 9.1 Defective Colouring
    2. 9.2 Clustered Colouring
  10. 10 General Setting

##  1 Introduction

Consider a graph where each vertex is assigned a colour. A _monochromatic
component_ is a connected component of the subgraph induced by all the
vertices assigned a single colour. A graph $G$ is $k$-colourable with
_clustering_ $c$ if each vertex can be assigned one of $k$ colours such that
each monochromatic component has at most $c$ vertices. A graph $G$ is
$k$-colourable with _defect_ $d$ if each vertex of $G$ can be assigned one of
$k$ colours such that each vertex is adjacent to at most $d$ neighbours of the
same colour; that is, each monochromatic component has maximum degree at most
$d$.

This paper surveys results and open problems regarding clustered and defective
graph colouring, where the first priority is to minimise the number of
colours, with small defect or small clustering as a secondary goal. We include
various proofs that highlight the main methods employed. The emphasis is on
general results for broadly defined classes of graphs, rather than more
precise results for more specific classes. With this viewpoint the following
definitions naturally arise.

The _clustered chromatic number_ of a graph class $\mathcal{G}$, denoted by
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})$, is the
minimum integer $k$ for which there exists an integer $c$ such that every
graph in $\mathcal{G}$ has a $k$-colouring with clustering $c$. If there is no
such integer $k$, then $\mathcal{G}$ has _unbounded_ clustered chromatic
number. A graph class $\mathcal{G}$ is _defectively_ $k$-colourable if there
exists an integer $d$ such that every graph in $\mathcal{G}$ is $k$-colourable
with defect $d$. The _defective chromatic number_ of $\mathcal{G}$, denoted by
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})$, is the
minimum integer $k$ such that $\mathcal{G}$ is defectively $k$-colourable. If
there is no such integer $k$, then $\mathcal{G}$ has _unbounded_ defective
chromatic number. Every colouring of a graph with clustering $c$ has defect
$c-1$. Thus
$\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})$
for every class $\mathcal{G}$. Tables 1 and 2 summarise the results presented
in this survey; see Sections 1.2 and 1.3 for the relevant definitions.

###  1.1 History and Terminology

There is no single origin for the notions of defective and clustered graph
colouring, and the terminology used in the literature is inconsistent.

Early papers on defective colouring include [16, 17, 212, 128, 166, 138],
although these did not use the term ‘defect’. The definition of
“$k$-colourable with defect $d$”, often written _$(k,d)$ -colourable_, was
introduced by Cowen et al. [66]. This terminology is fairly standard, although
_$d$ -relaxed_ or _$d$ -improper_ is sometimes used. The minimum number of
colours in a colouring of a graph $G$ with defect $d$ has been called the _$d$
-improper chromatic number_ [144] or _$d$ -chromatic number_ [16] of $G$.
Cowen et al. [65] introduced the _defective chromatic number_ of a graph class
(as defined above).

Also for clustered colouring, the literature is inconsistent. One of the early
papers is by Kleinberg et al. [151], who defined a colouring to be _$(k,c)$
-fragmented_ if, in our language, it is a $k$-colouring with clustering $c$. I
prefer “clustering” since as $c$ increases, intuitively the “fragmentation” of
the monochromatic components decreases. Edwards and Farr [90, 89] called a
monochromatic component a _chromon_ and called the clustered chromatic number
of a class the _metachromatic number_.

Table 1: Summary of Results for Defective Colouring

graph class | $\mathcal{G}$ | $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})$ | $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{G})$ | Sect.
---|---|---|---|---
outerplanar | $\mathcal{O}$ | 2 | 2 | 3.1
planar | $\mathcal{P}$ | 3 | 3 | 3.2
Euler genus $\leqslant g$ | $\mathcal{E}_{g}$ | 3 | 3 | 3.4
max average degree $\leqslant m$ | $\mathcal{A}_{m}$ | $\lfloor{\frac{m}{2}}\rfloor+1$ | $\lfloor{\frac{m}{2}}\rfloor+1$ | 5
linklessly embeddable | $\mathcal{L}$ | $4$ | $4$ | 7.2
knotlessly embeddable | $\mathcal{K}$ | $5$ | $5$ | 7.3
Colin de Verdière $\leqslant k$ | $\mathcal{V}_{k}$ | $k$ | $k$ | 7.4
$k$-stack graphs | $\mathcal{S}_{k}$ | $k+1$ | $k+1$ | 7.6
$k$-queue graphs | $\mathcal{Q}_{k}$ | $k+1,\ldots,2k+1$ | $2k+1$ | 7.6
no $K_{t}$ immersion | $\mathcal{I}_{t}$ | $2$ | $t-1$ | 7.7
treewidth $\leqslant k$ |  | $k+1$ | $k+1$ | 8.1
treewidth $\leqslant k$, max degree $\leqslant\Delta$ | $2$ | $2$ | 8.1
no $K_{t}$-minor | $\mathcal{M}_{K_{t}}$ | $t-1$ | $t-1$ | 8.2
no $H$-minor | $\mathcal{M}_{H}$ | $\operatorname{\overline{td}}(H)-1,\ldots,2^{\operatorname{\overline{td}}(H)+1}-4$ | $\min\\{s:\exists t\,H\preceq K_{s,t}\\}$ | 8.3
no $K_{s,t}$-minor $(s\leqslant t$) | $\mathcal{M}_{K_{s,t}}$ | $s$ | $s$ | 8.4
circumference $\leqslant k$ | $\mathcal{C}_{k}$ | $\lfloor{\log_{2}k}\rfloor+1,\ldots,\lfloor{3\log_{2}k}\rfloor$ | $\lceil{\frac{k+1}{2}}\rceil$ | 8.5
no $(k+1)$-path | $\mathcal{H}_{k}$ | $\lceil{\log_{2}(k+2)}\rceil-1,\ldots,\lfloor{3\log_{2}k}\rfloor$ | $\lfloor{\frac{k+1}{2}}\rfloor$ | 8.5
$g$-thickness $\leqslant k$ | $\mathcal{T}^{g}_{k}$ | $2k+1$ | $2k+1$ | 9

Table 2: Summary of Results for Clustered Colouring

graph class | $\mathcal{G}$ | $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})$ | $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{G})$ | Sect.
---|---|---|---|---
outerplanar | $\mathcal{O}$ | 3 | 3 | 3.1
planar | $\mathcal{P}$ | 4 | 4 | 3.2
Euler genus $\leqslant g$ | $\mathcal{E}_{g}$ | 4 | 4 | 3.5
Euler genus $\leqslant g$, max degree $\leqslant\Delta$ | $3$ | $3,4$ | 8.1
max degree $\leqslant\Delta$ | $\mathcal{D}_{\Delta}$ | $\left\lfloor\frac{\Delta+6}{4}\right\rfloor,\ldots,\left\lceil{\frac{\Delta+1}{3}}\right\rceil$ | $\left\lfloor\frac{\Delta+6}{4}\right\rfloor,\ldots,\Delta+1$ | 4
max average degree $\leqslant m$ | $\mathcal{A}_{m}$ | $\lfloor{\frac{m}{2}}\rfloor+1,\ldots,\lfloor{m}\rfloor+1$ | $\lfloor{\frac{m}{2}}\rfloor+1,\ldots,\lfloor{m}\rfloor+1$ | 5
linklessly embeddable | $\mathcal{L}$ | $5$ | $5$ | 7.2
knotlessly embeddable | $\mathcal{K}$ | $6$ | $6$ | 7.3
Colin de Verdière $\leqslant k$ | $\mathcal{V}_{k}$ | open | open | 7.4
$k$-stack graphs | $\mathcal{S}_{k}$ | $k+2,\ldots,2k+2$ | $k+2\ldots 2k+2$ | 7.6
$k$-queue graphs | $\mathcal{Q}_{k}$ | $k+1,\ldots,4k$ | $k+1,\ldots,4k$ | 7.6
no $K_{t}$ immersion | $\mathcal{I}_{t}$ | $\geqslant\lfloor{\frac{t+4}{4}}\rfloor$ | $\geqslant t-1$ | 7.7
treewidth $\leqslant k$ |  | $k+1$ | $k+1$ | 8.1
treewidth $\leqslant k$, max degree $\leqslant\Delta$ | $2$ | $2$ | 8.1
no $K_{t}$-minor | $\mathcal{M}_{K_{t}}$ | $t-1,\ldots,2t-2$ | $t-1,\ldots,\lceil{\frac{31}{2}t}\rceil$ | 8.2
no $K_{t}$-minor, max degree $\leqslant\Delta$ | $3$ | $\geqslant 3$ | 8.2
no $H$-minor | $\mathcal{M}_{H}$ | $\operatorname{\overline{td}}(H)-1,\ldots,2^{\operatorname{\overline{td}}(H)+1}-4$ | open | 8.3
no $K_{s,t}$-minor $(s\leqslant t$) | $\mathcal{M}_{K_{s,t}}$ | $s+1,\ldots,2s+2$ | open | 8.4
circumference $\leqslant k$ | $\mathcal{C}_{k}$ | $\lfloor{\log_{2}k}\rfloor+1,\ldots,\lfloor{3\log_{2}k}\rfloor$ | open | 8.5
no $(k+1)$-path | $\mathcal{H}_{k}$ | $\lceil{\log_{2}(k+2)}\rceil-1,\ldots,\lfloor{3\log_{2}k}\rfloor$ | open | 8.5
$g$-thickness $\leqslant k$ | $\mathcal{T}^{g}_{k}$ | $2k+2,\ldots,6k+1$ | $2k+2,\ldots,6k+1$ | 9

###  1.2 Definitions

This section briefly states standard graph theoretic definitions, familiar to
most readers.

A _clique_ in a graph is a set of pairwise adjacent vertices.

Let $G$ be a graph. A _$k$ -colouring_ of $G$ is a function that assigns one
of $k$ colours to each vertex of $G$. An edge $vw$ of $G$ is _bichromatic_ if
$v$ and $w$ are assigned distinct colours. A vertex $v$ of $G$ is _properly_
coloured if $v$ is assigned a colour distinct from every neighbour of $v$. A
colouring of $G$ is _proper_ if every vertex is properly coloured. The
_chromatic number_ of $G$, denoted
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(G)$, is the minimum integer $k$
such that there is a proper $k$-colouring of $G$.

A _graph parameter_ is a real-valued function $f$ on the class of graphs such
that $f(G_{1})=f(G_{2})$ whenever graphs $G_{1}$ and $G_{2}$ are isomorphic.
Say $f$ is _bounded_ on a graph class $\mathcal{G}$ if there exists $c$ such
that $f(G)\leqslant c$ for every $G\in\mathcal{G}$, otherwise $f$ is
_unbounded_ on $\mathcal{G}$. If $f$ is bounded on $\mathcal{G}$, then let
$f(\mathcal{G}):=\sup\\{f(G):G\in\mathcal{G}\\}$. Most graph parameters
considered in this survey are integer-valued, in which case, if $f$ is bounded
on $\mathcal{G}$, then $f(\mathcal{G})=\max\\{f(G):G\in\mathcal{G}\\}$.

For a graph $G$, let $\operatorname{mad}(G)$ be the maximum average degree of
a subgraph of $G$.

A graph is _$k$ -degenerate_ if every non-empty subgraph has a vertex of
degree at most $k$. A greedy colouring algorithm shows that every
$k$-degenerate graph is $(k+1)$-colourable.

A graph $H$ is a _minor_ of a graph $G$ if a graph isomorphic to $H$ can be
obtained from a subgraph of $G$ by contracting edges. A class of graphs
$\mathcal{G}$ is _minor-closed_ if for every graph $G\in\mathcal{G}$ every
minor of $G$ is in $\mathcal{G}$, and some graph is not in $\mathcal{G}$. A
graph $G$ is _$H$ -minor-free_ if $H$ is not a minor of $G$. Let
$\mathcal{M}_{H}$ be the class of $H$-minor-free graphs.

To _subdivide_ an edge $vw$ in a graph $G$ means to delete $vw$, add a new
vertex $x$, and add new edges $vx$ and $xw$. A _subdivision_ of $G$ is any
graph obtained from $G$ by repeatedly subdividing edges. The _1-subdivision_
of $G$ is the graph obtained from $G$ by subdividing each edge of $G$ exactly
once. A graph $H$ is a _topological minor_ of a graph $G$ if a graph
isomorphic to a subdivision of $H$ is a subgraph of $G$.

The _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 Euler genus of a surface in which
$G$ embeds (with no crossings). See [177] for background on embeddings of
graphs on surfaces.

A _tree decomposition_ of a graph $G$ is given by a tree $T$ whose nodes index
a collection $(T_{x}\subseteq V(G):x\in V(T))$ of sets of vertices in $G$
called _bags_ , such that (1) for every edge $vw$ of $G$, some bag $T_{x}$
contains both $v$ and $w$, and (2) for every vertex $v$ of $G$, the set
$\\{x\in V(T):v\in T_{x}\\}$ induces a non-empty (connected) subtree of $T$.
The _width_ of a tree decomposition $T$ is $\max\\{|T_{x}|-1:x\in V(T)\\}$.
The _treewidth_ of a graph $G$, denoted by $\operatorname{tw}(G)$, is the
minimum width of the tree decompositions of $G$. See [193, 118, 32, 33, 194]
for surveys on treewidth.

A _layering_ of a graph $G$ is a partition $(V_{0},V_{1},\dots,V_{\ell})$ 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$. Each set $V_{i}$ is called a _layer_. If $r$
is a vertex in a connected graph $G$ and $V_{i}:=\\{v\in
V(G):\operatorname{dist}_{G}(v,r)=i\\}$ for $i\geqslant 0$, then
$V_{0},V_{1},\dots$ is a layering called the _BFS layering_ of $G$ starting at
$r$.

The _layered treewidth_ of a graph $G$ is the minimum integer $k$ such that
there is a tree decomposition $(T_{x}\subseteq V(G):x\in V(T))$ of $G$ and a
layering $(V_{0},V_{1},\dots,V_{\ell})$ of $G$, such that $|V_{i}\cap
T_{x}|\leqslant k$ for every $i\in[0,\ell]$ and every $x\in V(T)$. Layered
treewidth was introduced by Dujmović et al. [81].

A pair $(G_{1},G_{2})$ is a _separation_ of a graph $G$ if $G_{1}$ and $G_{2}$
are induced subgraphs of $G$ such that $G=G_{1}\cup G_{2}$, and
$V(G_{1})\setminus V(G_{2})\neq\emptyset$ and $V(G_{2})\setminus
V(G_{1})\neq\emptyset$. If, in addition, $|V(G_{1}\cap G_{2})|\leqslant k$,
then $(G_{1},G_{2})$ is a _$k$ -separation_. A separation $(G_{1},G_{2})$ of
$G$ is _minimal_ if every vertex in $V(G_{1})\cap V(G_{2})$ has a neighbour in
both $V(G_{1})\setminus V(G_{2})$ and $V(G_{2})\setminus V(G_{1})$.

A _balanced separator_ in a graph $G$ is a set $S\subseteq V(G)$ such that
every component of $G-S$ has at most $\frac{1}{2}|V(G)|$ vertices.

The _radius_ of a connected graph $G$ is the minimum integer $r$ such that for
some vertex $v$ of $G$, every vertex of $G$ is at distance at most $r$ from
$v$.

###  1.3 Choosability

Many defective and clustered colouring results hold in the setting of list
colouring. Eaton and Hull [86] first introduced defective list colouring.

A _list assignment_ for a graph $G$ is a function $L$ that assigns a set
$L(v)$ of colours to each vertex $v\in V(G)$. Define a graph $G$ to be _$L$
-colourable_ if there is a proper colouring of $G$ such that each vertex $v\in
V(G)$ is assigned a colour in $L(v)$. A list assignment $L$ is a _$k$ -list
assignment_ if $|L(v)|\geqslant k$ for each vertex $v\in V(G)$. The _choice
number_ of a graph $G$ is the minimum integer $k$ such that $G$ is
$L$-colourable for every $k$-list-assignment $L$ of $G$.

For a list-assignment $L$ of a graph $G$ and integer $d\geqslant 0$, define
$G$ to be _$L$ -colourable with defect $d$_ if there is a colouring of $G$
with defect $d$ such that each vertex $v\in V(G)$ is assigned a colour in
$L(v)$. Define $G$ to be _$k$ -choosable with defect $d$_ if $G$ is
$L$-colourable with defect $d$ for every $k$-list assignment $L$ of $G$.
Similarly, for an integer $c\geqslant 1$, $G$ is _$L$ -colourable with
clustering $c$_ if there is a colouring of $G$ with clustering $c$ such that
each vertex $v\in V(G)$ is assigned a colour in $L(v)$. Define $G$ to be _$k$
-choosable with clustering $c$_ if $G$ is $L$-colourable with clustering $c$
for every $k$-list assignment $L$ of $G$.

The _defective choice number_ of a graph class $\mathcal{G}$, denoted by
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{G})$, is
the minimum integer $k$ for which there exists an integer $d\geqslant 0$, such
that every graph $G\in\mathcal{G}$ is $k$-choosable with defect $d$. The
_clustered choice number_ of a graph class $\mathcal{G}$, denoted by
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{G})$, is
the minimum integer $k$ for which there exists an integer $c\geqslant 1$, such
that every graph $G\in\mathcal{G}$ is $k$-choosable with clustering $c$.

###  1.4 Standard Examples

The following construction, or variants of it, have been used by several
authors [119, 87, 185, 183, 124] to provide lower bounds on the defective
chromatic number. As illustrated in Figure 1, let $S(h,d)$ be defined
recursively as follows. Let $S(0,d)$ be the graph with one vertex and no
edges. For $h\geqslant 1$, let $S(h,d)$ be the graph obtained from $d+1$
disjoint copies of $S(h-1,d)$ by adding one dominant vertex. Note that
$S(1,d)=K_{1,d+1}$, the star with $d+1$ leaves.

Figure 1: The standard example $S(h,d)$.

######  Lemma 1.

For integers $h\geqslant 1$ and $d\geqslant 0$, the graph $S(h,d)$ has no
$h$-colouring with defect $d$.

###### Proof.

We proceed by induction on $h$. In the base case, $S(1,d)=K_{1,d+1}$, which
obviously has no 1-colouring with defect $d$. Now assume that $h\geqslant 2$
and the claim holds for $h-1$. Suppose on the contrary that $S(h,d)$ has an
$h$-colouring with defect $d$. Let $v$ be the dominant vertex in $S(h,d)$, and
say $v$ is blue. Then $S(h,d)-v$ has $d+1$ components $C_{1},\dots,C_{d+1}$.
Since $v$ is dominant and has monochromatic degree at most $d$, at most $d$ of
$C_{1},\dots,C_{d+1}$ contain a blue vertex. Thus some $C_{i}$ is
$(h-1)$-coloured with defect $d$. This is a contradiction since $C_{i}$ is
isomorphic to $S(h-1,d)$. Thus $S(h,d)$ has no $h$-colouring with defect $d$.
∎

Similarly, as illustrated in Figure 2, let $\overline{S}(h,c)$ be defined
recursively as follows. Let $\overline{S}(1,c)$ be the path on $c+1$ vertices.
For $h\geqslant 2$, let $\overline{S}(h,c)$ be the graph obtained from $c$
disjoint copies of $\overline{S}(h-1,c)$ by adding one dominant vertex.

Figure 2: The standard example $\overline{S}(h,c)$.

######  Lemma 2.

For integers $h,d\geqslant 1$, the graph $\overline{S}(h,c)$ has no
$h$-colouring with clustering $c$.

###### Proof.

We proceed by induction on $h$. In the base case, $\overline{S}(1,c)$ is the
path on $c+1$ vertices, which obviously has no 1-colouring with clustering
$c$. Now assume that $h\geqslant 2$ and the claim holds for $h-1$. Suppose on
the contrary that $\overline{S}(h,c)$ has an $h$-colouring with defect $c$.
Let $v$ be the dominant vertex in $\overline{S}(h,c)$, and say $v$ is blue.
Then $\overline{S}(h,c)-v$ has $c$ components $C_{1},\dots,C_{c}$. Since $v$
is dominant and the monochromatic component containing $v$ has at most $c$
vertices, at most $c-1$ of $C_{1},\dots,C_{c}$ contain a blue vertex. Thus
some $C_{i}$ is $(h-1)$-coloured with clustering $c$. This is a contradiction
since $C_{i}$ is isomorphic to $\overline{S}(h-1,c)$. Thus $\overline{S}(h,d)$
has no $h$-colouring with clustering $c$. ∎

As illustrated in Figure 3, $S(2,d)$ is planar, $\overline{S}(2,c)$ is
outerplanar, and $\overline{S}(3,c)$ is planar.

Figure 3: Planar standard examples.

###  1.5 Two Fundamental Observations

The following elementary, but fundamental, result characterises those graph
classes with bounded defective or clustered chromatic number.

######  Proposition 3.

The following are equivalent for a graph class $\mathcal{G}$:

  1. (1)

$\mathcal{G}$ has bounded defective chromatic number,

  2. (2)

$\mathcal{G}$ has bounded clustered chromatic number,

  3. (3)

$\mathcal{G}$ has bounded chromatic number.

Moreover,
$\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})$.

###### Proof.

We first show that (3) implies (1) and (2). Suppose that $\mathcal{G}$ has
bounded chromatic number. That is, for some integer $k$, every graph $G$ in
$\mathcal{G}$ is properly $k$-colourable. Thus $G$ is $k$-colourable with
defect 0 and with clustering 1. Hence
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})\leqslant
k$.

We now show that (1) implies (3). Suppose that $\mathcal{G}$ has bounded
defective chromatic number. That is, for some integers $k$ and $d$, every
graph $G$ in $\mathcal{G}$ is $k$-colourable such that each monochromatic
subgraph has maximum degree $d$. Every graph with maximum degree $d$ is
properly $(d+1)$-colourable by a greedy algorithm. Apply this result to each
monochromatic subgraph of $G$. Hence $G$ is properly $k(d+1)$-colourable, and
$\mathcal{G}$ has bounded chromatic number.

We finally show that (2) implies (1). Suppose that $\mathcal{G}$ has bounded
clustered chromatic number. That is, for some integers $k$ and $c$, every
graph $G$ in $\mathcal{G}$ is $k$-colourable such that each monochromatic
subgraph has at most $c$ vertices, and therefore has maximum degree at most
$c-1$. Hence
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})\leqslant k$,
and $\mathcal{G}$ has bounded defective chromatic number. ∎

We have the following analogous result for defective and clustered
choosability.

######  Proposition 4.

The following are equivalent for a graph class $\mathcal{G}$:

  1. (1)

$\mathcal{G}$ has bounded defective choice number,

  2. (2)

$\mathcal{G}$ has bounded clustered choice number,

  3. (3)

$\mathcal{G}$ has bounded choice number.

  4. (4)

$\mathcal{G}$ has bounded maximum average degree.

###### Proof.

A greedy algorithm shows that (4) implies (3). Alon [10] proved that (3)
implies (4). More generally, Kang [141] proved that (1) implies (4). It is
immediate that (3) implies (1) and (2). As in the proof of Proposition 3, if a
graph $G$ is $k$-choosable with clustering $c$, then $G$ is $k$-choosable with
defect $c-1$. Thus (2) implies (1). ∎

###  1.6 Related Topics

We briefly mention here some related topics not covered in this survey:

  * •

defective colourings of random graphs [142, 143, 144],

  * •

defective versions of Ohba’s list colouring conjecture [230, 215],

  * •

defective Nordhaus-Gaddum type results [3, 2],

  * •

acyclic defective colourings [49, 101, 5, 34, 100],

  * •

uniquely defectively colourable graphs [104]

  * •

weighted defective colouring [20, 123, 22].

  * •

defective colourings of triangle-free graphs [4, 205, 204],

  * •

defective colouring of directed graphs [165],

  * •

defective edge colouring [126, 125, 224],

  * •

defective circular and fractional colouring [174, 152, 99, 111],

  * •

equitable defective colouring [218],

  * •

defective co-colouring [6],

Also note that defective colouring is computationally hard. In particular, it
is NP-complete to decide if a given graph $G$ is 3-colourable with defect 1,
even when $G$ has maximum degree 6 or is planar with maximum degree 7 [18].
See [115, 155, 24, 64, 28, 178, 55, 52] for more computational aspects of
defective and clustered clustered colouring.

##  2 Greedy Approaches

###  2.1 Light Edges

Light edges provide a generic method for proving results about defective
colourings. An edge $e$ in a graph is _$\ell$ -light_ if both endpoints of $e$
have degree at most $\ell$. There is a large literature on light edges in
graphs; see [48, 135, 136, 133, 50, 35] for example. Several results on
defective colouring use, sometimes implicitly, the following lemma [158, 185,
87, 206, 119].

######  Lemma 5.

For integers $\ell\geqslant k\geqslant 1$, if every subgraph $H$ of a graph
$G$ has a vertex of degree at most $k$ or an $\ell$-light edge, then $G$ is
$(k+1)$-choosable with defect $\ell-k$.

###### Proof.

Let $L$ be a $(k+1)$-list assignment for $G$. We prove by induction on
$|V(H)|+|E(H)|$ that every subgraph $H$ of $G$ is $L$-colourable with defect
$\ell-k$. The base case with $|V(H)|+|E(H)|=0$ is trivial. Consider a subgraph
$H$ of $G$. If $H$ has a vertex $v$ of degree at most $k$, then by induction
$H-v$ is $L$-colourable with defect $\ell-k$, and there is a colour in $L(v)$
used by no neighbour of $v$ which can be assigned to $v$. Now assume that $H$
has minimum degree at least $k+1$. By assumption, $H$ contains an $\ell$-light
edge $xy$. By induction, $H-xy$ has an $L$-colouring $c$ with defect $\ell-k$.
If $c(x)\neq c(y)$, then $c$ is also an $L$-colouring of $H$ with defect
$\ell-k$. Now assume that $c(x)=c(y)$. We may further assume that $c$ is not
an $L$-colouring of $H$ with defect $\ell-k$. Without loss of generality, $x$
has exactly $\ell-k+1$ neighbours (including $y$) coloured by $c(x)$. Since
$\deg_{H}(x)\leqslant\ell$, there are at most $k-1$ neighbours not coloured by
$c(x)$. Since $L(v)$ contains $k$ colours different from $c(x)$, there is a
colour used by no neighbour of $x$ which can be assigned to $x$. ∎

###  2.2 Islands

Esperet and Ochem [98] introduced the following definition and lemma. A _$k$
-island_ in a graph $G$ is a non-empty set $S\subseteq V(G)$ such that every
vertex in $S$ has at most $k$ neighbours in $V(G)\setminus S$.

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

If every non-empty subgraph of a graph $G$ has a $k$-island of size at most
$c$, then $G$ is $(k+1)$-choosable with clustering $c$.

###### Proof.

We proceed by induction on $|V(G)|$. The base case is trivial. Let $L$ be a
$(k+1)$-list assignment for $G$. By assumption, $G$ has a $k$-island $S$. By
induction, $G-S$ is $L$-colourable with clustering $c$. Assign each vertex
$v\in S$ a colour in $L(v)$ not assigned to any neighbour of $v$ in
$V(G)\setminus S$. Each monochromatic component is contained in $S$ or is a
monochromatic component of $G-S$. Since $|S|\leqslant c$, $G$ is $L$-coloured
with clustering $c$. Thus $G$ is $k$-choosable with clustering $c$. ∎

Note that islands generalise the notion of degeneracy, since a graph is
$k$-degenerate if and only if every non-empty subgraph has a $k$-island of
size 1. Thus Lemma 6 with $c=1$ is equivalent to the well-known statement that
every $k$-degenerate graph is properly $(k+1)$-choosable.

##  3 Graphs on Surfaces

###  3.1 Outerplanar Graphs

Let $\mathcal{O}$ be the class of outerplanar graphs. Every outerplanar graph
is 2-degenerate, and thus is properly 3-colourable and 3-choosable. Since
$\overline{S}(2,c)$ is outerplanar, by Lemma 2,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{O})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{O})=3.$

Cowen et al. [66] proved the following result for defective colourings of
outerplanar graphs.

######  Theorem 7 ([66]).

Every outerplanar graph $G$ is $2$-colourable such that each monochromatic
component is a path (and thus with defect 2).

###### Proof.

We may assume $G$ is connected. Let $V_{0},V_{1},\dots$ be the BFS layering
starting from some vertex $r$. Thus $V_{0}=\\{r\\}$. If $G[V_{i}]$ has maximum
degree at least 3, for some $i\geqslant 1$, then contracting
$V_{0}\cup\dots\cup V_{i-1}$ into a single vertex gives a $K_{2,3}$-minor,
which is not outerplanar. Thus $G[V_{i}]$ has maximum degree at most 2. If
$G[V_{i}]$ contains a cycle, then contracting $V_{0}\cup\dots\cup V_{i-1}$
into a single vertex gives a $K_{4}$-minor, which is not outerplanar. Thus
each component of $G[V_{i}]$ is a path. Colour each vertex in $V_{i}$ by
$i\bmod{2}$. Then $G$ is 2-coloured such that each monochromatic component is
a path. ∎

Eaton and Hull [86] generalised Theorem 7 by showing that every outerplanar
graph is $2$-choosable with defect 2. By Lemma 1, the outerplanar graph
$K_{1,d+1}$ is not 1-colourable with defect $d$. Thus

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{O})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{O})=2.$

Moreover, the defect bound in the above results is best possible since the
graph shown in Figure 4 is not 2-colourable with defect 1.

Figure 4: An outerplanar graph that is not 2-colourable with defect 1.

See [226, 224] for more results on defective colouring of outerplanar graphs.

###  3.2 Planar Graphs

Let $\mathcal{P}$ be the class of planar graphs. We now discuss defective
colourings of $\mathcal{P}$. First note that many results about light edges in
a planar graphs are known [137, 136]. Borodin [35] proved that every planar
graph with minimum degree at least 3 contains an edge $vw$ with
$\deg(v)+\deg(w)\leqslant 13$ (which is best possible for the graph obtained
from the icosahedron by stellating each face). This edge is 10-light. By Lemma
5, every planar graph is $3$-choosable with defect $8$. Cowen et al. [66]
improved the defect bound here to 2, and Poh [189] proved an analogous result
in which each monochromatic component is a path (see [124] for an alternative
proof).

######  Theorem 8 ([189]).

Every planar graph is $3$-colourable such that each monochromatic component is
a path (and thus with defect 2).

###### Proof.

We proceed by induction on $|V(G)|$ with the hypothesis that every planar
graph $G$ is 3-colourable such that for each edge $v_{1}v_{2}$ of $G$, there
is such a 3-colouring of $G$ such that each monochromatic component is a path,
and $v_{1}$ and $v_{2}$ are properly coloured. (Recall that this means that
every neighbour of $v_{1}$ is assigned a distinct colour from $v_{1}$, and
every neighbour of $v_{2}$ is assigned a distinct colour from $v_{2}$.) In the
base case, if $|V(G)|\leqslant 4$, then assign $v_{1}$ and $v_{2}$ distinct
colours, and assign the (at most two) other vertices a third colour. Each
monochromatic component is a path. Now assume that $|V(G)|\geqslant 5$. By
adding edges, we may assume that $G$ is a planar triangulation. Say the faces
containing $v_{1}v_{2}$ are $v_{1}av_{2}$ and $v_{1}bv_{2}$. Let $G^{\prime}$
be obtained from $G$ by deleting the edge $v_{1}v_{2}$, and introducing a new
vertex $x$ adjacent to $v_{1},v_{2},a,b$. Then $G^{\prime}$ is a planar
triangulation. Let $C$ be a shortest cycle in $(G^{\prime}-v_{1})-v_{2}$ such
that $axb$ is a subpath of $C$. Since $G^{\prime}$ is 3-connected and
$|V(G)|\geqslant 5$, such a cycle exists. Since $C$ is shortest, $C$ is an
induced cycle. Let $G_{1}^{\prime}$ and $G_{2}^{\prime}$ be the subgraphs of
$G^{\prime}$ ‘inside’ and ‘outside’ of $C$ including $C$. That is,
$G^{\prime}=G_{1}^{\prime}\cup G_{2}^{\prime}$ and $V(G_{1}^{\prime})\cap
V(G_{2}^{\prime})=V(C)$ and $E(G_{1}^{\prime})\cap E(G_{2}^{\prime})=E(C)$.
Without loss of generality, $v_{i}\in V(G_{i}^{\prime})$ for $i\in\\{1,2\\}$.
Note that

$|V(G)|=|V(G^{\prime})|-1=|V(G^{\prime}_{1})|+|V(G^{\prime}_{2})|-|V(C)|-1.$

Let $G_{i}^{\prime\prime}$ be obtained from $G_{i}^{\prime}$ by contracting
$C$ into vertex $x_{i}$. Then $v_{i}x_{i}\in E(G_{i}^{\prime\prime})$ and
$|V(G^{\prime\prime}_{i})|=|V(G^{\prime}_{i})|-|V(C)|+1$. Thus

$\displaystyle|V(G)|$
$\displaystyle=(|V(G^{\prime\prime}_{1})|+|V(C)|-1)+(|V(G^{\prime\prime}_{2})|+|V(C)|-1)-|V(C)|-1$
$\displaystyle=|V(G^{\prime\prime}_{1})|+|V(G^{\prime\prime}_{2})|+|V(C)|-3.$

Since $|V(G^{\prime\prime}_{2})|\geqslant 2$ and $|V(C)|\geqslant 3$, we have
$|V(G)|\geqslant|V(G^{\prime\prime}_{1})|+2$, implying
$|V(G_{1}^{\prime\prime})|<|V(G)|$. Similarly,
$|V(G_{2}^{\prime\prime})|<|V(G)|$. By induction, each $G_{i}^{\prime\prime}$
is 3-colourable such that each monochromatic component is a path, and $v_{i}$
and $x_{i}$ are properly coloured. Permute the colours so that $x_{1}$ and
$x_{2}$ get the same colour, and $v_{1}$ and $v_{2}$ get distinct colours.
Colour each vertex in $V(C)\setminus\\{x\\}$ by the colour assigned to $x_{1}$
and $x_{2}$. Note that $V(C)\setminus\\{x\\}$ induces a path in $G$ (since $x$
is not a vertex of $G$). Moreover, $V(C)\setminus\\{x\\}$ is a monochromatic
component, since each $x_{i}$ is properly coloured in $G_{i}^{\prime\prime}$.
Every other monochromatic component of $G$ is a monochromatic component of
$G_{1}^{\prime\prime}$ or $G_{2}^{\prime\prime}$, and is therefore a path in
$G$. ∎

Eaton and Hull [86] strengthened Theorem 8 by showing that every planar graph
is $3$-choosable with defect 2. (See Theorem 33 or an alternative proof of a
more general result with a weaker defect bound.) Since $S(2,d)$ is planar, by
Lemma 1,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{P})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{P})=3.$

See [60, 158, 206, 214, 229, 36, 38, 110, 224] for more on defective
colourings of planar graphs. See [232, 216, 225] for more on defective
choosability of planar graphs.

Now consider clustered colourings of planar graphs. The 4-colour theorem [19,
196] says that every planar graph is properly $4$-colourable. Cowen et al.
[66] proved the weaker result that every planar graph is $4$-colourable with
defect 1 and thus with clustering 2 (with a computer-free elementary proof).
Cushing and Kierstead [68] strengthened this result by proving that every
planar graph is $4$-choosable with defect 1 and thus with clustering 2. Since
$\overline{S}(3,c)$ is planar, by Lemma 2,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{P})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{P})=4.$

Thomassen [211] proved that every planar graph is properly $5$-choosable.
Voigt [213] and later Mirzakhani [175] constructed planar graphs that are not
4-choosable. Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}(\mathcal{P})=5$.

###  3.3 Hex Lemma

Here we consider colourings of planar graphs with bounded degree. The
following result is a dual version of the Hex Lemma, which says that the game
of Hex cannot end in a draw. The proof is based on the proof of the Hex Lemma
by Gale [105]. See [171, Section 6.1] for another proof.

######  Theorem 9.

For every integer $k\geqslant 2$ there is planar graph $G$ with maximum degree
6 such that every 2-colouring of $G$ has a monochromatic path of length $k$.

###### Proof.

A suitable subgraph of the triangular grid forms an embedded plane graph with
maximum degree 6, such that every internal face is a triangle, the outerface
is a cycle $(a,\dots,b,\dots,c,\dots,d,\dots)$, the distance between
$\\{a,\dots,b\\}$ and $\\{c,\dots,d\\}$ is at least $k$, and the distance
between $\\{b,\dots,c\\}$ and $\\{d,\dots,a\\}$ is at least $k$. By Lemma 10
below, every 2-colouring of $G$ contains a monochromatic path between
$\\{a,\dots,b\\}$ and $\\{c,\dots,d\\}$ or between $\\{b,\dots,c\\}$ and
$\\{d,\dots,a\\}$, which has length at least $k$. ∎

Figure 5: Proof of the Hex Lemma

######  Lemma 10.

Let $G$ be an embedded plane graph with outerface
$(a,\dots,b,\dots,c,\dots,d,\dots)$, such that every internal face is a
triangle, and $a,b,c,d$ are distinct. Then for every 2-colouring of $G$ there
is a monochromatic path between $\\{a,\dots,b\\}$ and $\\{c,\dots,d\\}$ or
between $\\{b,\dots,c\\}$ and $\\{d,\dots,a\\}$.

###### Proof.

Say the colours are blue and red. As shown in Figure 5, let $G^{\prime}$ be
obtained from $G$ by adding four new vertices $w,x,y,z$, where
$N(w)=\\{a,\dots,b\\}\cup\\{z,x\\}$ and $N(x)=\\{b,\dots,c\\}\cup\\{w,y\\}$
and $N(y)=\\{c,\dots,d\\}\cup\\{x,z\\}$ and
$N(z)=\\{d,\dots,a\\}\cup\\{y,w\\}$. Colour $w$ and $y$ blue. Colour $x$ and
$z$ red. Note that $G^{\prime}$ embeds in the plane, such that every internal
face of $G^{\prime}$ is a triangle, and the outerface of $G^{\prime}$ is the
4-cycle $(w,x,y,z)$. The four internal faces of $G^{\prime}$ that share an
edge with the outerface are $(a,w,z)$, $(b,x,w)$, $(c,x,y)$ and $(d,y,z)$.
Call these faces _special_. Let $H$ be the graph with one vertex for each
internal face of $G^{\prime}$, where two vertices of $H$ are adjacent if the
corresponding faces of $H$ share an edge whose endpoints are coloured
differently. $H$ is a subgraph of the dual of $G^{\prime}$ and is therefore
planar. Let $A,B,C,D$ be the vertices of $H$ respectively corresponding to the
special faces $(a,w,z)$, $(b,x,w)$, $(c,x,y)$, $(d,y,z)$. Since $w$ and $z$
are coloured differently, $a$ has the same colour as exactly one of $w$ and
$z$, implying $A$ has degree 1 in $H$. Similarly, $B$, $C$ and $D$ each have
degree 1 in $H$. If some face of $G^{\prime}$ is monochromatic, then the
corresponding vertex of $H$ has degree 0. Every non-monochromatic non-special
face $F$ has two vertices of one colour and one vertex of the other colour,
and $F$ does not share an edge with the outerface. Thus the vertex of $H$
corresponding to $F$ has degree 2 in $H$. In summary, every vertex of $H$ has
degree 0 or 2, except for $A,B,C,D$, which have degree 1. Thus each component
of $H$ is either an isolated vertex, a cycle, or a path joining two of
$A,B,C,D$. The two paths joining $A,B,C,D$ are disjoint and do not cross.
Thus, without loss of generality, $H$ contains a path $P$ with endpoints $A$
and $B$. The red vertices on the faces corresponding to vertices in $P$ form a
walk from $\\{d,\dots,a\\}$ to $\\{b,\dots,c\\}$, which contains the desired
red path. ∎

See [25, 172, 170, 145] for multi-dimensional generalisations of the Hex
Lemma.

###  3.4 Defective Colouring of Graphs on Surfaces

For every integer $g\geqslant 0$, let $\mathcal{E}_{g}$ be the class of graphs
with Euler genus at most $g$. This section considers defective colourings of
graphs in $\mathcal{E}_{g}$. Cowen et al. [66] proved that every graph in
$\mathcal{E}_{g}$ is defectively 4-colourable. Archdeacon [21] proved the
conjecture of Cowen et al. [66] that every graph in $\mathcal{E}_{g}$ is
defectively 3-colourable. Since $S(2,d)$ is planar,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{E}_{g})=3$ by
Lemma 1. The following proof of Cowen et al. [65]444Cowen et al. [65] actually
claim an upper bound on the defect of $\max\\{12,\sqrt{6g}+6\\}$. We could not
replicate this calculation. provides a defect bound that is within a constant
factor of optimal (since $K_{n}$ has Euler genus $\Theta(n^{2})$).

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

Every graph $G$ with Euler genus $g$ is 3-colourable with defect
$d:=\max\\{12,\lceil{\sqrt{6g}}\rceil+7\\}$.

###### Proof.

We proceed by induction on $|V(G)|+|E(G)|$. If some vertex $v$ has degree at
most 2, then by induction, $G-v$ is 3-colourable with defect $d$. Assign $v$ a
colour different from the colours assigned to the neighbours of $v$. Then $G$
is 3-coloured with defect $d$. Now assume that $G$ has minimum degree at least
3. Let $A$ be the set of vertices with degree at most $d$. If $v,w\in A$ for
some edge $vw$, then by induction, $G-vw$ is 3-colourable with defect $d$,
which is a 3-colouring of $G$ with defect $d$. Now assume that $A$ is a stable
set. Let $B$ be the set of vertices with degree at least $d+1$. Since
$d\geqslant 12$ and by Lemma 12 below,
$|B|\leqslant\frac{\max\\{12(g-2),0\\}}{d-11}$. Colour the vertices in $A$
blue. Colour $\lceil{\frac{|B|}{2}}\rceil$ of the vertices in $B$ red. Colour
the other vertices in $B$ green.

If $g\leqslant 2$ then $B=\emptyset$ and the defect is $0\leqslant d$, as
desired. Otherwise $|B|\leqslant\frac{12(g-2)}{d-11}$, and the defect is at
most $\lceil{\frac{|B|}{2}}\rceil-1$. If $g\in\\{3,4\\}$ then $d=12$ and
$|B|\leqslant 24$ and the defect is at most $11$, as desired. Otherwise,
$g\geqslant 5$, and the defect is at most
$\frac{|B|-1}{2}\leqslant\frac{6(g-2)}{d-11}-\frac{1}{2}$. We now show this
bound is at most $d$. Since $g\geqslant 5$, we have $12g+36\leqslant
12g+7\sqrt{6g}$, implying

$12(g-2)\leqslant 12g+(15-8)\sqrt{6g}-60=(2\sqrt{6g}+15)(\sqrt{6g}-4).$

Since $d\geqslant\sqrt{6g}+7$, we have $12(g-2)\leqslant(2d+1)(d-11)$. That
is, $6(g-2)\leqslant(d+\frac{1}{2})(d-11)$. Since $d\geqslant 12$, we have
$\frac{6(g-2)}{d-11}-\frac{1}{2}\leqslant d$, as claimed. ∎

######  Lemma 12 ([65]).

Let $G$ be a graph with Euler genus $g$ and minimum degree at least 3. Fix an
integer $d$. Let $A$ be the set of vertices with degree at most $d$. Assume
that $A$ is a stable set. Let $B$ be the set of vertices with degree at least
$d+1$. Then $(d-11)|B|\leqslant\max\\{12(g-2),0\\}$.

###### Proof.

If $B=\emptyset$ then the result is vacuous. Now assume that $B\neq\emptyset$.
For each non-triangular face $f$, add an edge between two non-consecutive
vertices in $B$ (which must exist since $A$ is a stable set). We obtain a
multigraph triangulation $G^{\prime}$, in which $A$ is a stable set. Let
$n_{i}$ be the number of vertices with degree $i$ in $G^{\prime}$. Let
$\alpha$ be the number of edges in $G^{\prime}$ incident with vertices in $A$.
Let $\beta$ be the number of edges in $G^{\prime}$ with both endpoints in $B$.
By Euler’s formula,

$\displaystyle 6(g-2)=\sum_{i\geqslant 3}(i-6)n_{i}$
$\displaystyle=\sum_{3\leqslant i\leqslant d}(i-6)n_{i}+\sum_{i\geqslant
d+1}(i-6)n_{i}$ $\displaystyle=\sum_{3\leqslant i\leqslant
d}(i-6)n_{i}+\sum_{i\geqslant
d+1}(\tfrac{i}{2}-6)n_{i}+\frac{1}{2}\sum_{i\geqslant d+1}in_{i}$
$\displaystyle=\sum_{3\leqslant i\leqslant d}(i-6)n_{i}+\sum_{i\geqslant
d+1}(\tfrac{i}{2}-6)n_{i}+\frac{1}{2}(\alpha+2\beta).$

Since $G^{\prime}$ is a triangulation, each face of $G^{\prime}$ has at most
two edges incident with $A$, and at least one edge with endpoints in $B$. It
follows that $\alpha\leqslant 2\beta$ and

$\displaystyle 6(g-2)$ $\displaystyle\geqslant\sum_{3\leqslant i\leqslant
d}(i-6)n_{i}+\sum_{i\geqslant d+1}(\tfrac{i}{2}-6)n_{i}+\alpha$
$\displaystyle=\sum_{3\leqslant i\leqslant d}(2i-6)n_{i}+\sum_{i\geqslant
d+1}(\tfrac{i}{2}-6)n_{i}$ $\displaystyle\geqslant
0+\left(\tfrac{d+1}{2}-6\right)|B|.$

The result follows. ∎

Woodall [228] improved Theorem 11 to show that every graph with Euler genus
$g$ is 3-choosable with defect $\max\\{9,2+\sqrt{4g+6}\\}$. Thus

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{E}_{g})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{E}_{g})=3.$

See Theorems 43 and 76 for generalisations of this result, and see [190, 224,
117, 59, 58, 235] for further results on defective colourings of graphs
embeddable on surfaces. One direction of interest is the following definition,
which allows for results that bridge the gap between proper and defective
colourings [69, 56, 178, 59, 40, 39, 58]: a graph $G$ is
_$(d_{1},\dots,d_{k})$ -colourable_ if there is a partition
$V_{1},\dots,V_{k}$ of $V(G)$ such that each induced subgraph $G[V_{i}]$ has
maximum degree at most $d_{i}$. For example, Choi and Esperet [59] proved the
following analogue of the 4-colour theorem: every graph with Euler genus $g>0$
is $(0,0,0,9g-4)$-colourable.

Note that the light edge approach also proves 3-choosability, but with a
weaker defect bound. In particular, results of Ivančo [130] and Jendro’l and
Tuhársky [134] together imply that every graph in $\mathcal{E}_{g}$ with
minimum degree at least 3 has an edge $vw$ with
$\deg(v)+\deg(w)\leqslant\max\\{2g+7,19\\}$. (Better results are known for
specific surfaces with $g\leqslant 5$, and all the bounds are tight.) Thus
every graph in $\mathcal{E}_{g}$ with minimum degree at least 3 has a
$\max\\{2g+4,16\\}$-light edge. (See Lemma 78 for a more general result with a
slightly weaker bound.) Lemma 5 then implies that every graph with Euler genus
$g$ is $3$-choosable with defect $\max\\{2g+2,14\\}$. See [57, 173, 235, 234,
233, 236] for more on defective choosability of graphs embedded on surfaces.

###  3.5 Clustered Colouring of Graphs on Surfaces

This section considers clustered colouring of graphs embeddable on surfaces.
Esperet and Ochem [98] proved that every graph of bounded Euler genus has a
4-island of bounded size, and is thus 5-colourable with bounded clustering by
Lemma 6. Kawarabayashi and Thomassen [148] also proved that every graph of
bounded Euler genus is 5-colourable with bounded clustering. Dvořák and Norin
[84] improved 5 to 4 via the following remarkably simple argument.

######  Lemma 13 ([84]).

Let $G$ be a graph, such that for some constants $\alpha,c>0$ and
$\beta\in(0,1)$,

$|E(G)|<(k+1-\alpha)|V(G)|,$

and every subgraph of $G$ with $n$ vertices has a balanced separator of size
at most $cn^{1-\beta}$. Then $G$ has a $k$-island of size at most

$\left\lceil{2\left(\frac{c(k+1)}{\alpha(2^{\beta}-1)}\right)^{1/\beta}}\right\rceil.$

###### Proof.

Let $\epsilon:=\frac{\alpha}{k+1}$. By Lemma 15 below, there exists
$X\subseteq V(G)$ of size at most $\epsilon|V(G)|$ such that if
$K_{1},\dots,K_{p}$ are the components of $G-X$, then each $K_{i}$ has at most
$\lceil{2(\frac{c}{\epsilon(2^{\beta}-1)})^{1/\beta}}\rceil$ vertices. Let
$e(K_{i})$ be the number of edges of $G$ with at least one endpoint in
$K_{i}$. Then

$\displaystyle\sum_{i}e(K_{i})\leqslant|E(G)|<(k+1-\alpha)|V(G)|=(1-\epsilon)(k+1)\,|V(G)|$
$\displaystyle\leqslant(k+1)\,|V(G)\setminus X|$
$\displaystyle=(k+1)\sum_{i}|V(K_{i})|.$

Hence $e(K_{i})<(k+1)\,|V(K_{i})|$ for some $i$. Repeatedly remove vertices
from $K_{i}$ with at least $k+1$ neighbours outside of $K_{i}$. Doing so
maintains the property that $e(K_{i})<(k+1)\,|V(K_{i})|$. Thus the final set
is non-empty. We obtain a $k$-island of size at most
$|V(K_{i})|\leqslant\lceil{2(\frac{c(k+1)}{\alpha(2^{\beta}-1)})^{1/\beta}}\rceil$.
∎

The above proof depends on the following result by Edwards and McDiarmid [91].
Lipton and Tarjan [160, 161] implicitly proved an analogous result for planar
graphs.

######  Lemma 14 ([91]).

Fix $c>0$ and $\beta\in(0,1)$. Let $G$ be a graph with $n$ vertices such that
every subgraph $G^{\prime}$ of $G$ has a balanced separator of size at most
$c|V(G^{\prime})|^{1-\beta}$. Then for all $p\geqslant 1$ there exists
$S\subseteq V(G)$ of size at most $\frac{c2^{\beta}n}{(2^{\beta}-1)p^{\beta}}$
such that each component of $G-S$ has at most $p$ vertices.

###### Proof.

Run the following algorithm. Initialise $S:=\emptyset$. While $G-S$ has a
component $X$ with more than $p$ vertices, let $S_{X}$ be a balanced separator
of $X$ with size at most $c|V(X)|^{1-\beta}$, and add $S_{X}$ to $S$.

Say a component of $G-S$ at the end of the algorithm has _level_ 0\. Say $X$
is a component of $G-S$ at some stage of the algorithm, but $X$ is not a
component of $G-S$ at the end of the algorithm. Then $X$ is separated by some
set $S_{X}$, which is then added to $S$. Define the _level_ of $X$ to 1 plus
the maximum level of a component of $X-S_{X}$.

By assumption, level 0 components have at most $p$ vertices. Each level 1
component has more than $p$ vertices. By induction on $i$, each level
$i\geqslant 1$ component has more than $2^{i-1}p$ vertices. Let $t_{i}$ be the
number of components at level $i\geqslant 1$. Say $X_{1},\dots,X_{t_{i}}$ are
the components at level $i$. Since level $i$ components are pairwise disjoint,

$t_{i}2^{i-1}p<\sum_{j=1}^{t_{i}}|V(X_{j})|\leqslant n,$

implying $t_{i}<\frac{n}{2^{i-1}p}$. The number of vertices added to $S$ by
separating $X_{1},\dots,X_{t_{i}}$ is at most

$c\sum_{j=1}^{t_{i}}|V(X_{j})|^{1-\beta},$

which is maximised, subject to $\sum_{j}|V(X_{j})|\leqslant n$, when
$|V(X_{j})|=\frac{n}{t_{i}}$. Thus

$c\sum_{j=1}^{t_{i}}|V(X_{j})|^{1-\beta}\leqslant
ct_{i}\left(\frac{n}{t_{i}}\right)^{1-\beta}=ct_{i}^{\beta}n^{1-\beta}<c\left(\frac{n}{2^{i-1}p}\right)^{\beta}n^{1-\beta}=cn\left(\frac{2^{1-i}}{p}\right)^{\beta}.$

Hence

$|S|\leqslant c\sum_{i\geqslant
1}n\left(\frac{2^{1-i}}{p}\right)^{\beta}=\frac{cn}{p^{\beta}}\sum_{i\geqslant
1}(2^{1-i})^{\beta}=\frac{c\,2^{\beta}n}{(2^{\beta}-1)p^{\beta}}.\qed$

Lemma 14 implies the following result. In the language of Edwards and
McDiarmid [91], this lemma provides a sufficient condition for a graph to be
‘fragmentable’; this idea is extended by Edwards and Farr [88, 90].

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

Fix $c>0$ and $\beta\in(0,1)$. Let $G$ be a graph with $n$ vertices such that
every subgraph $G^{\prime}$ of $G$ has a balanced separator of size at most
$c|V(G^{\prime})|^{1-\beta}$. Then for $\epsilon>0$ there exists $S\subseteq
V(G)$ of size at most $\epsilon|V(G)|$ such that each component of $G-S$ has
at most $\lceil{2(\frac{c}{\epsilon(2^{\beta}-1)})^{1/\beta}}\rceil$ vertices.

We now reach the main result of this section.

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

Every graph $G$ with Euler genus $g$ is 4-choosable with clustering
$1500(g+2)$.

###### Proof.

We proceed by induction on $|V(G)|$. Let $L$ be a $4$-list assignment for $G$.
The claim is trivial if $|V(G)|=0$. Now assume that $|V(G)|\geqslant 1$. First
suppose that $|V(G)|\leqslant 6000g$. Let $v$ be any vertex of $G$. By
induction, $G-v$ is $L$-colourable with clustering $1500(g+2)$. Since
$|L(v)|=4$ and $|V(G-v)|<6000g$, some colour $c\in L(v)$ is assigned to at
most $1500g$ vertices in $G-v$. Colour $v$ by $c$. Thus $G$ is $L$-coloured
with clustering $1500(g+2)$. Now assume that $|V(G)|>6000g$. Define
$\alpha:=\frac{1999}{2000}$ and $k:=3$. It follows from Euler’s formula that
$|E(G)|<3(|V(G)|+g)\leqslant(k+1-\alpha)|V(G)|$. Various authors [93, 109, 9,
78] proved that every $n$-vertex graph with Euler genus at most $g$ has a
balanced separator of size $O(\sqrt{gn})$. Dujmović et al. [81] proved a
concrete upper bound of $2\sqrt{(2g+3)n}$. Thus Lemma 13 with
$\beta=\frac{1}{2}$ implies that $G$ has a $3$-island of size at most

$\left\lceil{2\left(\frac{4\cdot
2\sqrt{2g+3}}{\frac{1999}{2000}(\sqrt{2}-1)}\right)^{2}}\right\rceil\leqslant\left\lceil{747(2g+3)}\right\rceil<747(2g+3)+1<1500(g+2).$

By induction, $G-S$ is $L$-colourable with clustering $1500(g+2)$. By the
argument in Lemma 6, $G$ is $L$-colourable with clustering $1500(g+2)$. ∎

Since $\overline{S}(3,d)$ is planar, Lemmas 2 and 16 imply

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{E}_{g})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{E}_{g})=4.$

It is still open to determine the best possible clustering function.

######  Open Problem 17.

Does every graph in $\mathcal{E}_{g}$ have a 4-colouring with clustering
$O(\sqrt{g})$?

The following question also remains open; see Section 8.1 for relevant
material.

######  Open Problem 18.

Are graphs with bounded Euler genus and bounded maximum degree 3-choosable
with bounded clustering?

The above method extends for embedded graphs with large girth (since
$|E(G)|<2(|V(G)|+g)$ if the girth is at least 4, and
$|E(G)|<\frac{5}{3}(|V(G)|+g)$ if the girth is at least 5).

######  Theorem 19 ([84]).

Let $G$ be a graph with Euler genus $g$ and girth $k$. If $k\geqslant 4$, then
$G$ is 3-choosable with clustering $O(g)$. If $k\geqslant 5$, then $G$ is
2-choosable with clustering $O(g)$.

See Section 8.2 for more applications of the island method. Also note that
Linial et al. [159] use sublinear separators in a slightly different way
(compared with Lemma 13) to obtain bounds on the size of monochromatic
components in 2-colourings of graphs.

##  4 Maximum Degree

The defective chromatic number of any graph class with bounded maximum degree
equals 1. Thus defective colourings in the setting of bounded degree graphs
are only interesting if one also considers the bound on the defect. Lovász
[164] proved the following result for defective colourings of bounded degree
graphs; see [29, 43, 156, 107] for related results and extensions.

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

For $d\geqslant 0$, every graph with maximum degree $\Delta$ is $k$-colourable
with defect $d$, where $k:=\lfloor{\frac{\Delta}{d+1}}\rfloor+1$.

###### Proof.

Consider a $k$-colouring of $G$ that maximises the number of bichromatic
edges. Suppose that some vertex $v$ is adjacent to at least $d+1$ vertices of
the same colour. Some other colour is assigned to at most
$\lfloor{(\deg(v)-d-1)/(k-1)}\rfloor\leqslant d$ neighbours of $v$. Recolour
$v$ this colour. The number of bichromatic edges increases by at least 1. This
contradiction shows that every vertex $v$ is adjacent to at most $d$ vertices
of the same colour. ∎

We now show that Theorem 20 is best possible. Say $G=K_{n}$ is $k$-colourable
with defect $d$. Some monochromatic subgraph has at least
$\lceil{\frac{n}{k}}\rceil$ vertices. Thus
$d\geqslant\lceil{\frac{n}{k}}\rceil-1$ and
$k\geqslant\frac{n}{d+1}=\frac{\Delta(G)+1}{d+1}$. Moreover, if $k$ does not
divide $n$, then $k>\frac{\Delta(G)+1}{d+1}$, implying
$k\geqslant\lfloor{\frac{\Delta(G)+1}{d+1}}\rfloor+1$, which exactly matches
the bound in Theorem 20.

Clustered colourings of bounded degree graphs are more challenging than their
defective cousins. Let $\mathcal{D}_{\Delta}$ be the class of graphs with
maximum degree $\Delta$. First note the following straightforward lemma.

######  Lemma 21.

For $\Delta>d\geqslant 1$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left(\left\lfloor\frac{\Delta}{d+1}\right\rfloor+1\right)\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{d}).$

###### Proof.

Let $k_{1}:=\lfloor{\frac{\Delta}{d+1}}\rfloor+1$ and
$k_{2}:=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{d})$.
Let $G$ be a graph with maximum degree $\Delta$. By Theorem 20, $G$ is
$k_{1}$-colourable with defect $d$. Each monochromatic subgraph, which has
maximum degree $d$, is $k_{2}$-colourable with clustering $c$ (depending only
on $d$). The product gives a $k_{1}k_{2}$-colouring of $G$ with clustering
$c$. Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant
k_{1}k_{2}$. ∎

We now show a series of improving upper bounds on
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})$.
Theorem 20 with $d=1$ implies every graph with maximum degree $\Delta$ is
$(\lfloor{\Delta/2}\rfloor+1)$-colourable with defect 1, and thus with
clustering 2. Hence

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left\lfloor\frac{\Delta}{2}\right\rfloor+1.$

In particular, this shows that every graph with maximum degree $3$ is
$2$-colourable with clustering 2. Alon et al. [11] proved that every graph
with maximum degree 4 is 2-colourable with clustering 57. Haxell et al. [120]
improved this bound on the cluster size from 57 to 6. Lemma 21 with $d=4$ then
implies that

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant
2\left(\left\lfloor\frac{\Delta}{5}\right\rfloor+1\right).$

Alon et al. [11] pushed their method further to prove that

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left\lceil{\frac{\Delta+2}{3}}\right\rceil.$

In fact, Alon et al. [11] showed that for $\epsilon\in(0,3)$ every graph of
maximum degree $\Delta$ is $\lceil{(\Delta+2)/(3-\epsilon)}\rceil$-colourable
with clustering $c(\epsilon)$ (independent of $\Delta$).

For the sake of brevity, we present slightly weaker results with simpler
proofs. The following result was implicitly proved by Alon et al. [11].

######  Theorem 22.

Let $G$ be a graph with maximum degree $\Delta$. If $G$ has a $k$-colouring
with defect 2, then $G$ has a $(k+1)$-colouring with clustering $24\Delta$.

###### Proof.

Say an induced cycle or path in $G$ is _short_ if it has at most $8\Delta$
vertices, otherwise it is _long_. Let $X_{1},\dots,X_{k}$ be a partition of
$V(G)$ corresponding to the given $k$-colouring with defect $2$. Thus each
$G[X_{i}]$ is a collection of pairwise disjoint induced cycles and paths.
Consider such a cycle or path $Y$ that is long. Then $|Y|=a(8\Delta)+b$ for
some $a\geqslant 1$ and $b\in[1,8\Delta]$. Partition $Y$ into a set of paths
$Y_{1},\dots,Y_{a},Y_{a+1}$, where $|V(Y_{j})|=8\Delta$ for $j\in[1,a]$, and
$|V(Y_{a+1})|=b$. Here the last vertex in $Y_{j}$ is adjacent to the first
vertex in $Y_{j+1}$ for $j\in[1,a]$, and if $Y$ is a cycle then the last
vertex in $Y_{a+1}$ is adjacent to the first vertex in $Y_{1}$. Let
$Z_{1},\dots,Z_{n}$ be the collection of all these induced paths with exactly
$8\Delta$ vertices (which might include some $Y_{a+1}$).

Let $G^{\prime}$ be the subgraph of $G$ induced by $V(Z_{1}\cup\dots\cup
Z_{n})$. Thus $G^{\prime}$ has maximum degree at most $\Delta$. By Lemma 23
below, $G$ has a stable set $S=\\{v_{1},\dots,v_{n}\\}$ with $v_{i}\in Z_{i}$
for each $i\in[n]$. We claim that $\\{S,X_{1}\setminus S,\dots,X_{k}\setminus
S\\}$ defines a $(k+1)$-colouring with clustering $24\Delta$. By construction,
$S$ is a stable set in $G$. Say $Q$ is a component of $G[X_{i}\setminus S]$.
Then $Q$ is contained in some component $Y$ of $G[X_{i}$]. If $Y$ is short,
then $|Q|\leqslant 8\Delta$ as desired. Now assume that $Y$ is long. Let
$(Y_{1},\dots,Y_{a},Y_{a+1})$ be the above partition of $Y$. Since each of
$Y_{1},\dots,Y_{a}$ has a vertex in $S$, $Q$ is contained in $Y_{j}\cup
Y_{j+1}\cup Y_{j+2}$ for some $j\in[1,a+1]$, where $Y_{a+2}$ means $Y_{1}$ and
$Y_{a+3}$ means $Y_{2}$. Thus $|Q|\leqslant 24\Delta$. ∎

The proof of Theorem 22 used the following well-known lemma about ‘independent
transversals’.

######  Lemma 23.

Let $G$ be a graph with maximum degree at most $\Delta$. Let
$V_{1},\dots,V_{n}$ be a partition of $V(G)$, with $|V_{i}|\geqslant 8\Delta$
for each $i\in[n]$. Then $G$ has a stable set $\\{v_{1},\dots,v_{n}\\}$ with
$v_{i}\in V_{i}$ for each $i\in[n]$.

###### Proof.

The proof uses the Lovász Local Lemma [96], which says that if $\mathcal{X}$
is a set of events in a probability space, such that each event in
$\mathcal{X}$ has probability at most $p$ and is mutually independent of all
but $D$ other events in $\mathcal{X}$, and $4pD\leqslant 1$, then with
positive probability no event in $\mathcal{X}$ occurs.

We may assume that $|V_{i}|=8\Delta$ for $i\in[n]$. For each $i\in[n]$,
independently and randomly choose one vertex $v_{i}\in V_{i}$. Each vertex in
$V_{i}$ is chosen with probability at most $\frac{1}{8\Delta}$. Consider an
edge $vw$, where $v\in V_{i}$ and $w\in V_{j}$. Let $X_{vw}$ be the event that
both $v$ and $w$ are chosen. Thus $X_{vw}$ has probability at most
$p:=\frac{1}{64\Delta^{2}}$. Observe that $X_{vw}$ is mutually independent of
every event $X_{xy}$ where $x\not\in V_{i}\cup V_{j}$ and $y\not\in V_{i}\cup
V_{j}$. Thus $X_{vw}$ is mutually independent of all but at most
$D:=\Delta(|V_{i}|+|V_{j}|)=16\Delta^{2}$ other events. Thus
$4pD=4(\frac{1}{64\Delta^{2}})(16\Delta^{2})\leqslant 1$. By the Lovász Local
Lemma, with positive probability, no event $X_{vw}$ occurs. Hence there exist
$v_{1},\dots,v_{n}$ such that no event $X_{vw}$ occurs. That is,
$\\{v_{1},\dots,v_{n}\\}$ is the desired stable set. ∎

The $8\Delta$ term in Lemma 23 was improved to $2\Delta$ by Haxell [121],
which means the $24\Delta$ term in Theorem 22 can be improved to $6\Delta$.

Theorem 20 with $d=2$ and Theorem 22 imply

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left\lfloor\frac{\Delta}{3}\right\rfloor+2.$
(1)

Answering a question of Alon et al. [11], Haxell et al. [120] proved that
every graph with maximum degree 5 is 2-colourable with clustering less than
20000. For two colours, maximum degree 5 is best possible, by the Hex Lemma
(Theorem 9). Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})=2$ if
and only if $\Delta\in\\{2,\dots,5\\}$. Lemma 21 with $d=5$ then implies

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant
2\left(\left\lfloor\frac{\Delta}{6}\right\rfloor+1\right).$

Haxell et al. [120] proved that every graph with maximum degree 8 is
3-colourable with bounded clustering. Using their result for the $\Delta=5$
case and the $\Delta=8$ case, Haxell et al. [120] proved that

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left\lceil{\frac{\Delta+1}{3}}\right\rceil.$

Moreover, Haxell et al. [120] proved for large $\Delta$ one can do slightly
better: for some constants $\epsilon>0$ and for all
$\Delta\geqslant\Delta_{0}$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left(\frac{1}{3}-\epsilon\right)\Delta.$

Note that for both these results by Haxell et al. [120] the clustering bound
is independent of $\Delta$.

It is open whether every graph with maximum degree 9 is 3-colourable with
bounded clustering [120]. If this is true, then Lemma 21 with $d=9$ would
imply

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant
3\left(\left\lfloor\frac{\Delta}{10}\right\rfloor+1\right),$

which would be the best known upper bound on
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})$.
Graphs with maximum degree 10 are not 3-colourable with bounded clustering
[11], as shown by the following general lower bound, which also implies a
3-colour lower bound for graphs of maximum degree 6.

######  Theorem 24 ([11, 120]).

For every integer $\Delta\geqslant 2$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\geqslant\left\lfloor\frac{\Delta+6}{4}\right\rfloor.$

###### Proof.

If $\Delta$ is odd, then
$\lfloor{\frac{\Delta+6}{4}}\rfloor=\lfloor{\frac{(\Delta-1)+6}{4}}\rfloor$,
and the result for $\Delta-1$ implies the result for $\Delta$. Thus we may
assume that $\Delta$ is even. Let $k:=\lfloor{\frac{\Delta+6}{4}}\rfloor$. Our
goal is to show that for every integer $c\geqslant 3$ there is a graph $G$
that has no $(k-1)$-colouring with clustering $c$. Erdős and Sachs [94] proved
that there is a $(\frac{\Delta}{2}+1)$-regular graph $G_{0}$ with girth
greater than $c$. Say $|V(G_{0})|=n$. Let $G$ be the line graph of $G_{0}$.
Then $G$ is $\Delta$-regular with $(\frac{\Delta+2}{4})n$ vertices. Suppose on
the contrary that $G$ is $(k-1)$-colourable with clustering $c$. For some
colour class $X$ of $G$,

$|X|\geqslant\frac{|V(G)|}{k-1}=\frac{(\Delta+2)n}{4k-4}\geqslant n.$

Thus $X$ corresponds to a set $X^{\prime}$ of at least $n$ edges in $G_{0}$,
which therefore contains a cycle of size greater than $c$. Thus, $X$ contains
a monochromatic component of size greater than $c$, which is a contradiction.
∎

The following problem remains open for $\Delta\geqslant 9$.

######  Open Problem 25.

What is
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})$? The
best known bounds are

$\left\lfloor\frac{\Delta+6}{4}\right\rfloor\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left\lceil{\frac{\Delta+1}{3}}\right\rceil,$

and for some $\epsilon>0$ and all $\Delta$ at least some constant
$\Delta_{0}$.

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})\leqslant\left(\frac{1}{3}-\epsilon\right)\Delta.$

######  Open Problem 26.

What is
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{D}_{\Delta})$?
The best known bounds are

$\left\lfloor\frac{\Delta+6}{4}\right\rfloor\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{D}_{\Delta})\leqslant\Delta,$

where the upper bound follows from known Brooks-type bounds on the choice
number [67].

It is interesting that for many of the above results the bound on the
clustering is independent of $\Delta$. We now show that from any upper bound
on $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})$
with clustering linear in $\Delta$, one can obtain a slightly larger upper
bound that is independent of $\Delta$. The idea of the proof is by Alon et al.
[11].

######  Theorem 27.

Suppose that every graph with maximum degree $\Delta$ is
$(\frac{\Delta}{x}+y)$-colourable with clustering $\alpha\Delta$, for some
constants $\alpha,x,y>0$. Then for every $\epsilon>0$ there is a number
$c=c(\epsilon,\alpha,x,y)$ such that every graph with maximum degree $\Delta$
is $((1+\epsilon)\frac{\Delta}{x}+y)$-colourable with clustering $c$.

###### Proof.

Let $d:=\lceil{\frac{2}{\epsilon}(xy-1)}\rceil-1$ and $c:=\max\\{\alpha
d,\frac{2\alpha d}{\epsilon}\\}$. If $\alpha\Delta\leqslant c$ then the result
holds by assumption. Now assume that $\alpha\Delta>c\geqslant\frac{2\alpha
d}{\epsilon}$ implying $d\leqslant\frac{\epsilon\Delta}{2}$. By Theorem 20,
$G$ is $k$-colourable with defect $d$, where
$k:=\lfloor{\frac{\Delta}{d+1}}\rfloor+1$. By assumption, each of these $k$
monochromatic subgraphs is $(\frac{d}{x}+y)$-colourable with clustering
$\alpha d$. Thus $G$ is $k^{\prime}$-colourable with clustering $\alpha
d\leqslant c$, where

$\displaystyle
k^{\prime}:=\left(\frac{\Delta}{d+1}+1\right)\left(\frac{d}{x}+y\right)=\frac{\Delta}{x}+\frac{\Delta(xy-1)}{x(d+1)}+\frac{d}{x}+y.$

Since $xy-1\leqslant\frac{\epsilon}{2}(d+1)$ and
$d\leqslant\frac{\epsilon\Delta}{2}$,

$k^{\prime}\leqslant\frac{\Delta}{x}+\frac{\epsilon\Delta}{2x}+\frac{\epsilon\Delta}{2x}+y=\frac{(1+\epsilon)\Delta}{x}+y.\qed$

See [27, 159, 89, 26] for more results about clustered colourings of graphs
with given maximum degree.

##  5 Maximum Average Degree

Recall that $\operatorname{mad}(G)$ is the maximum average degree of a
subgraph of $G$. For $m\in\mathbb{R}^{+}$, let $\mathcal{A}_{m}$ be the class
of graphs $G$ with $\operatorname{mad}(G)\leqslant m$. A greedy algorithm
shows that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{A}_{m})\leqslant\lfloor{m}\rfloor+1$.
Havet and Sereni [119] determined
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{A}_{m})$ as
follows.

######  Theorem 28 ([119]).

For $m\in\mathbb{R}^{+}$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{A}_{m})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{A}_{m})=\left\lfloor\frac{m}{2}\right\rfloor+1.$

We prove Theorem 28 below. The key is the following lemma, which is a slightly
weaker version of a result by Havet and Sereni [119], who proved that every
graph $G$ with $\operatorname{mad}(G)<k+\frac{kd}{k+d}$ is $k$-choosable with
defect $d$.

######  Lemma 29 (Frédéric Havet).

For all $m\in\mathbb{R}^{+}$ and $k,d\in\mathbb{Z}^{+}$ such that
$\frac{1}{k}+\frac{1}{d}\leqslant\frac{2}{m}$, every graph $G$ with
$\operatorname{mad}(G)\leqslant m$ is $k$-choosable with defect $d$.

###### Proof.

Let $G$ be a counterexample with $|V(G)|+|E(G)|$ minimum (with $r,k,d$ fixed).
By Lemma 5, $G$ has minimum degree $k$ and has no $d$-light edge. Let

$\displaystyle A:=$ $\displaystyle\\{v\in V(G):\deg(v)\leqslant m\\},$
$\displaystyle B:=$ $\displaystyle\\{v\in V(G):m<\deg(v)\leqslant d\\}\text{
and}$ $\displaystyle C:=$ $\displaystyle\\{v\in V(G):d<\deg(v)\\}.$

Since $\frac{1}{k}+\frac{1}{d}\leqslant\frac{2}{m}$ we have
$\frac{m}{k}-1\leqslant 1-\frac{m}{d}$. Let $\gamma$ be a real number with
$\frac{m}{k}-1\leqslant\gamma\leqslant 1-\frac{m}{d}$. Associate with each
vertex $v$ an initial charge of $\deg(v)$. The total charge is
$\sum_{v}\deg(v)=2|E(G)|$. Redistribute the charge as follows: for each edge
$vw$ with $v\in A$, let $w$ send $\gamma$ charge to $v$. Note that $w\in C$
since $G$ has no $d$-light edge. Now, each vertex $v\in A$ has charge
$(1+\gamma)\deg(v)\geqslant(1+\gamma)k\geqslant m$. The charge for each vertex
$v\in B$ is unchanged. Each vertex $v\in C$ has charge at least
$(1-\gamma)\deg(v)>(1-\gamma)d\geqslant m$. We may assume that
$C\neq\emptyset$, as otherwise $G$ is 1-colourable with defect $d$. Thus the
total charge is greater than $m|V(G)|$, implying the average degree is greater
than $m$, which is a contradiction. ∎

###### Proof of Theorem 28.

Let $k:=\lfloor{\frac{m}{2}}\rfloor+1$. Thus $k>\frac{m}{2}$. Let
$d:=\lceil{\frac{m^{2}}{4k-2m}+\frac{m}{2}}\rceil$, which is well-defined
since $4k>2m$. Then

$4d-2m\geqslant\frac{m^{2}}{k-\frac{m}{2}},$

implying

$k\geqslant\frac{m}{2}+\frac{m^{2}}{4d-2m}=\frac{m(2d-m)+m^{2}}{4d-2m}=\frac{md}{2d-m}=\frac{1}{\frac{2}{m}-\frac{1}{d}}.$

Since $2d>m$,

$\frac{1}{k}\leqslant\frac{2}{m}-\frac{1}{d}$

and $\frac{1}{k}+\frac{1}{d}\leqslant\frac{2}{m}$. By Lemma 29, every graph
$G$ with $\operatorname{mad}(G)\leqslant m$ is
$(\lfloor{\frac{m}{2}}\rfloor+1)$-choosable with defect $d$. Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{A}_{m})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{A}_{m})\leqslant\left\lfloor\frac{m}{2}\right\rfloor+1$.

For the lower bound, let $h:=\lfloor{\frac{m}{2}}\rfloor$. Then the standard
example $S(h,d)$ has maximum average degree less than $2h\leqslant m$ and is
not $h$-colourable with defect $d$ by Lemma 1. Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{A}_{m})\geqslant
h+1$, as required. ∎

See [150, 46, 79, 47, 149, 42, 41, 40, 39, 45, 37, 44] for more results about
defective colourings of graphs with given maximum average degree.

Little is known about clustered colourings of graphs with given maximum
average degree.

######  Open Problem 30.

What is $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{A}_{m})$?
The best known bounds are
$\lfloor{\frac{m}{2}}\rfloor+1\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{A}_{m})\leqslant\lfloor{m}\rfloor+1$.

Maximum average degree is closely related to degeneracy. Recall that a graph
$G$ is $k$-degenerate if every subgraph of $G$ has minimum degree at most $k$.
A greedy algorithm shows that every $k$-degenerate graph is properly
$(k+1)$-colourable. Since the standard example $S(k,d)$ is $k$-degenerate,
this bound cannot be improved even for defective colourings. Thus for the
class of $k$-degenerate graphs, the defective chromatic number, defective
choice number, clustered chromatic number, clustered choice number, and
(proper) chromatic number all equal $k+1$.

##  6 Excluding a Subgraph

For every graph $H$, the class of graphs with no $H$ subgraph has bounded
chromatic number if and only if $H$ is a forest. The same result holds for
defective chromatic number and clustered chromatic number. To see this,
observe that if $H$ contains a cycle, then graphs with girth greater than
$|V(H)|$ contain no $H$ subgraph, and by the classical result of Erdős [95]
there are graphs with arbitrarily large girth and chromatic number. By
Proposition 3, the defective and clustered chromatic numbers are also
arbitrarily large. Conversely, say $F$ is a forest with $n$ vertices. A well
known greedy embedding procedure shows that every graph with minimum degree at
least $n-1$ contains $F$ as a subgraph. That is, every graph containing no $F$
subgraph is $(n-2)$-degenerate, and is thus $(n-1)$-colourable. This bound is
tight since $K_{n-1}$ contains no $F$ subgraph and is $(n-1)$-chromatic. In
short, for the class of graphs containing no $F$ subgraph, the chromatic
number equals $n-1$. The following result by Ossona de Mendez et al. [185]
shows that defective colourings exhibit qualitatively different behaviour.

######  Theorem 31 ([185]).

Let $T$ be a tree with $n\geqslant 2$ vertices and radius $r\geqslant 1$. Then
every graph containing no $T$ subgraph is $r$-colourable with defect $n-2$.

###### Proof.

For $i=1,2,\dots,r-1$, let $V_{i}$ be the set of vertices $v\in
V(G)\setminus(V_{1}\cup\dots\cup V_{i-1})$ that have at most $n-2$ neighbours
in $V(G)\setminus(V_{1}\cup\dots\cup V_{i-1})$. Let
$V_{r}:=V(G)\setminus(V_{1}\cup\dots\cup V_{r-1})$. Then $V_{1}\cup\dots\cup
V_{r}$ is a partition of $V(G)$. For $i\in[1,r-1]$, by construction,
$G[V_{i}]$ has maximum degree at most $n-2$, as desired. Suppose that
$G[V_{r}]$ has maximum degree at least $n-1$. We now show that $T$ is a
subgraph of $G$, where each vertex $v$ of $T$ is mapped to a vertex
$v^{\prime}$ of $G$. Let $x$ be the centre of $T$. Map the vertices of $T$ to
vertices in $G$ in order of their distance from $x$ in $T$, where $x$ is
mapped to a vertex $x^{\prime}$ with degree at least $n-1$ in $G[V_{r}]$. The
key invariant is that each vertex $v$ at distance $j\in[1,r]$ from $x$ in $T$
is mapped to a vertex $v^{\prime}$ in $V_{r-j+1}\cup\dots\cup V_{r}$. If $j=0$
then $v=x$ and by assumption, $v^{\prime}=x^{\prime}$ has at least $n-1$
neighbours in $V_{r}$. If $j\in[1,r-1]$ then by construction, $v^{\prime}$ has
at least $n-1$ neighbours in $V_{r-j}\cup\dots\cup V_{r}$ (otherwise
$v^{\prime}$ would be in $V_{r-j}$). Thus there are always unmapped vertices
in $V_{r-j}\cup\dots\cup V_{r}$ to choose as the children of $v$. Hence $T$ is
a subgraph of $G$. This contradiction shows that $G[V_{r}]$ has maximum degree
at most $n-2$, and $G$ is $r$-colourable with defect $n-2$. ∎

The number of colours in Theorem 31 is best possible for the complete binary
tree $T$ of radius $r$. Since $S(r-1,d)$ contains no $T$ subgraph, Lemmas 1
and 31 imply that the defective chromatic number of the class of graphs
containing no $T$ subgraph equals $r$.

######  Open Problem 32.

For a tree $T$, what is the clustered chromatic number of the class of graphs
with no $T$ subgraph?

The results in Section 4 on
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{\Delta})$ are
relevant to this question since a graph has maximum degree at most $\Delta$ if
and only if it excludes $K_{1,\Delta+1}$ as a subgraph. Section 8.5 studies
colourings of graphs that exclude a given path subgraph.

##  7 Excluding a Shallow Minor

###  7.1 Excluding $K_{s,t}^{*}$

As illustrated in Figure 6, for integers $s,t\geqslant 1$, let $K_{s,t}^{*}$
be the bipartite graph obtained from $K_{s,t}$ by adding $\binom{s}{2}$ new
vertices, each adjacent to a distinct pair of vertices in the colour class of
$s$ vertices in $K_{s,t}$. Ossona de Mendez et al. [185] studied defective
colourings for graphs excluding $K^{*}_{s,t}$ as a subgraph, where the defect
bound depends on the density of shallow topological minors. Let $\nabla(G)$ be
the maximum average degree of a graph $H$ such that the 1-subdivision of $H$
is a subgraph of $G$.

Figure 6: The graph $K^{*}_{7,13}$.

######  Theorem 33 ([185]).

Every graph $G$ with no $K_{s,t}^{*}$ subgraph is $s$-choosable with defect
$\ell-s+1$, where $\delta=\operatorname{mad}(G)$ and $\nabla=\nabla(G)$ and

$\ell:=\ell(s,t,\delta,\nabla):=\begin{cases}\lfloor{(\delta-s)\left(\binom{\lfloor\nabla\rfloor}{s-1}(t-1)+\tfrac{1}{2}\nabla\right)+\delta}\rfloor&\text{if
}s>2,\\\ \lfloor{\tfrac{1}{2}(\delta-2)\nabla t+\delta}\rfloor&\text{if
}s=2,\\\ t-1&\text{if }s=1.\end{cases}$

###### Proof.

Assume for contradiction that $G$ has minimum degree at least $s$ (thus
$s\leqslant\delta$) and that $G$ contains no $\ell$-light edge. The case $s=1$
is simple: Since $G$ has minimum degree at least 1, $G$ has at least one edge,
which is $\ell$-light since $\Delta(G)\leqslant t-1$ and $\ell=t-1$. Now
assume that $s\geqslant 2$.

Let $A$ be the set of vertices in $G$ of degree at most $\ell$. Let
$B:=V(G)\setminus A$. Let $a:=|A|$ and $b:=|B|$. Since $G$ has a vertex of
degree at most $\delta$ and $\delta\leqslant\ell$, we deduce that $a>0$. Note
that no two vertices in $A$ are adjacent.

Since the average degree of $G$ is at most $\delta$,

$(\ell+1)b+sa\leqslant 2|E(G)|\leqslant\delta(a+b).$

That is,

$(\ell+1-\delta)b\leqslant(\delta-s)a.$ (2)

Let $G^{\prime}$ be the graph obtained from $G-E(G[B])$ by greedily finding a
vertex $w\in A$ having a pair of non-adjacent neighbours $x$, $y$ in $B$ and
replacing $w$ by an edge joining $x$ and $y$ (by deleting all edges incident
with $w$ except $xw$, $yw$ and contracting $xw$), until no such vertex $w$
exists.

Let $A^{\prime}:=V(G^{\prime})\setminus B$ and $a^{\prime}:=|A^{\prime}|$.
Clearly the $1$-subdivision of $G^{\prime}[B]$ is a subgraph of $G$. So every
subgraph of $G^{\prime}[B]$ has average degree at most $\nabla$. Since
$G^{\prime}[B]$ contains at least $a-a^{\prime}$ edges,

$a-a^{\prime}\leqslant\tfrac{1}{2}\nabla b.$ (3)

Let $M$ be the number of cliques of size $s$ in $G^{\prime}[B]$. Since
$G^{\prime}[B]$ is $\lfloor\nabla\rfloor$-degenerate,

$M\leqslant\binom{\lfloor\nabla\rfloor}{s-1}b$

(See [180, p. 25] or [222]). If $s=2$, then the following better inequality
holds:

$M\leqslant\tfrac{1}{2}\nabla b.$

For each vertex $v\in A^{\prime}$, since $v$ was not contracted in the
creation of $G^{\prime}$, the set of neighbours of $v$ in $B$ is a clique of
size at least $s$. Thus if $a^{\prime}>M(t-1)$, then there are at least $t$
vertices in $A^{\prime}$ sharing at least $s$ common neighbours in $B$. These
$t$ vertices and their $s$ common neighbours in $B$ with the vertices in
$A-A^{\prime}$ form a $K_{s,t}^{*}$ subgraph of $G$, contradicting our
assumption. Thus,

$a^{\prime}\leqslant M(t-1).$ (4)

By (2), (3) and (4),

$\ell+1\leqslant(\delta-s)\left(\frac{M}{b}(t-1)+\tfrac{1}{2}\nabla\right)+\delta,$

contradicting the definition of $\ell$. Thus $G$ has minimum degree at most
$s-1$ or $G$ contains an $\ell$-light edge. The theorem now follows from Lemma
5. ∎

Theorem 33, in conjunction with the standard example, determines the defective
chromatic number for several graph classes of interest; see Sections 7.5, 7.2,
7.3, 7.4 and 7.6. Moreover, Theorem 33 determines the defective choice number
for a very broad class of graphs—complete bipartite subgraphs are the key.

######  Theorem 34 ([185, 84]).

Let $\mathcal{G}$ be a subgraph-closed class of graphs with
$\operatorname{mad}(\mathcal{G})$ and $\nabla(\mathcal{G})$ bounded (which
holds if $\mathcal{G}$ is minor-closed). Then
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{G})$
equals the minimum integer $s$ such that $K_{s,t}\not\in\mathcal{G}$ for some
integer $t$.

###### Proof.

If $K_{s,t}\not\in\mathcal{G}$ for some $s,t\geqslant 1$, then by Theorem 33,
every graph in $\mathcal{G}$ is $s$-choosable with defect bounded by a
function of $s$, $t$, $\operatorname{mad}(\mathcal{G})$ and
$\nabla(\mathcal{G})$. This proves the claimed upper bound. Conversely, let
$s:=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{G})$.
Then for some $d$, every graph in $\mathcal{G}$ is $s$-choosable with defect
$d$. By Lemma 35 below, if $t=(ds+1)s^{s}$ then $K_{s,t}$ is not in
$\mathcal{G}$. ∎

######  Lemma 35.

For $s\geqslant 1$ and $d\geqslant 0$, if $t=(ds+1)s^{s}$, then the complete
bipartite graph $K_{s,t}$ is not $s$-choosable with defect $d$.

###### Proof.

Let $A$ and $B$ be the colour classes of $K_{s,t}$ with $|A|=s$ and $|B|=t$.
Say $A=\\{v_{1},\dots,v_{s}\\}$. Let $X_{1},\dots,X_{s}$ be pairwise disjoint
sets of colours, each of size $s$. Let $L$ be the following $s$-list
assignment for $K_{s,t}$. Let $L(v_{i}):=X_{i}$ for each vertex $v_{i}\in A$.
For each vector $(c_{1},\dots,c_{s})$ with $c_{i}\in X_{i}$ for each
$i\in[s]$, let $L(x):=\\{c_{1},\dots,c_{s}\\}$ for $ds+1$ vertices $x$ in $B$.
This is possible since $|B|=(ds+1)s^{s}$. Consider an $L$-colouring of
$K_{s,t}$. Say each vertex $v_{i}$ is coloured $c_{i}\in L(v_{i})$. Since
$X_{i}\cap X_{j}=\emptyset$, we have $c_{i}\neq c_{j}$ for distinct
$i,j\in[s]$. By construction, there are $ds+1$ vertices $x\in B$ with
$L(x)=\\{c_{1},\dots,c_{s}\\}$. At least $d+1$ of these vertices are assigned
the same colour, say $c_{i}$. Thus $v_{i}$ has monochromatic degree at least
$d+1$. Hence $K_{s,t}$ is not $L$-colourable with defect $d$. Therefore
$K_{s,t}$ is not $s$-choosable with defect $d$. ∎

Note that Theorem 34 generalises several previous results. For example,
Theorem 34 says that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{O})=2$
since $K_{2,3}$ is not outerplanar, but $K_{1,n}$ is outerplanar for all $n$.
Similarly,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{P})=3$
since $K_{3,3}$ is not planar, but $K_{2,n}$ is planar for all $n$. More
generally, Theorem 34 immediately implies:

######  Corollary 36.

For every graph $H$,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{M}_{H})$
equals the minimum integer $s$ such that $H$ is a minor of $K_{s,t}$ for some
integer $t$.

Theorem 34 also determines the defective choice number for graphs excluding a
fixed immersion (see Theorem 52).

###  7.2 Linklessly Embeddable Graphs

A graph is _linklessly embeddable_ if it has an embedding in $\mathbb{R}^{3}$
with no two linked cycles [201, 199]. Let $\mathcal{L}$ be the class of
linklessly embeddable graphs. Then $\mathcal{L}$ is a minor-closed class whose
minimal excluded minors are the so-called Petersen family [200], which
includes $K_{6}$, $K_{4,4}$ minus an edge, and the Petersen graph. Since
linklessly embeddable graphs exclude $K_{6}$ minors, they are $5$-colourable
[198] and $8$-choosable [23]. It is open whether $K_{6}$-minor-free graphs or
linklessly embeddable graphs are $6$-choosable [23].

Ossona de Mendez et al. [185] determined
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{L})$ as follows.
A graph is _apex_ if deleting at most one vertex makes it planar. Every apex
graph is linklessly embeddable [199]. Since $S(2,d)$ is planar, $S(3,d)$ is
apex, and thus linklessly embeddable. By Lemma 1,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{L})\geqslant 4$.
Note that the weaker lower bound,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{L})\geqslant
4$, follows from Theorem 34 since $K_{4,4}\not\in\mathcal{L}$. Mader’s theorem
[168] for $K_{6}$-minor-free graphs implies that linklessly embeddable graphs
have average degree less than 8 and minimum degree at most 7. Since linklessly
embeddable graphs exclude $K_{4,4}$ minors, Theorem 33 implies the upper bound
in the following theorem.

######  Theorem 37 ([185]).

Every linklessly embeddable graph is $4$-choosable with defect $440$, and

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{L})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{L})=4.$

Note that Theorem 34 also implies
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{L})=4$
since $K_{4,4}$ is not linkless, but $K_{3,n}$ is linkless for all $n$.

We have the following result for clustered colourings of linklessly embeddable
graphs.

######  Theorem 38.

Every linklessly embeddable graph is $5$-choosable with clustering $62948$,
and

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{L})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{L})=5.$

###### Proof.

The upper bound follows from Theorem 58 since every linkless graph contains no
$K_{6}$-minor. Since $\overline{S}(3,c)$ is planar, $\overline{S}(4,c)$ is
apex, and thus linklessly embeddable. The lower bound then follows from Lemma
2. ∎

###  7.3 Knotlessly Embeddable Graphs

A graph is _knotlessly embeddable_ if it has an embedding in $\mathbb{R}^{3}$
in which every cycle forms a trivial knot; see [191] for a survey. Let
$\mathcal{K}$ be the class of knotlessly embeddable graphs. Then $\mathcal{K}$
is a minor-closed class whose minimal excluded minors include $K_{7}$ and
$K_{3,3,1,1}$ [63, 102]. More than 260 minimal excluded minors are known
[112], but the full list of minimal excluded minors is unknown. Since
knotlessly embeddable graphs exclude $K_{7}$ minors, they are $8$-colourable
[7, 132]. Mader [168] proved that $K_{7}$-minor-free graphs have average
degree less than 10, which implies they are $9$-degenerate and thus
$10$-choosable. It is open whether $K_{7}$-minor-free graphs or knotlessly
embeddable graphs are $6$-colourable or $7$-choosable [23].

Ossona de Mendez et al. [185] determined the defective chromatic number of
knotlessly embeddable graphs as follows. A graph is _$2$ -apex_ if deleting at
most two vertices makes it planar. Blain et al. [31] and Ozawa and Tsutsumi
[186] proved that every $2$-apex graph is knotlessly embeddable. Since every
block of $S(4,d)$ is $2$-apex, $S(4,d)$ is knotlessly embeddable, as
illustrated in Figure 7. By Lemma 1,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{K})\geqslant 5$.
Since $K_{3,3,1,1}$ is a minor of $K_{5,3}^{*}$, knotlessly embeddable graphs
do not contain a $K_{5,3}^{*}$ subgraph. Since
$\operatorname{mad}(\mathcal{K})<10$, Theorem 33 implies the following result.

######  Theorem 39 ([185]).

Every knotlessly embeddable graph is $5$-choosable with defect $660$, and

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{K})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{K})=5.$

Figure 7: $S(4,d)$ is knotlessly embeddable.

We have the following result for clustered colourings of knotlessly embeddable
graphs.

######  Theorem 40.

Every knotlessly embeddable graph is $6$-choosable with clustering $99958$,
and

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{K})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{K})=6.$

###### Proof.

The upper bound follows from Theorem 58 since every knotless graph contains no
$K_{7}$-minor. Since every block of $\overline{S}(5,d)$ is $2$-apex,
$\overline{S}(5,d)$ is knotlessly embeddable. The lower bound then follows
from Lemma 2. ∎

###  7.4 Colin de Verdière Parameter

The Colin de Verdière parameter $\mu(G)$ is an important graph invariant
introduced by Colin de Verdière [61, 62]; see [127, 202] for surveys. It is
known that $\mu(G)\leqslant 1$ if and only if $G$ is a disjoint union of
paths, $\mu(G)\leqslant 2$ if and only if $G$ is outerplanar, $\mu(G)\leqslant
3$ if and only if $G$ is planar, and $\mu(G)\leqslant 4$ if and only if $G$ is
linklessly embeddable. A famous conjecture of Colin de Verdière [61] states
that $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(G)\leqslant\mu(G)+1$ (which
implies the 4-colour theorem, and is implied by Hadwiger’s Conjecture). Ossona
de Mendez et al. [185] showed that for defective colourings one fewer colour
suffices. Let $\mathcal{V}_{k}:=\\{G:\mu(G)\leqslant k\\}$.

######  Theorem 41 ([185]).

For $k\geqslant 1$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{V}_{k})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{V}_{k})=k.$

###### Proof.

$\mathcal{V}_{k}$ is a minor-closed class [61, 62]. van der Holst et al. [127]
proved that $\mu(K_{s,t})=s+1$ for $t\geqslant\max\\{s,3\\}$. Thus, if
$\mu(G)\leqslant k$ then $G$ contains no $K_{k,\max(k,3)}$ minor, and
$\operatorname{mad}(G)\leqslant 2\nabla(G)\leqslant O(k\sqrt{\log k})$.
Theorem 33 with $s=k$ and $t=\max\\{k,3\\}$ implies that $G$ is $k$-choosable
with defect $2^{O(k\log\log k)}$. Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{V}_{k})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{V}_{k})\leqslant
k$. For the lower bound, van der Holst et al. [127] proved that $\mu(G)$
equals the maximum of $\mu(G^{\prime})$, taken over the components
$G^{\prime}$ of $G$, and if $G$ has a dominant vertex $v$, then
$\mu(G)=\mu(G-v)+1$. It follows that the standard example $S(k-1,d)$ is in
$\mathcal{V}_{k}$ for $d\geqslant 2$. Lemma 1 then implies that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{V}_{k})\geqslant
k$. Note that the weaker lower bound,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{V}_{k})\geqslant
k$, follows from Theorem 34 since $K_{k,\max\\{k,3\\}}\not\in\mathcal{V}_{k}$.
∎

Theorem 41 generalises Theorem 37 which corresponds to the case $k=4$.

Clustered colourings provide a natural approach to the conjecture of Colin de
Verdière [61] mentioned above.

######  Conjecture 42.

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{V}_{k})=k+1$.

Note that Conjecture 42 with $k\leqslant 7$ is implied by Theorem 58 below
since graphs in $\mathcal{V}_{k}$ contain no $K_{k+2}$ minor.

###  7.5 Crossings

This section considers defective colourings of graphs with linear crossing
number. For an integer $g\geqslant 0$ and real number $k\geqslant 0$, let
$\mathcal{E}_{g}^{k}$ be the class of graphs $G$ such that every subgraph $H$
of $G$ has a drawing on a surface of Euler genus $g$ with at most $k\,|E(H)|$
crossings. (In a drawing, we assume that no three edges cross at a common
point.) This says that the average number of crossings per edge is at most
$2k$ (for every subgraph). Of course, a graph is planar if and only if it is
in $\mathcal{E}_{0}$, and a graph has Euler genus at most $g$ if and only if
it is in $\mathcal{E}_{g}^{0}$.

Graphs that can be drawn in the plane with at most $k$ crossings per edge, so
called _$k$ -planar graphs_, are examples of graphs in
$\mathcal{E}_{0}^{(k/2)}$. Pach and Tóth [187] proved that $k$-planar graphs
have average degree $O(\sqrt{k})$. It follows that $k$-planar graphs are
$O(\sqrt{k})$-colourable, which is best possible since $K_{n}$ is
$O(n^{2})$-planar. Say a graph is _$(g,k)$ -planar_ if it can be drawn on a
surface with Euler genus $g$ with at most $k$ crossings per edge. Such graphs
are in $\mathcal{E}_{g}^{(k/2)}$. Also note that even 1-planar graphs do not
form a minor-closed class. For example, the $n\times n\times 2$ grid graph is
1-planar, as illustrated in Figure 8, but contracting the $i$-th row in the
front grid with the $i$-column in the back grid (plus the edge joining them)
creates $K_{n}$ as a minor.

Figure 8: The $n\times n\times 2$ grid graph is 1-planar.

Ossona de Mendez et al. [185] showed that Theorem 33 is applicable for graphs
in $\mathcal{E}_{g}^{k}$. In particular, such graphs contain no
$K_{3,3k(2g+3)(2g+2)+2}$ subgraph and have $\operatorname{mad}\leqslant
O(\sqrt{(k+1)(g+1)})$ and $\nabla\leqslant O(\sqrt{(k+1)(g+1)})$. The first
claim here is proved using a standard technique of counting copies of
$K_{3,3}$. The second claim is proved using the crossing lemma. The next
theorem follows. It is a substantial generalisation of Theorem 8 (the $g=k=0$
case) and Theorem 11 (the $k=0$ case), with a worse defect bound.

######  Theorem 43 ([185]).

For every integer $g\geqslant 0$ and real number $k\geqslant 0$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{E}_{g}^{k})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{E}_{g}^{k})=3.$

In particular, every graph in $\mathcal{E}_{g}^{k}$ is $3$-choosable with
defect $O((k+1)^{5/2}(g+1)^{7/2})$.

######  Open Problem 44.

What is the clustered chromatic number of $k$-planar graphs? What is the
clustered chromatic number of $(g,k)$-planar graphs? What is the clustered
chromatic number of $\mathcal{E}_{g}^{k}$?

It may be that the answer to all these questions is 4. Here we prove the
answer is at most 12 for the first two questions.

######  Proposition 45.

Every $(g,k)$-planar graph $G$ is 12-colourable with clustering
$O((k+1)^{7/2}(g+1)^{9/2})$.

###### Proof.

By Theorem 43, $G$ is 3-colourable with defect $O((k+1)^{5/2}(g+1)^{7/2})$.
That is, $G$ contains three induced subgraphs $G_{1}$, $G_{2}$ and $G_{3}$ of
$G$ each with maximum degree at most $O((k+1)^{5/2}(g+1)^{7/2})$, where
$V(G)=\bigcup_{i}V(G_{i})$. Dujmović et al. [80] proved that every
$(g,k)$-planar graph has layered treewidth $O((g+1)(k+1))$. Apply this result
to each $G_{i}$. Thus, for some layering $V_{1},\dots,V_{n}$ of $G_{i}$, each
layer $G_{i}[V_{j}]$ has treewidth $O((g+1)(k+1))$. By Theorem 55,
$G_{i}[V_{j}]$ is 2-colourable with clustering $O((k+1)^{7/2}(g+1)^{9/2})$.
Within $G_{i}$, use two colours for odd $j$ and two distinct colours for even
$j$. Each monochromatic component is contained in some $V_{i}$. The total
number of colours is $3\times 2\times 2=12$. ∎

###  7.6 Stack and Queue Layouts

A _$k$ -stack layout_ of a graph $G$ consists of a linear ordering
$v_{1},\dots,v_{n}$ of $V(G)$ and a partition $E_{1},\dots,E_{k}$ of $E(G)$
such that no two edges in $E_{i}$ cross with respect to $v_{1},\dots,v_{n}$
for each $i\in[1,k]$. Here edges $v_{a}v_{b}$ and $v_{c}v_{d}$ _cross_ if
$a<c<b<d$. A graph is a _$k$ -stack graph_ if it has a $k$-stack layout. The
_stack-number_ of a graph $G$ is the minimum integer $k$ for which $G$ is a
$k$-stack graph. Stack layouts are also called _book embeddings_ , and stack-
number is also called _book-thickness_ , _fixed outer-thickness_ and _page-
number_. Let $\mathcal{S}_{k}$ be the class of $k$-stack graphs. Dujmović and
Wood [83] showed that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{S}_{k})\in\\{2k,2k+1,2k+2\\}$.
For defective colourings, Ossona de Mendez et al. [185] showed that $k+1$
colours suffice.

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

The class of $k$-stack graphs has defective chromatic number and defective
choice number equal to $k+1$. In particular, every $k$-stack graph is
$(k+1)$-choosable with defect $2^{O(k\log k)}$.

###### Proof.

The lower bound follows from Lemma 1 since an easy inductive argument shows
that $S(k,d)$ is a $k$-stack graph for all $d$. For the upper bound,
$K_{k+1,k(k+1)+1}$ is not a $k$-stack graph [30]; see also [70]. Every
$k$-stack graph $G$ has average degree less than $2k+2$ (see [30, 83]) and
$\nabla(G)\leqslant 20k^{2}$ (see [92, 181]). The result follows from Theorem
33 with $s=k+1$ and $t=k(k+1)+1$, since
$\ell(k+1,k(k+1)+1,2k+2,40k^{2})\leqslant 2^{O(k\log k)}$. ∎

A _$k$ -queue layout_ of a graph $G$ consists of a linear ordering
$v_{1},\dots,v_{n}$ of $V(G)$ and a partition $E_{1},\dots,E_{k}$ of $E(G)$
such that no two edges in $E_{i}$ are nested with respect to
$v_{1},\dots,v_{n}$ for each $i\in[1,k]$. Here edges $v_{a}v_{b}$ and
$v_{c}v_{d}$ are _nested_ if $a<c<d<b$. The _queue-number_ of a graph $G$ is
the minimum integer $k$ for which $G$ has a $k$-queue layout. A graph is a
_$k$ -queue graph_ if it has a $k$-queue layout. Let $\mathcal{Q}_{k}$ be the
class of $k$-queue graphs. Dujmović and Wood [83] state that determining
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{Q}_{k})$ is an open
problem, and showed lower and upper bounds of $2k+1$ and $4k$. Ossona de
Mendez et al. [185] proved the following partial answer to this question.

######  Theorem 47 ([185]).

Every $k$-queue graph is $(2k+1)$-choosable with defect $2^{O(k\log k)}$.

###### Proof.

Heath and Rosenberg [122] proved that $K_{2k+1,2k+1}$ is not a $k$-queue
graph. Every $k$-queue graph $G$ has $\operatorname{mad}(G)<4k$ (see [122,
188, 83]) and $\nabla(G)<(2k+2)^{2}$ (see [181]). The result then follows from
Theorem 33 with $s=2k+1$ and $t=2k+1$, since
$\ell(2k+1,2k+1,4k,2(2k+2)^{2})\leqslant 2^{O(k\log k)}$. ∎

An easy inductive construction shows that $S(k,n)$ has a $k$-queue layout.
Thus
$k+1\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{Q}_{k})\leqslant
2k+1$ by Lemma 1 and Theorem 47. It remains an open problem to determine
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{Q}_{k})$.

Now consider clustered colourings of $k$-stack and $k$-queue graphs. The
standard example $\overline{S}(2,c)$ is outerplanar, and thus has a 1-stack
layout. An easy inductive construction then shows that $\overline{S}(k,c)$ has
a $(k-1)$-stack layout (for $k\geqslant 2$) and a $k$-queue layout. The best
known upper bounds come from degeneracy: every $k$-stack graph is
$(2k+1)$-degenerate and every $k$-queue graph is $(4k-1)$-degenerate (see
[83]). Thus

$\displaystyle k+2$
$\displaystyle\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{S}_{k})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{S}_{k})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}(\mathcal{S}_{k})\leqslant
2k+2\text{ and }$ $\displaystyle k+1$
$\displaystyle\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{Q}_{k})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{Q}_{k})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}(\mathcal{Q}_{k})\leqslant
4k.$

Closing the gap in these bounds is interesting because the existing methods
say nothing about clustered colourings of $k$-stack or $k$-queue graphs. For
example, Lemma 13 is not applicable since 3-stack and 2-queue graphs do not
have sublinear balanced separators. Indeed, Dujmović et al. [82] constructed
(cubic bipartite) 3-stack expander graphs and (cubic bipartite) 2-queue
expander graphs.

###  7.7 Excluded Immersions

This section considers colourings of graphs excluding a fixed immersion. A
graph $G$ contains a graph $H$ as an _immersion_ if the vertices of $H$ can be
mapped to distinct vertices of $G$, and the edges of $H$ can be mapped to
pairwise edge-disjoint paths in $G$, such that each edge $vw$ of $H$ is mapped
to a path in $G$ whose endpoints are the images of $v$ and $w$. The image in
$G$ of each vertex in $H$ is called a _branch vertex_. A graph $G$ contains a
graph $H$ as a _strong immersion_ if $G$ contains $H$ as an immersion such
that for each edge $vw$ of $H$, no internal vertex of the path in $G$
corresponding to $vw$ is a branch vertex. Let $\mathcal{I}_{t}$ be the class
of graphs not containing $K_{t}$ as an immersion. Let
$\mathcal{I}^{\prime}_{t}$ be the class of graphs not containing $K_{t}$ as a
strong immersion.

Lescure and Meyniel [157] and Abu-Khzam and Langston [1] independently
conjectured that every $K_{t}$-immersion-free graph is properly
$(t-1)$-colourable. Often motivated by this question, structural and colouring
properties of graphs excluding a fixed immersion have recently been widely
studied. The best upper bound, due to Gauthier et al. [106], says that every
$K_{t}$-immersion-free graph is properly $(3.54t+3)$-colourable

Van den Heuvel and Wood [124] proved that the defective chromatic number of
$K_{t}$-immersion-free graphs equals 2. The proof, presented below, is based
on the following structure theorem of DeVos et al. [74]. Almost the same
result can be concluded from a structure theorem by Wollan [219]. Since Lemma
48 is not proved explicitly in [74] we include the full proof, which relies on
the following definitions. For each edge $xy$ of a tree $T$, let $T(xy)$ and
$T(yx)$ be the components of $T-xy$, where $x$ is in $T(xy)$ and $y$ is in
$T(yx)$. For a tree $T$ and graph $G$, a _$T$ -partition_ of $G$ is a
partition $(T_{x}\subseteq V(G):x\in V(T))$ of $V(G)$ indexed by the nodes of
$T$. Each set $T_{x}$ is called a _bag_. Note that a bag may be empty. For
each edge $e=xy\in E(T)$, let $G(T,xy)=\bigcup_{z\in V(T(xy))}T_{z}$ and
$G(T,yx)=\bigcup_{z\in V(T(yx))}T_{z}$, and let $E(G,T,e)$ be the set of edges
in $G$ between $G(T,xy)$ and $G(T,yx)$. The _adhesion_ of a $T$-partition is
the maximum, taken over all edges $e$ of $T$, of $|E(G,T,e)|$. For each node
$x$ of $T$, the _torso of $x$_ (with respect to a $T$-partition) is the graph
obtained from $G$ by identifying $G(T,yx)$ into a single vertex for each edge
$xy$ incident to $x$, deleting resulting parallel edges and loops. Note that a
tree $T$ for which $V(G)\subseteq V(T)$ implicitly defines a $T$-partition of
$G$ with $T_{x}=\\{x\\}\cap V(G)$ for each node $x\in V(T)$.

######  Lemma 48 ([74]).

For every graph $G$ that does not contain $K_{t}$ as an immersion, there is a
tree $T$ and a $T$-partition of $G$ with adhesion less than $(t-1)^{2}$, such
that each bag has at most $t-1$ vertices.

###### Proof.

Gomory and Hu [113] proved that for every graph $G$ there is a tree $F$ with
vertex set $V(G)$ such that for all distinct vertices $v,w\in V(G)$, the size
of the smallest edge-cut in $G$ separating $v$ and $w$ equals

$\zeta(e):=\min_{e}|E(G,F,e)|,$

where the minimum is taken over all edges $e$ on the $vw$-path in $F$. Let $S$
be the set of edges $e\in E(F)$ with $\zeta(e)<(t-1)^{2}$.

Suppose that some component $X$ of $F-S$ has at least $t$ vertices. Let
$x,v_{2},v_{3},\dots,v_{t}$ be distinct vertices in $X$. Let $G^{\prime}$ be
the multigraph obtained from $G$ by adding a new vertex $w$ and adding $t-1$
parallel edges between $w$ and $v_{i}$ for each $i\in[2,t]$. We claim that
$G^{\prime}$ contains $(t-1)^{2}$ edge-disjoint $xw$-paths. Consider a set of
vertices $R\subseteq V(G)$ with $x\in R$, such that there are less than
$(t-1)^{2}$ edges between $R$ and $V(G^{\prime})-R$ in $G^{\prime}$. Since
$w\in V(G^{\prime})-R$ has degree $(t-1)^{2}$, some neighbour $v_{i}$ of $w$
is also in $V(G^{\prime})-R$ (where $i\in[2,t]$). Thus in $G$, there is an
edge-cut with less than $(t-1)^{2}$ edges separating $x$ and $v_{i}$, meaning
that $\zeta(e)<(t-1)^{2}$ for some edge $e$ on the $xv_{i}$-path in $F$. But
every such edge $e$ is in $X$, which implies $\zeta(e)\geqslant(t-1)^{2}$.
This contradiction shows (by Menger’s Theorem) that $G^{\prime}$ contains
$(t-1)^{2}$ edge-disjoint $xw$-paths. Hence $G$ contains $(t-1)^{2}$ edge-
disjoint paths starting at $x$, exactly $t-1$ of which end at $v_{i}$ for each
$i\in[2,t]$. Label these $xv_{i}$-paths as $P_{i,j}$, for $j\in[2,t]$. For
$j\neq i$, the combined path $P_{i,j}P_{j,i}$ is a $v_{i}v_{j}$-path, while
each $P_{i,i}$ is a $v_{i}x$ path. Since all these paths are edge-disjoint,
$G$ contains a $K_{t}$-immersion. This contradiction shows that every
component of $F-S$ has at most $t-1$ vertices.

Let $T$ be obtained from $F$ by contracting each connected component of $F-S$
into a single vertex. For each node $x$ of $T$, let $T_{x}$ be the set of
vertices contracted into $x$. Then $\bigl{(}T_{x}:x\in V(T)\bigr{)}$ is the
desired partition. ∎

######  Lemma 49 ([124]).

If a graph $G$ has a $T$-partition with $V(G)\subseteq V(T)$ and adhesion at
most $k$, then $G$ is $2$-colourable with defect $k$.

###### Proof.

We proceed by induction on $|V(G)|+|E(G)|$. The result is trivial if
$|V(G)|\leqslant 2$. Now assume $|V(G)|\geqslant 3$. Call a vertex $v$ of $G$
_large_ if $\deg_{G}(v)\geqslant k+1$; otherwise $v$ is _small_. If
$\deg_{G}(v)\leqslant 1$ for some vertex $v$, then by induction, $G-v$ is
2-colourable with defect $k$; assign $v$ a colour distinct from its neighbour.
Now $G$ is 2-coloured with defect $k$. Now assume that $G$ has minimum degree
at least $2$. If two small vertices $v$ and $w$ are adjacent, then by
induction, $G-vw$ is 2-colourable with defect $k$, which is also a 2-colouring
of $G$ with defect $k$. Now assume that the small vertices are a stable set.
If $G$ has no large vertices, then every 2-colouring of $G$ has defect $k$.
Now assume that $G$ has some large vertex. Let $X$ be the union of all paths
in $T$ whose endpoints are large. Let $u$ be a leaf in $X$. Thus $u$ is large.
Let $v$ be the neighbour of $u$ in $X$, or any neighbour of $u$ if $|V(X)|=1$.
Let $Y:=V(T(uv))\setminus\\{u\\}$. Every vertex in $Y$ is small. Since no two
small vertices are adjacent and $G$ has minimum degree at least 2, every
vertex in $Y$ has at least one neighbour in $T(vu)$. Also, $u$ has at least
$\deg_{G}(u)-|Y|$ neighbours in $T(vu)$. Thus
$|E(G,T,uv)|\geqslant|Y|+\deg_{G}(u)-|Y|\geqslant k+1$, which is a
contradiction. ∎

Note that Lemma 49 with a $O(k^{3})$ defect bound can be concluded from
Theorem 33 with $s=2$.

The following result by Van den Heuvel and Wood [124] is the first main
contribution of this section.

######  Theorem 50 ([124]).

Every graph $G\in\mathcal{I}_{t}$ is $2$-colourable with defect $(t-1)^{3}$,
and

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{I}_{t})=2.$

###### Proof.

By Lemma 48, there is a tree $T$ and a $T$-partition of $G$ with adhesion at
most $(t-1)^{2}-1$, such that each bag has at most $t-1$ vertices. Let $Q$ be
the graph with vertex set $V(T)$, where $xy\in E(Q)$ whenever there is an edge
of $G$ between $T_{x}$ and $T_{y}$. Any one edge of $Q$ corresponds to at most
$t-1$ edges in $G$. By Lemma 49, the graph $Q$ is $2$-colourable with defect
$(t-1)^{2}-1$. Assign to each vertex $v$ in $G$ the colour assigned to the
vertex $x$ in $Q$ with $v\in T_{x}$. Since at most $t-1$ vertices of $G$ are
in each bag, $G$ is $2$-coloured with defect
$(t-1)\cdot\bigl{(}(t-1)^{2}-1\bigr{)}+(t-2)<(t-1)^{3}$. ∎

Van den Heuvel and Wood [124] proved the following result for excluded strong
immersions. The omitted proof is based on a more involved structure theorem of
Dvořák and Wollan [85].

######  Theorem 51 ([124]).

Every graph $G\in\mathcal{I}^{\prime}_{t}$ is $2$-colourable with defect at
most some function $d(t)$, and thus

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{I}^{\prime}_{t})=2.$

While only two colours suffice for defective colourings of graphs excluding a
fixed immersion, significantly more colours are needed for defective list
colouring.

######  Theorem 52.

For all $t\geqslant 2$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{I}_{t})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{I}^{\prime}_{t})=t-1.$

###### Proof.

DeVos et al. [73] proved that
$\operatorname{mad}(\mathcal{I}^{\prime}_{t})\leqslant O(t)$. If the
1-subdivision of a graph $H$ is a subgraph of $G$, then $G$ contains $H$ as a
strong immersion, implying $\nabla(\mathcal{I}^{\prime}_{t})\leqslant O(t)$.
Theorem 34 then implies that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{I}^{\prime}_{t})$
equals the minimum integer $s$ such that $K_{s,n}$ contains $K_{t}$ as a
strong immersion for some $n$. It is easily seen that
$K_{t-1,\binom{t-1}{2}+1}$ contains $K_{t}$ as a strong immersion, but
$K_{t-2,n}$ does not contain $K_{t}$ as a weak immersion for all $n$. The
result follows. ∎

It is an open problem to determine the clustered chromatic number and
clustered choice number of graphs excluding a (strong or weak) $K_{t}$
immersion. We have the following lower bounds. Since every graph with maximum
degree at most $t-2$ contains no $K_{t}$ immersion, by Theorem 24,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{I}^{\prime}_{t})\geqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{I}_{t})\geqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{D}_{t-2})\geqslant\left\lfloor\frac{t+4}{4}\right\rfloor.$

By Theorem 52,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{I}^{\prime}_{t})\geqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{I}_{t})\geqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{I}_{t})=t-1.$

##  8 Minor-Closed Classes

This section studies defective and clustered colourings of graphs in a minor-
closed class. Hadwiger’s Conjecture states that every $K_{t}$-minor-free graph
is $(t-1)$-colourable [116]. This is widely considered one of the most
important open problems in graph theory; see [203] for a survey. Defective and
clustered colourings of $K_{t}$-minor-free graphs provide an avenue for
attacking Hadwiger’s Conjecture.

###  8.1 Excluding a Minor and Bounded Degree

All the known examples of planar graphs that are not 3-colourable with bounded
clustering have unbounded maximum degree. This observation motivated several
authors [151, 11, 159] to ask whether planar graphs with bounded maximum
degree are $3$-colourable with bounded clustering. Esperet and Joret [97]
solved this question in the affirmative and extended the result to graphs of
bounded Euler genus.

######  Theorem 53 ([97]).

Every graph with maximum degree $\Delta$ and Euler genus $g$ is $3$-colourable
with clustering $f(\Delta,g)$, for some function $f$.

Esperet and Joret [97] posed the following open problem

######  Open Problem 54 ([97]).

Are triangle-free planar graphs with bounded maximum degree 2-colourable with
bounded clustering?

Graphs with treewidth $k$ are properly $(k+1)$-colourable, which is best
possible for $K_{k+1}$. Moreover, since the standard example $S(k,d)$ has
treewidth $k$, the defective chromatic number of graphs with treewidth $k$
equals $k+1$. On the other hand, Alon et al. [11] proved that every graph with
maximum degree $\Delta$ and treewidth $k$ is 2-colourable with clustering
$24k\Delta$. The proof was based on a result about tree-partitions by Ding and
Oporowski [75], which was improved by Wood [220]. It follows that:

######  Theorem 55.

Every graph with maximum degree $\Delta$ and treewidth $k$ is 2-colourable
with clustering $\frac{5}{2}(k+1)(\frac{7}{2}\Delta-1)$.

Liu [162] proved a list colouring analogue of Theorem 55: every graph with
maximum degree $\Delta$ and treewidth $k$ is 2-choosable with clustering
$f(k,\Delta)$, for some function $f$.

DeVos et al. [72] proved the conjecture of Robin Thomas that graphs excluding
a fixed minor can be 2-coloured so that each monochromatic subgraph has
bounded treewidth. Alon et al. [11] observed that this result and Theorem 55
together imply that graphs excluding a fixed minor and with bounded maximum
degree are $4$-colourable with bounded clustering. Answering a question of
Esperet and Joret [97], this result was improved by Liu and Oum [163] (using
the graph minor structure theorem):

######  Theorem 56 ([163]).

Every graph containing no $H$-minor and with maximum degree $\Delta$ is
$3$-colourable with clustering $f(\Delta,H)$, for some function $f$.

This theorem generalises Theorem 53 above. It is open whether graphs with
bounded maximum degree and excluding a fixed minor are $3$-choosable with
bounded clustering (Open Problem 18 is a special case).

The above results lead to the following connection between clustered and
defective colourings, which was implicitly observed by Edwards et al. [87].
The second observation was made by Norin et al. [183].

######  Lemma 57 ([87, 183]).

For every minor-closed class $\mathcal{G}$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})\leqslant
3\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G}).$

Moreover, if some planar graph is not in $\mathcal{G}$ then

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})\leqslant
2\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G}).$

###### Proof.

As mentioned above, Liu and Oum [163] proved that for every integer $d$ there
is an integer $c=c(\mathcal{G},d)$ such that every graph in $\mathcal{G}$ with
maximum degree $d$ has a $3$-colouring with clustering $c$. Let
$k:=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})$. That is,
for some integer $d$, every graph $G$ in $\mathcal{G}$ is $k$-colourable with
defect $d$. Apply the result of Liu and Oum [163] to each monochromatic
component of $G$, which has maximum degree at most $d$. Then $G$ is
$3k$-colourable with clustering $c$, and
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})\leqslant 3k$.
For the second claim, Robertson and Seymour [197] proved that a minor-closed
class not containing all planar graphs has bounded treewidth. The result
follows from the method used above, with Theorem 55 in place of the result of
Liu and Oum [163]. ∎

###  8.2 $K_{t}$-Minor-Free Graphs

First consider defective colourings of $K_{t}$-minor-free graphs. Edwards et
al. [87] proved that every $K_{t}$-minor-free graph is $(t-1)$-colourable with
defect $O(t^{2}\log t)$. Their proof gives the same result for
$(t-1)$-choosability. This result is implied by Theorem 33 since
$K_{t-1,1}^{*}$ contains a $K_{t}$ minor. Indeed, the proof of Theorem 33 in
this case is identical to the proof of Edwards et al. [87] (which predated
[185]). Van den Heuvel and Wood [124] improved the upper bound on the defect
in the result of Edwards et al. [87] to $t-2$; see Theorem 61 below. Edwards
et al. [87] also showed that the standard example $S(t-2,d)$ is $K_{t}$-minor-
free. Thus, Lemma 1 implies the following defective version of Hadwiger’s
Conjecture:

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{M}_{K_{t}})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{M}_{K_{t}})=t-1.$
(5)

Now consider clustered colourings of $K_{t}$-minor-free graphs. Note that (5)
implies

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})\geqslant
t-1.$

We now show that the island-based method of Dvořák and Norin [84] determines
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})$ for
$t\leqslant 9$.

######  Theorem 58 ([84]).

For $t\leqslant 9$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})=t-1.$

In particular, every $K_{t}$-minor-free graph $G$ is $(t-1)$-choosable with
clustering

$c_{t}:=\left\lceil{2\left(\frac{5t^{3/2}}{\sqrt{2}-1}\right)^{2}}\right\rceil.$

###### Proof.

For $t\leqslant 9$, the exact extremal function for $K_{t}$-minor-free graphs
is known [77, 167, 168, 169, 139, 207]. In particular, every $K_{t}$-minor-
free graph on $n$ vertices has less than $(t-2)n$ edges for $t\leqslant 9$.
For all $t$, every such graph has a balanced separator of size
$t^{3/2}n^{1/2}$ [12]. By Lemma 13 with $k=t-2$ and $\alpha=1$ and
$\beta=\frac{1}{2}$ and $c=t^{3/2}$, $G$ has a $(t-2)$-island of size at most
$c_{t}$. By Lemma 6, $G$ is $(t-1)$-choosable with clustering $c_{t}$. Since
the standard example $S(t-2,d)$ is $K_{t}$-minor-free, the clustered chromatic
number of $K_{t}$-minor-free graphs is at least $t-1$. Thus for $t\leqslant
9$, the clustered chromatic number of $K_{t}$-minor-free graphs equals $t-1$.
∎

The only obstacle for extending Theorem 58 for larger values of $t$ is that
the exact extremal function is not precisely known. Moreover, for large $t$,
the maximum average degree of $K_{t}$-minor-free graphs tends to
$\Theta(t\sqrt{\log t})$; see [153, 154, 209, 210]. Thus Lemma 13 alone cannot
determine the clustered chromatic number of $K_{t}$-minor-free graphs for
large $t$.

Kawarabayashi and Mohar [147] first proved a $O(t)$ upper bound on
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})$. The
constants in this result have been successively improved, as shown in Table 3,
to

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})\leqslant
2t-2.$

Dvořák and Norin [84] have announced a proof that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}^{\ell}_{\star}(\mathcal{M}_{K_{t}})=t-1$.

Table 3:  Upper bounds on the clustered chromatic number of $K_{t}$-minor-free graphs ($t\geqslant 3$).  | $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})\leqslant$ | clustering | choosability
---|---|---|---
Kawarabayashi and Mohar [147] | $\lceil{\frac{31}{2}t}\rceil$ | $c(t)$ | yes
Wood [221] 111This result depended on a result announced by Norine and Thomas [184, 208] which has not yet been written. | $\lceil{\frac{7t-3}{2}}\rceil$ | $c(t)$ | yes
Edwards et al. [87] | $4t-4$ | $c(t)$ |
Liu and Oum [163] | $3t-3$ | $c(t)$ |
Norin [182] 222See [203] for some of the details. | $2t-2$ | $c(t)$ |
Van den Heuvel and Wood [124] | $2t-2$ | $\lceil{\frac{t-2}{2}}\rceil$ |
Dvořák and Norin [84] | $2t-2$ | $c(t)$ |

Most of the results shown in Table 3 depend on the graph minor structure
theorem, so the clustering function is large and not explicit. The exception
is the self-contained proof of Van den Heuvel and Wood [124], which we now
present.

######  Lemma 59 ([124]).

For every set $A$ of $k\geqslant 1$ vertices in a connected graph $G$, and for
every minimal induced connected subgraph $H$ of $G$ containing $A$,

  1. (1)

$H$ has maximum degree at most $k$, and

  2. (2)

$H$ can be $2$-coloured with clustering
$\bigl{\lceil}{\tfrac{1}{2}k}\bigr{\rceil}$.

###### Proof.

Say $v\in V(H)$. Let $T$ be a spanning tree of $H$ that includes each edge of
$H$ incident with $v$. By the minimality of $H$, every leaf of $T$ is in $A$.
Thus, the number of leaves in $T$ is at least $\deg_{H}(v)$ and at most $k$.
Hence $\deg_{H}(v)\leqslant k$, implying $\Delta(H)\leqslant k$.

To prove (2) by induction on $|V(H)|$. In the base case, $|V(H)|=|A|=k$ and
the result is trivial. Now assume that $|V(H)|>k$. Thus
$V(H-A)\neq\varnothing$, and by the minimality of $H$, every vertex in $H-A$
is a cut-vertex of $H$. Consider a leaf-block $L$ of $H$. Every vertex in $L$,
except the one cut-vertex in $L$, is in $A$. There are at least two leaf-
blocks. Thus $|V(L-v)|\leqslant\tfrac{1}{2}k$ for some leaf block $L$, where
$v$ is the one cut-vertex of $H$ in $L$. Let $H^{\prime}=H-V(L-v)$ and
$A^{\prime}=(A\setminus V(L))\cup\\{v\\}$. Then $H^{\prime}$ is a minimal
induced connected subgraph of $G$ containing $A^{\prime}$, and
$|A^{\prime}|\leqslant k$. By induction, $H^{\prime}$ has a $2$-colouring with
clustering $\bigl{\lceil}{\tfrac{1}{2}k}\bigr{\rceil}$. Colour every vertex in
$L\setminus\\{v\\}$ by the colour not assigned to $v$ in $H^{\prime}$. Now $H$
is $2$-coloured with clustering $\bigl{\lceil}{\tfrac{1}{2}k}\bigr{\rceil}$. ∎

Disjoint subgraphs $H_{1}$ and $H_{2}$ in a graph $G$ are _adjacent_ if some
edge of $G$ has one endpoint in $H_{1}$ and one endpoint in $H_{2}$.

######  Lemma 60 ([124]).

For $t\geqslant 4$, for every $K_{t}$-minor-free graph $G$, there are induced
subgraphs $H_{1},\dots,H_{n}$ of $G$ that partition $V(G)$, and for $i\in[n]$:

  1. (1)

The subgraph $H_{i}$ has maximum degree at most $t-2$, and can be $2$-coloured
with clustering $\bigl{\lceil}{\tfrac{1}{2}(t-2)}\bigr{\rceil}$;

  2. (2)

For each component $C$ of $G-\bigl{(}V(H_{1})\cup\dots\cup V(H_{i})\bigr{)}$,
at most $t-2$ subgraphs in $H_{1},\dots,H_{i}$ are adjacent to $C$, and these
subgraphs are pairwise adjacent.

###### Proof.

We may assume that $G$ is connected. We construct $H_{1},\dots,H_{n}$
iteratively, maintaining properties (1) and (2). Let $H_{1}$ be the subgraph
induced by a single vertex in $G$. Then (1) and (2) hold for $i=1$.

Assume that $H_{1},\dots,H_{i}$ satisfy (1) and (2) for some $i\geqslant 1$,
but $V(H_{1}),\dots,V(H_{i})$ do not partition $V(G)$. Let $C$ be a component
of $G-\bigl{(}V(H_{1})\cup\dots\cup V(H_{i})\bigr{)}$. Let $Q_{1},\dots,Q_{k}$
be the elements of $\\{H_{1},\dots,H_{i}\\}$ that are adjacent to $C$. By (2),
$Q_{1},\dots,Q_{k}$ are pairwise adjacent and $k\leqslant t-2$. Since $G$ is
connected, $k\geqslant 1$.

For $j\in[k]$, let $v_{j}$ be a vertex in $C$ adjacent to $Q_{j}$. By Lemma 59
with $k\leqslant t-2$, there is an induced connected subgraph $H_{i+1}$ of $C$
containing $v_{1},\dots,v_{k}$ that satisfies (1).

Consider a component $C^{\prime}$ of $G-\bigl{(}V(H_{1})\cup\dots\cup
V(H_{i+1})\bigr{)}$. Either $C^{\prime}$ is disjoint from $C$, or $C^{\prime}$
is contained in $C$. If $C^{\prime}$ is disjoint from $C$, then $C^{\prime}$
is a component of $G-\bigl{(}V(H_{1})\cup\dots\cup V(H_{i})\bigr{)}$ and
$C^{\prime}$ is not adjacent to $H_{i+1}$, implying (2) is maintained for
$C^{\prime}$.

Now assume $C^{\prime}$ is contained in $C$. The subgraphs in
$H_{1},\dots,H_{i+1}$ that are adjacent to $C^{\prime}$ are a subset of
$Q_{1},\dots,Q_{k},H_{i+1}$, which are pairwise adjacent. Suppose that $k=t-2$
and $C^{\prime}$ is adjacent to all of $Q_{1},\dots,Q_{t-2},H_{i+1}$. Then $C$
is adjacent to all of $Q_{1},\dots,Q_{t-2}$. Contracting each of
$Q_{1},\dots,Q_{t-2},H_{i+1},C^{\prime}$ into a single vertex gives $K_{t}$ as
a minor of $G$, which is a contradiction. Hence $C^{\prime}$ is adjacent to at
most $t-2$ of $Q_{1},\dots,Q_{t-2},H_{i+1}$, and property (2) is maintained
for $C^{\prime}$. ∎

The following is the main result of Van den Heuvel and Wood [124].

######  Theorem 61 ([124]).

For $t\geqslant 4$, every $K_{t}$-minor-free graph $G$ is $(t-1)$-colourable
with defect $t-2$ and is $(2t-2)$-colourable with clustering
$\lceil{\tfrac{1}{2}(t-2)}\rceil$.

###### Proof.

Let $H_{1},\dots,H_{n}$ be the subgraphs from Lemma 60. By property (2) in
Lemma 60, each subgraph $H_{i}$ is adjacent to at most $t-2$ of
$H_{1},\dots,H_{i-1}$. For $i=1,2,\dots,n$ colour $H_{i}$ with one of $t-1$
colours different from the colours assigned to the at most $t-2$ subgraphs in
$H_{1},\dots,H_{i-1}$ adjacent to $H_{i}$. Since $H_{i}$ has maximum degree
$t-2$, we obtain a $(t-1)$-colouring of $G$ with defect $t-2$. Each $H_{i}$
has a $2$-colouring with clustering
$\bigl{\lceil}{\tfrac{1}{2}(t-2)}\bigr{\rceil}$. The product of these
colourings is a $(2t-2)$-colouring with clustering
$\lceil{\tfrac{1}{2}(t-2)}\rceil$. ∎

Note that the $O(t)$ upper bound on
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{t}})$ has
been extended to the setting of odd minors. In particular, Kawarabayashi [146]
proved that every graph with no odd $K_{t}$-minor is $496t$-colourable with
clustering at most some function $f(t)$. The bound of $496t$ was improved to
$10t-13$ by Kang and Oum [140]. By Proposition 4, these results do not
generalise to the setting of choosability (even for defective colourings),
since complete bipartite graphs contain no odd $K_{3}$ minor and have
unbounded maximum average degree.

###  8.3 $H$-Minor-Free Graphs

Hadwiger’s Conjecture implies that for every graph $H$ with $t$ vertices, the
maximum chromatic number of $H$-minor-free graphs equals $t-1$ (since
$K_{t-1}$ is $H$-minor-free). However, for clustered and defective colourings,
fewer colours often suffice. For example, as discussed in Section 3.4,
Archdeacon [21] proved that graphs embeddable on a fixed surface are
defectively 3-colourable, whereas the maximum chromatic number for graphs of
Euler genus $g$ is $\Theta(\sqrt{g})$. The natural question arises: what is
the defective or clustered chromatic number of the class of $H$-minor-free
graphs, for an arbitrary graph $H$? We will see that the answer depends on the
structure of $H$, unlike the chromatic number which only depends on $|V(H)|$.

Ossona de Mendez et al. [185] observed that the following definition is a key
to answering this question. Let $T$ be a rooted tree. The _depth_ of $T$ is
the maximum number of vertices on a root–to–leaf path in $T$. The _closure_ of
$T$ is obtained from $T$ by adding an edge between every ancestor and
descendent in $T$, as illustrated in Figure 9. The _connected tree-depth_
555This definition is a variant of the more commonly studied notion of the
_tree-depth_ of $H$, denoted by $\operatorname{td}(H)$, which equals the
maximum connected tree-depth of the connected components of $H$. See [180] for
background on tree-depth. If $H$ is connected, then
$\operatorname{td}(H)=\operatorname{\overline{td}}(H)$. In fact,
$\operatorname{td}(H)=\operatorname{\overline{td}}(H)$ unless $H$ has two
connected components $H_{1}$ and $H_{2}$ with
$\operatorname{td}(H_{1})=\operatorname{td}(H_{2})=\operatorname{td}(H)$, in
which case $\operatorname{\overline{td}}(H)=\operatorname{td}(H)+1$. Norin et
al. [183] introduced connected tree-depth to avoid this distinction. of a
graph $H$, denoted by $\operatorname{\overline{td}}(H)$, is the minimum depth
of a rooted tree $T$ such that $H$ is a subgraph of the closure of $T$. Note
that the connected tree-depth is closed under taking minors.

Figure 9:  The closure of a tree of depth 6 contains $K_{5,9}$.

Note that the standard example, $S(h,d)$, is the closure of the complete
$(d+1)$-ary tree of depth $h+1$. By Lemma 1, for every graph $H$, the
defective chromatic number of $H$-minor-free graphs satisfies

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{M}_{H})\geqslant\operatorname{\overline{td}}(H)-1,$
(6)

as observed by Ossona de Mendez et al. [185], who conjectured that equality
holds.

######  Conjecture 62 ([185]).

For every graph $H$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{M}_{H})=\operatorname{\overline{td}}(H)-1.$

Since $K_{s,t}$ has connected tree-depth $\min\\{s,t\\}+1$, by Theorem 33,
Conjecture 62 is true if $H=K_{s,t}$, as proved by Ossona de Mendez et al.
[185], who also proved Conjecture 62 if $\operatorname{\overline{td}}(H)=3$.
Norin et al. [183] provided further evidence for the conjecture by showing
that $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H})$ is
bounded from above by some function of $\operatorname{\overline{td}}(H)$. This
implies that both
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{M}_{H})$ and
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H})$ are tied
to $\operatorname{\overline{td}}(H)$.

######  Theorem 63 ([183]).

For every graph $H$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H})\leqslant
2^{\operatorname{\overline{td}}(H)+1}-4.$

While Ossona de Mendez et al. [185] conjectured that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{M}_{H})=\operatorname{\overline{td}}(H)-1$,
the following lower bound by Norin et al. [183] shows that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H})$ might be
larger, thus providing some distinction between defective and clustered
colourings.

######  Theorem 64 ([183]).

For each $k\geqslant 2$, if $H_{k}$ is the the standard example $S(k-1,2)$
then $H_{k}$ has connected tree-depth $k$ and

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H_{k}})\geqslant
2k-2.$

###### Proof.

Fix an integer $c$. We now recursively define graphs $G_{k}$ (depending on
$c$), and show by induction on $k$ that $G_{k}$ has no $(2k-3)$-colouring with
clustering $c$, and $H_{k}$ is not a minor of $G_{k}$.

For the base case $k=2$, let $G_{2}$ be the path on $c+1$ vertices. Then
$G_{2}$ has no $H_{2}=S(1,2)=K_{1,3}$ minor, and $G_{2}$ has no 1-colouring
with clustering $c$.

Assume $G_{k-1}$ is defined for some $k\geqslant 3$, that $G_{k-1}$ has no
$(2k-5)$-colouring with clustering $c$, and $H_{k-1}$ is not a minor of
$G_{k-1}$. As illustrated in Figure 10, let $G_{k}$ be obtained from a path
$(v_{1},\dots,v_{c+1})$ as follows: for $i\in\\{1,\dots,c\\}$ add $2c-1$
pairwise disjoint copies of $G_{k-1}$ complete to $\\{v_{i},v_{i+1}\\}$.

Figure 10:  Construction of $G_{k}$ in Theorem 64.

Suppose that $G_{k}$ has a $(2k-3)$-colouring with clustering $c$. Then
$v_{i}$ and $v_{i+1}$ receive distinct colours for some $i\in\\{1,\dots,c\\}$.
Consider the $2c-1$ copies of $G_{k-1}$ complete to $\\{v_{i},v_{i+1}\\}$. At
most $c-1$ such copies contain a vertex assigned the same colour as $v_{i}$,
and at most $c-1$ such copies contain a vertex assigned the same colour as
$v_{i+1}$. Thus some copy avoids both colours. Hence $G_{k-1}$ is
$(2k-5)$-coloured with clustering $c$, which is a contradiction. Therefore
$G_{k}$ has no $(2k-3)$-colouring with clustering $c$.

It remains to show that $H_{k}$ is not a minor of $G_{k}$. Suppose that
$G_{k}$ contains a model $\\{J_{x}:x\in V(H_{k})\\}$ of $H_{k}$. Let $r$ be
the root vertex in $H_{k}$. Choose the $H_{k}$-model to minimise $\sum_{x\in
V(H)}|V(J_{x})|$. Thus $J_{r}$ is a connected subgraph of
$(v_{1},\dots,v_{c+1})$. Say $J_{r}=(v_{i},\dots,v_{j})$. Note that $H_{k}-r$
consists of three pairwise disjoint copies of $H_{k-1}$. The model $X$ of one
such copy avoids $v_{i-1}$ and $v_{j+1}$ (if these vertices are defined).
Since $H_{k-1}$ is connected, $X$ is contained in a component of
$G_{k}-\\{v_{i-1},\dots,v_{j+1}\\}$ and is adjacent to $(v_{i},\dots,v_{j})$.
Each such component is a copy of $G_{k-1}$. Thus $H_{k-1}$ is a minor of
$G_{k-1}$, which is a contradiction. Thus $H_{k-1}$ is not a minor of $G_{k}$.
∎

Norin et al. [183] conjectured an analogous upper bound:

######  Conjecture 65 ([183]).

For every graph $H$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H})\leqslant
2\operatorname{\overline{td}}(H)-2.$

Norin et al. [183] observed that Conjecture 65 holds for every graph $H$ with
$\operatorname{\overline{td}}(H)=3$. In this case, as mentioned above, Ossona
de Mendez et al. [185] proved that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{M}_{H})=2$. Since
$H$ is planar, by Lemma 57,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H})\leqslant