2\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{M}_{H})=4=2\operatorname{\overline{td}}(H)-2$,
as claimed.

In the remainder of this section we prove Theorem 63. The proof depends on the
following Erdős-Pósa Theorem by Robertson and Seymour [197]. For a graph $H$
and integer $p\geqslant 1$, let $p\,H$ be the disjoint union of $p$ copies of
$H$.

######  Theorem 66 ([197]; see [192, Lemma 3.10]).

For every graph $H$ with $c$ connected components and for all integers
$p,w\geqslant 1$, for every graph $G$ with treewidth at most $w$ and with no
$p\,H$ minor, there is a set $X\subseteq V(G)$ of size at most $(p-1)(wc-1)$
such that $G-X$ has no $H$ minor.

The next lemma is the heart of the proof of Theorem 63.

######  Lemma 67 ([183]).

For all integers $h,k,w\geqslant 1$, every $S(h-1,k-1)$-minor-free graph $G$
of treewidth at most $w$ is $(2^{h}-2)$-colourable with clustering
$(k-1)(w-1)$.

###### Proof.

We proceed by induction on $h\geqslant 1$, with $w$ and $k$ fixed. The case
$h=1$ is trivial since $S(0,k-1)$ is the 1-vertex graph. Now assume that
$h\geqslant 2$, the claim holds for $h-1$, and $G$ is a $S(h-1,k-1)$-minor-
free graph with treewidth at most $w$. Let $V_{0},V_{1},\dots$ be the BFS
layering of $G$ starting at some vertex $r$.

Fix $i\geqslant 1$. Then $G[V_{i}]$ contains no $k\,S(h-2,k-1)$ as a minor, as
otherwise contracting $V_{0}\cup\dots\cup V_{i-1}$ to a single vertex gives a
$S(h-1,k-1)$ minor (since every vertex in $V_{i}$ has a neighbour in
$V_{i-1}$). Since $G$ has treewidth at most $w$, so does $G[V_{i}]$. By
Theorem 66 with $H=S(h-2,k-1)$ and $c=1$, there is a set $X_{i}\subseteq
V_{i}$ of size at most $(k-1)(w-1)$ such that $G[V_{i}\setminus X_{i}]$ has no
$S(h-2,k-1)$ minor. By induction, $G[V_{i}\setminus X_{i}]$ is
$(2^{h-1}-2)$-colourable with clustering $(k-1)(w-1)$. Use one new colour for
$X_{i}$. Thus $G[V_{i}]$ is $(2^{h-1}-1)$-colourable with clustering
$(k-1)(w-1)$. Use disjoint sets of colours for even and odd $i$, and colour
$r$ by one of the colours used for even $i$. No edge joins $V_{i}$ with
$V_{j}$ for $j\geqslant i+2$. Now $G$ is $(2^{h}-2)$-coloured with clustering
$(k-1)(w-1)$. ∎

To drop the assumption of bounded treewidth, we use the following result of
DeVos, Ding, Oporowski, Sanders, Reed, Seymour, and Vertigan [72].

######  Theorem 68 ([72]).

For every graph $H$ there is an integer $w$ such that for every graph $G$ with
no $H$-minor, there is a partition $V_{1},V_{2}$ of $V(G)$ such that
$G[V_{i}]$ has treewidth at most $w$, for $i\in\\{1,2\\}$.

###### Proof of Theorem 63.

Let $k:=|V(H)|$ and $h:=\operatorname{\overline{td}}(H)$. By definition, $H$
is a subgraph of $S(h-1,k-1)$. Thus every $H$-minor-free graph $G$ contains no
$C(h,k)$-minor. Lemmas 67 and 68 implies that $G$ is $(2^{h+1}-4)$-colourable
with clustering at most some function $g(h,k)$. The claim follows. ∎

Note that Norin et al. [183] proved a weaker bound, roughly
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{H})\leqslant
4^{\operatorname{\overline{td}}(H)}$, with a self-contained proof avoiding
Theorem 68 and thus avoiding the graph minor structure theorem. See [223, 227]
for more about defective choosability in minor-closed classes.

###  8.4 Conjectures

We now present a conjecture of Norin et al. [183] about the clustered
chromatic number of an arbitrary minor-closed class of graphs. Consider the
following recursively defined class of graphs, illustrated in Figure 11. Let
$\mathcal{X}_{1,c}:=\\{P_{c+1},K_{1,c}\\}$. For $k\geqslant 2$, let
$\mathcal{X}_{k,c}$ be the set of graphs obtained by the following three
operations. For the first two operations, consider an arbitrary graph
$G\in\mathcal{X}_{k-1,c}$.

  * •

Let $G^{\prime}$ be the graph obtained from $c$ disjoint copies of $G$ by
adding one dominant vertex. Then $G^{\prime}$ is in $\mathcal{X}_{k,c}$.

  * •

Let $G^{+}$ be the graph obtained from $G$ as follows: for each $k$-clique $D$
in $G$, add a stable set of $k(c-1)+1$ vertices complete to $D$. Then $G^{+}$
is in $\mathcal{X}_{k,c}$.

  * •

If $k\geqslant 3$ and $G\in\mathcal{X}_{k-2,c}$, then let $G^{++}$ be the
graph obtained from $G$ as follows: for each $(k-1)$-clique $D$ in $G$, add a
path of $(c^{2}-1)(k-1)+(c+1)$ vertices complete to $D$. Then $G^{++}$ is in
$\mathcal{X}_{k,c}$.

Figure 11:  Construction of $\mathcal{X}_{k,c}$.

A vertex-coloured graph is _rainbow_ if every vertex receives a distinct
colour.

######  Lemma 69 ([183]).

For every $c\geqslant 1$ and $k\geqslant 2$, for every graph
$G\in\mathcal{X}_{k,c}$, every colouring of $G$ with clustering $c$ contains a
rainbow $K_{k+1}$. In particular, no graph in $\mathcal{X}_{k,c}$ is
$k$-colourable with clustering $c$.

###### Proof.

We proceed by induction on $k\geqslant 1$. In the case $k=1$, every colouring
of $P_{c+1}$ or $K_{1,c}$ with clustering $c$ contains a bichromatic edge, and
we are done. Now assume the claim for $k-1$ and for $k-2$ (if $k\geqslant 3$).

Let $G\in\mathcal{X}_{k-1,c}$. Consider a colouring of $G^{\prime}$ with
clustering $c$. Say the dominant vertex $v$ is blue. At most $c-1$ copies of
$G$ contain a blue vertex. Thus, some copy of $G$ has no blue vertex. By
induction, this copy of $G$ contains a rainbow $K_{k}$. With $v$ we obtain a
rainbow $K_{k+1}$.

Now consider a colouring of $G^{+}$ with clustering $c$. By induction, the
copy of $G$ in $G^{+}$ contains a clique $\\{w_{1},\dots,w_{k}\\}$ receiving
distinct colours. Let $S$ be the set of $k(c-1)+1$ vertices adjacent to
$w_{1},\dots,w_{k}$ in $G^{+}$. At most $c-1$ vertices in $S$ receive the same
colour as $w_{i}$. Thus some vertex in $S$ receives a colour distinct from the
colours assigned to $w_{1},\dots,w_{k}$. Hence $G^{+}$ contains a rainbow
$K_{k+1}$.

Now suppose $k\geqslant 3$ and $G\in\mathcal{X}_{k-2,c}$. Consider a colouring
of $G^{++}$ with clustering $c$. By induction, the copy of $G$ in $G^{++}$
contains a clique $\\{w_{1},\dots,w_{k-1}\\}$ receiving distinct colours. Let
$P$ be the path of $(c^{2}-1)(k-1)+(c+1)$ vertices in $G^{++}$ complete to
$\\{w_{1},\dots,w_{k-1}\\}$. Let $X_{i}$ be the set of vertices in $P$
assigned the same colour as $w_{i}$, and let $X:=\bigcup_{i}X_{i}$. Thus
$|X_{i}|\leqslant c-1$ and $|X|\leqslant(c-1)(k-1)$. Hence $P-X$ has at most
$(c-1)(k-1)+1$ components, and
$|V(P-X)|\geqslant(c^{2}-1)(k-1)+(c+1)-(c-1)(k-1)=c\big{(}(c-1)(k-1)+1\big{)}+1$.
Some component of $P-X$ has at least $c+1$ vertices, and therefore contains a
bichromatic edge $xy$. Then $\\{w_{1},\dots,w_{k-1}\\}\cup\\{x,y\\}$ induces a
rainbow $K_{k+1}$ in $G^{++}$. ∎

Norin et al. [183] conjectured that every minor-closed class that excludes
every graph in $\mathcal{X}_{k,c}$ for some $c$ is $k$-colourable with bounded
clustering. More precisely:

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

For every minor-closed class $\mathcal{M}$ of graphs,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M})$ equals the
minimum integer $k$ such that $\mathcal{M}\cap\mathcal{X}_{k,c}=\emptyset$ for
some integer $c$.

Note that the lower bound in Conjecture 70 follows from Lemma 69. Conjecture
70 is trivial when $k=1$, and Norin et al. [183] proved it when $k=2$. It is
easily seen that Conjecture 70 implies Conjecture 65; see [183].

Now consider the class of graphs excluding the complete bipartite graph
$K_{s,t}$ as a minor, where $s\leqslant t$.Theorems 33 and 6 imply that

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

For clustered colouring, Lemma 57 implies
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{s,t}})\leqslant
3s$. This bound was improved by Dvořák and Norin [84] who proved that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{s,t}})\leqslant
2s+2$, which is the best known upper bound. Van den Heuvel and Wood [124]
proved the lower bound,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{s,t}})\geqslant
s+1$ for $t\geqslant\max\\{s,3\\}$. Their construction is a special case of
the construction shown in Figure 11. Conjecture 70 says that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{M}_{K_{s,t}})=s+1$.

###  8.5 Circumference

The _circumference_ of a graph $G$ is the length of the longest cycle if $G$
contains a cycle, and is 2 if $G$ is a forest. This section studies clustered
colourings of graphs of given circumference. Let $\mathcal{C}_{k}$ be the
class of graphs with circumference at most $k$. A graph has circumference at
most $k$ if and only if it contains no $C_{k+1}$ minor, where $C_{k+1}$ is the
cycle on $k+1$ vertices. Thus $\mathcal{C}_{k}$ is a minor-closed class.

######  Lemma 71.

For all $k,d\geqslant 1$, the standard example $S(k,d)$ contains no path on
$2^{k+1}$ vertices and no cycle of length at least $2^{k}+1$.

###### Proof.

We proceed by induction on $k\geqslant 1$ with $d$ fixed. In the base case,
$S(1,d)=K_{1,d+1}$, which contains no 4-vertex path and no cycle. Now assume
the result for $S(k-1,d)$. Let $v$ be the root vertex of $S(k,d)$.

Suppose that $S(k,d)$ contains a cycle $C$ of length at least $2^{k}+1$. Since
$v$ is a cut vertex, $C$ is contained in one copy of $S(k-1,d)$ plus $v$. Thus
$S(k-1,d)$ contains a path on $2^{k}$ vertices, which is a contradiction. Thus
$S(k,d)$ has no cycle of length at least $2^{k}+1$.

If $S(k,d)$ contains a path $P$ on $2^{k+1}$ vertices, then $P-v$ contains a
path component with least $\lceil{\frac{1}{2}(2^{k+1}-1)}\rceil=2^{k}$
vertices that is contained in a copy of $S(k-1,d)$, which is a contradiction.
Hence $S(k,d)$ contains no path of order $2^{k+1}$. ∎

Figure 12:  The path on $n$ vertices is a subgraph of $S(k,1)$, where
$k=\lceil{\log_{2}(n+1)}\rceil$.

It follows from Lemma 71 that

$\operatorname{\overline{td}}(C_{k+1})=1+\lceil{\log_{2}(k+1)}\rceil=2+\lfloor{\log_{2}k}\rfloor.$

By Equation 6,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{C}_{k})\geqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{C}_{k})\geqslant\operatorname{\overline{td}}(C_{k+1})-1=1+\lfloor{\log_{2}k}\rfloor.$

Mohar et al. [176] proved an upper bound within a factor of 3 of this lower
bound.

######  Theorem 72 ([176]).

For every integer $k\geqslant 2$, every graph $G$ with circumference at most
$k$ is $(3\log_{2}k)$-colourable with clustering $k$. Thus

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{C}_{k})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{C}_{k})\leqslant
3\log_{2}k.$

This result is implied by the following lemma with $C=\emptyset$.

######  Lemma 73 ([176]).

For every integer $k\geqslant 2$, for every graph $G$ with circumference at
most $k$ and for every pre-coloured clique $C$ of size at most $2$ in $G$,
there is a $\lfloor{3\log_{2}k}\rfloor$-colouring of $G$ with clustering $k$,
such that every monochromatic component that intersects $C$ is contained in
$C$.

###### Proof.

We proceed by induction on $k+|V(G)|$. The result is trivial if
$|V(G)|\leqslant 2$. Now assume $|V(G)|\geqslant 3$.

First suppose that $k=2$. Then $G$ is a forest, which is properly
2-colourable. If $|C|\leq 1$ or $|C|=2$ and two colours are used on $C$, we
obtain the desired colouring (with $2<\lfloor{3\log_{2}k}\rfloor$ colours).
Otherwise, $|C|=2$ with the same colour on the vertices in $C$. Contract the
edge $C$ and 2-colour the resulting forest by induction, to obtain the desired
colouring of $G$. Now assume that $k\geqslant 3$.

Suppose that $G$ is not $3$-connected. Then $G$ has a minimal separation
$(G_{1},G_{2})$ with $S:=V(G_{1}\cap G_{2})$ of size at most 2. If $|S|=2$,
then add the edge on $S$ if the edge is not already present. Consider both
$G_{1}$ and $G_{2}$ to contain this edge. Observe that since the separation is
minimal, there is a path in each $G_{j}$ ($j=1,2$) between the two vertices of
$S$. Therefore, adding the edge does not increase the circumference of $G$.
Also note that any valid colouring of the augmented graph will be valid for
the original graph. Since $C$ is a clique, we may assume that $C\subseteq
V(G_{1})$. By induction, there is a $\lfloor{3\log_{2}k}\rfloor$-colouring of
$G_{1}$, with $C$ precoloured, such that every monochromatic component of
$G_{1}$ has order at most $k$ and every monochromatic component of $G_{1}$
that intersects $C$ is contained in $C$. This colours $S$. By induction, there
is a $\lfloor{3\log_{2}k}\rfloor$-colouring of $G_{2}$, with $S$ precoloured,
such that every monochromatic component of $G_{2}$ has order at most $k$ and
every monochromatic component of $G_{2}$ that intersects $S$ is contained in
$S$. By combining the two colourings, every monochromatic component of $G$ has
order at most $k$ and every monochromatic component of $G$ that intersects $C$
is contained in $C$, as required. Now assume that $G$ is 3-connected.

Every 3-connected graph contains a cycle of length at least 4. Thus
$k\geqslant 4$.

If $G$ contains no cycle of length $k$, then apply the induction hypothesis
for $k-1$; thus we may assume that $G$ contains a cycle $Q$ of length $k$. Let
$\mathcal{A}$ be the set of cycles in $G$ of length at least
$\lceil{\tfrac{1}{2}(k-5)}\rceil$. Suppose that a cycle $A\in\mathcal{A}$ is
disjoint from $Q$. Since $G$ is 3-connected, there are three disjoint paths
between $A$ and $Q$. It follows that $G$ contains three cycles with total
length at least $2(|A|+|Q|+3)>3k$. Thus $G$ contains a cycle of length greater
than $k$, which is a contradiction. Hence, every cycle in $\mathcal{A}$
intersects $Q$.

Let $S:=V(Q)\cup C$. As shown above, $G^{\prime}:=G-S$ contains no cycle of
length at least $\lceil{\frac{1}{2}(k-5)}\rceil$. Then $G^{\prime}$ has
circumference at most $\lceil{\frac{1}{2}(k-7)}\rceil$, which is at most
$\lfloor{\tfrac{1}{2}k}\rfloor$, which is at least 2. By induction (with no
precoloured vertices), there is a
$\lfloor{3\log_{2}\lfloor{\frac{1}{2}k}\rfloor}\rfloor$-colouring of
$G^{\prime}$ such that every monochromatic component of $G^{\prime}$ has order
at most $\lfloor{\frac{1}{2}k}\rfloor$. Use a set of colours for $G^{\prime}$
disjoint from the (at most two) preassigned colours for $C$. Use one new
colour for $S\setminus C$, which has size at most $k$. In total, there are at
most
$\lfloor{3\log_{2}\lfloor{\frac{1}{2}k}\rfloor}\rfloor+3\leqslant\lfloor{3\log_{2}k}\rfloor$
colours. Every monochromatic component of $G$ has order at most $k$, and every
monochromatic component of $G$ that intersects $C$ is contained in $C$. ∎

Similar results are obtained for graph classes excluding a fixed path. Let
$P_{k}$ be the path on $k$ vertices. It follows from Lemma 71 that

$\operatorname{\overline{td}}(P_{k})=\operatorname{td}(P_{k})=\lceil{\log_{2}(k+1)}\rceil.$

Let $\mathcal{H}_{k}$ be the class of graphs containing no path of order $k+1$
(or equivalently, with no $P_{k+1}$ minor). Thus Conjecture 62, in the case of
excluded paths, asserts that

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{H}_{k})=\operatorname{td}(P_{k+1})-1=\lceil{\log_{2}(k+2)}\rceil-1.$

Every graph with no $P_{k+1}$-minor has circumference at most $k$. Thus
Theorem 72 implies the following upper bound that is which is within a factor
of 3 of Conjecture 62 for excluded paths.

######  Theorem 74 ([176]).

For every integer $k\geqslant 2$, every graph $G$ with no path of order $k+1$
is $(3\log_{2}k)$-colourable with clustering $k$. Thus

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{H}_{k})\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{H}_{k})\leqslant\lfloor{3\log_{2}k}\rfloor,$

To conclude this section, we show that Theorem 34 determines the defective
choosability of $\mathcal{C}_{k}$ and $\mathcal{P}_{k}$.

First consider $\mathcal{C}_{k}$. Say $s\leqslant t$. Then the circumference
of $K_{s,t}$ equals $2s$. If $s\geqslant\lceil{\frac{k+1}{2}}\rceil$ then
$K_{s,t}$ contains a $(k+1)$-cycle and is not in $\mathcal{C}_{k}$. On the
other hand, if $s\leqslant\lceil{\frac{k+1}{2}}\rceil-1$ then $2s\leqslant k$
and $K_{s,t}\in\mathcal{C}_{k}$. Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{C}_{k})=\lceil{\frac{k+1}{2}}\rceil$.

Now consider $\mathcal{P}_{k}$. Say $t>s$. Then $K_{s,t}$ contains a path
order $2s+1$, and contains no path of order $2s+2$. Thus
$K_{s,t}\in\mathcal{H}_{k}$ if and only if $2s+1\leqslant k$. That is,
$K_{s,t}\not\in\mathcal{H}_{k}$ if and only if $s>\frac{k-1}{2}$. By Theorem
34,
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{H}_{k})=\lfloor{\frac{k+1}{2}}\rfloor$.

##  9 Thickness

The _thickness_ of a graph $G$ is the minimum integer $k$ such that $G$ is the
union of $k$ planar subgraphs; see [179] for a survey. Let $\mathcal{T}_{k}$
be the class of graphs with thickness $k$. Graphs with thickness $k$ have
maximum average degree less than $6k$. Thus
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{T}_{k})\leqslant 6k$. For
$k=2$, which corresponds to the so-called earth-moon problem, it is known that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{T}_{2})\in\\{9,10,11,12\\}$.
For $k\geqslant 3$, complete graphs provide a lower bound of $6k-2$, implying
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}(\mathcal{T}_{k})\in\\{6k-2,6k-1,6k\\}$.
It is an open problem to improve these bounds; see [129].

###  9.1 Defective Colouring

This section studies defective colourings of graphs with given thickness.
Yancey [231] first proposed studying this topic. The results in this section
are due to Ossona de Mendez et al. [185]. Since the maximum average degree is
less than $6k$, Theorem 28 implies that such graphs are $(3k+1)$-choosable
with defect $O(k^{2})$, but gives no result with at most $3k$ colours.

######  Lemma 75 ([185]).

The standard example $S(2k,d)$ has thickness at most $k$.

###### Proof.

We proceed by induction on $k\geqslant 1$. In the base case, $S(2,d)$ is
planar, and thus has thickness 1. Let $G:=S(2k,d)$ for some $k\geqslant 2$.
Let $r$ be the vertex of $G$ such that $G-r$ is the disjoint union of $d+1$
copies of $S(2k-1,d)$. For $i\in[d+1]$, let $v_{i}$ be the vertex of the
$i$-th component $C_{i}$ of $G-r$ such that $C_{i}-v_{i}$ is the disjoint
union of $d+1$ copies of $S(2k-2,d)$. Let
$H:=G-\\{r,v_{1},v_{2},\ldots,v_{d+1}\\}$. Observe that each component of $H$
is isomorphic to $S(2k-2,d)$ and by induction, $H$ has thickness at most
$k-1$. Since $G-E(H)$ consists of $d+1$ copies of $K_{2,d^{\prime}}$ pasted on
$r$ for some $d^{\prime}$, $G-E(H)$ is planar and thus has thickness 1. Hence
$G$ has thickness at most $k$. ∎

Lemmas 75 and 1 imply that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{T}_{k})\geqslant
2k+1$. Ossona de Mendez et al. [185] proved that equality holds. In fact, the
proof works in the following more general setting, implicitly introduced by
Jackson and Ringel [131]. For an integer $g\geqslant 0$, the _$g$ -thickness_
of a graph $G$ is the minimum integer $k$ such that $G$ is the union of $k$
subgraphs each with Euler genus at most $g$. Let $\mathcal{T}^{g}_{k}$ be the
class of graphs with $g$-thickness $k$. As an aside, note that the
$g$-thickness of complete graphs is closely related to bi-embeddings of graphs
[15, 14, 13, 54].

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

For integers $g\geqslant 0$ and $k\geqslant 1$,

$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{T}_{k}^{g})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}^{\ell}(\mathcal{T}_{k}^{g})=2k+1.$

In particular, every graph with $g$-thickness at most $k$ is
$(2k+1)$-choosable with defect $2kg+8k^{2}+2k$.

The lower bound in Theorem 76 follows from Lemma 75. The upper bound follows
from Lemma 5 and the next lemma.

######  Lemma 77 ([185]).

For integers $g\geqslant 0$ and $k\geqslant 1$, every graph with minimum
degree at least $2k+1$ and $g$-thickness at most $k$ has an $(\ell-1)$-light
edge, where $\ell:=2kg+8k^{2}+2k+1$.

###### Proof.

We claim that Lemma 78 below with $\delta=2k+1$ implies the result. Equations
7 and 8 are immediately satisfied. Let
$\beta:=\big{(}(4k-1)(2k+1)+2k(g-1)\big{)}$ and $\gamma:=4k(2k+1)(g-1)$.
Equation 9 requires that $\ell^{2}-\beta\ell-\gamma>0$. The larger root of
$\ell^{2}-\beta\ell-\gamma$ is $\frac{1}{2}(\beta+\sqrt{\beta^{2}+4\gamma})$,
which is at most $\beta+\frac{\gamma}{\beta}$ since
$\beta+\frac{2\alpha}{\beta}>0$. Elementary manipulations show that
$\ell>\beta+\frac{\gamma}{\beta}$. Thus (9) is satisfied. ∎

######  Lemma 78.

Let $G$ be a graph with $n$ vertices, $g$-thickness at most $k$, and minimum
degree at least $\delta$, where

$\displaystyle 6k\geqslant\delta\geqslant 2k+1,$ (7)
$\displaystyle(\delta-2k)\ell>4k\delta,\text{ and}$ (8)
$\displaystyle(\delta-2k)\ell^{2}-\big{(}(4k-1)\delta+2k(g-1)\big{)}\ell-4k(g-1)\delta>0.$
(9)

Then $G$ has an $(\ell-1)$-light edge.

###### Proof.

By Euler’s Formula, $G$ has at most $3k(n+g-2)$ edges, and every spanning
bipartite subgraph has at most $2k(n+g-2)$ edges. Let $X$ be the set of
vertices with degree at most $\ell-1$. Since vertices in $X$ have degree at
least $\delta$ and vertices not in $X$ have degree at least $\ell$,

$\delta|X|+(n-|X|)\ell\leqslant\sum_{v\in V(G)}\deg(v)=2|E(G)|\leqslant
6k(n+g-2).$

Thus

$(\ell-6k)n-6k(g-2)\leqslant(\ell-\delta)|X|.$

Suppose on the contrary that $X$ is a stable set in $G$. Let $G^{\prime}$ be
the spanning bipartite subgraph of $G$ consisting of all edges between $X$ and
$V(G)\setminus X$. Since each of the at least $\delta$ edges incident with
each vertex in $X$ are in $G^{\prime}$,

$\delta|X|\leqslant|E(G^{\prime})|\leqslant 2k(n+g-2).$

Since $\ell>\frac{4k}{\delta-2k}\delta>\delta$ (hence $\ell-\delta>0$) and
$\delta\geqslant 0$,

$\displaystyle\delta(\ell-6k)n-6k(g-2)\delta$
$\displaystyle\leqslant\delta(\ell-\delta)|X|\leqslant(\ell-\delta)(2k)(n+g-2)$
$\displaystyle\Longrightarrow$
$\displaystyle\big{(}\delta(\ell-6k)-2k(\ell-\delta)\big{)}n$
$\displaystyle\leqslant(\ell-\delta)2k(g-2)+6k(g-2)\delta$
$\displaystyle\Longrightarrow$
$\displaystyle\big{(}(\delta-2k)\ell-4k\delta\big{)}n$ $\displaystyle\leqslant
2k(g-2)\ell+4k(g-2)\delta.$

If $n\leqslant\ell$ then every edge is $(\ell-1)$-light. Now assume that
$n\geqslant\ell+1$. Since $(\delta-2k)\ell-4k\delta>0$,

$\big{(}(\delta-2k)\ell-4k\delta\big{)}(\ell+1)\leqslant
2k(g-2)\ell+4k(g-2)\delta.$

Thus

$(\delta-2k)\ell^{2}-\big{(}(4k-1)\delta+2k(g-1)\big{)}\ell-4k(g-1)\delta\leqslant
0,$

which is a contradiction. Thus $X$ is not a stable set. Hence $G$ contains an
$(\ell-1)$-light edge. ∎

Lemma 78 with $k=1$ and $\ell=2g+13$ implies that every graph $G$ with minimum
degree at least $3$ and Euler genus $g$ has a $(2g+12)$-light edge. Note that
this bound is within $+10$ of being tight since $K_{3,2g+2}$ has minimum
degree 3, embeds in a surface of Euler genus $g$, and every edge has an
endpoint of degree $2g+2$. More precise results, which are typically proved by
discharging with respect to an embedding, are known [134, 130, 35]. Theorem 76
then implies that every graph with Euler genus $g$ is $3$-choosable with
defect $2g+10$. As mentioned in Section 3.4, this result with a better degree
bound was proved by Woodall [228]; also see [59]. The utility of Lemma 78 is
that it applies for $k>1$.

The case $g=0$ and $k=2$ relates to the famous earth–moon problem [8, 108,
129, 195, 131], which asks for the maximum chromatic number of graphs with
thickness $2$. The answer is known to be in $\\{9,10,11,12\\}$. Since the
maximum average degree of every graph $G$ with thickness 2 is less than $12$,
the result of Havet and Sereni [119] mentioned in Section 5 implies that $G$
is $k$-choosable with defect $d$, for
$(k,d)\in\\{(7,18),(8,9),(9,5),(10,3),(11,2)\\}$. This result gives no bound
with at most 6 colours. On the other hand, Theorem 76 says that the class of
graphs with thickness 2 has defective chromatic number and defective choice
number equal to $5$. In particular, the method shows that every graph $G$ with
thickness 2 is $k$-choosable with defect $d$, for
$(k,d)\in\\{(5,36),(6,19),(7,12),(8,9),(9,6),(10,4),(11,2)\\}$. This
11-colouring result, which is also implied by the result of Havet and Sereni
[119], is close to the conjecture that graphs with thickness 2 are
11-colourable. Improving these degree bounds provides an approach for
attacking the earth–moon problem.

###  9.2 Clustered Colouring

Consider the clustered chromatic number of $\mathcal{T}^{g}_{k}$. We have the
following upper bound.

######  Proposition 79.

For all integers $g\geqslant 0$ and $k\geqslant 1$, every graph $G$ with
$g$-thickness at most $k$ is $(6k+1)$-choosable with clustering
$\max\\{g,1\\}$.

###### Proof.

We proceed by induction on $|V(G)|$. Let $L$ be a $(6k+1)$-list assignment for
$G$. In the base case, the claim is trivial if $|V(G)|=0$. Now assume that
$|V(G)|\geqslant 1$.

First suppose that $|V(G)|\leqslant 6kg$. Thus $g\geqslant 1$. Let $v$ be any
vertex of $G$. By induction, $G-v$ is $L$-colourable with clustering $g$.
Since $|L(v)|\geqslant 6g$ and $|V(G-v)|<6kg$, some colour $c\in L(v)$ is
assigned to at most $g-1$ vertices in $G-v$. Colour $v$ by $c$. Thus $G$ is
$L$-coloured with clustering $g$.

Now assume that $|V(G)|>6kg$. Every graph with $g$-thickness at most $k$ and
more than $6kg$ vertices has a vertex $v$ of degree at most $6k$, since
$|E(G)|<3k(|V(G)|+g)\leqslant(3k+\frac{1}{2})|V(G)|$, implying $G$ has average
degree less than $6k+1$. By induction, $G-v$ is $(6k+1)$-choosable with
clustering $\max\\{g,1\\}$. Since $|L(v)|\geqslant 6k+1$ and $\deg(v)\leqslant
6k$, some colour $c\in L(v)$ is not assigned to any neighbour of $v$. Colour
$v$ by $c$. Thus $v$ is in a singleton monochromatic component, and $G$ is
$L$-coloured with clustering $\max\\{g,1\\}$. ∎

Since $\overline{S}(3,c)$ is planar, an analogous proof to that of Lemma 75
shows that $\overline{S}(2k+1,c)$ has thickness at most $k$. By Lemmas 2 and
79,

$2k+2\leqslant\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{T}^{g}_{k})\leqslant
6k+1.$

Closing this gap is an interesting problem because the existing methods say
nothing for graphs with given thickness. For example, as illustrated in Figure
13, the 1-subdivision of $K_{n}$ has thickness 2. Thus thickness 2 graphs have
unbounded $\nabla$. Similarly, Lemma 13 is not applicable since graphs with
thickness 2 do not have sublinear balanced separators. Indeed, Dujmović et al.
[82] constructed ‘expander’ graphs with thickness 2, bounded degree, and with
no $o(n)$ balanced separators. Returning to the earth-moon problem, it is open
whether thickness 2 graphs are 11-colourable with bounded clustering.

Figure 13: The 1-subdivision of $K_{n}$ has thickness 2.

##  10 General Setting

Consider a graph parameter $f$. Several authors have studied colourings of
graphs such that $f$ is bounded for each monochromatic subgraph, or
equivalently each monochromatic subgraph satisfies a particular property; see
[103, 51, 138, 53, 217, 71] for example. For a graph class $\mathcal{G}$,
define $\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{f}(\mathcal{G})$ to be the
minimum integer $k$ such that for some $c$, every graph $G\in\mathcal{G}$ has
a $k$-colouring such that $f(H)\leqslant c$ for each monochromatic subgraph
$H$ of $G$. This definition incorporates the clustered and defective chromatic
numbers. In particular, if $f(H)$ is the maximum number of vertices in a
connected component of $H$, then
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{f}(\mathcal{G})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\star}(\mathcal{G})$,
and if $f(H)=\Delta(H)$ then
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{f}(\mathcal{G})=\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\Delta}(\mathcal{G})$.
There are many choices for $f$ and $\mathcal{G}$.

First consider when $f$ is the treewidth. Recall that DeVos et al. [72] proved
that
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\operatorname{tw}}(\mathcal{G})\leqslant
2$ for every minor-closed class $\mathcal{G}$. Bounded degree classes and
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\operatorname{tw}}(\mathcal{D}_{\Delta})$
look interesting. In particular, what is the maximum integer $\Delta$ such
that every graph with maximum degree $\Delta$ is 2-colourable with bounded
monochromatic treewidth? The answer is at least 5 since every graph with
maximum degree 5 is 2-colourable with bounded clustering [120]. The answer is
at most 25 since Berger et al. [25] proved that for every 2-colouring of the
$n\times n\times n$ grid with diagonals (which has maximum degree 26), there
is a monochromatic subgraph with unbounded treewidth (as
$n\rightarrow\infty$). This upper bound is probably easily improved by
eliminating some of the diagonals in the 3-dimensional grid. Can the lower
bound be improved? In particular, does every graph with maximum degree 6 have
a 2-colouring with bounded monochromatic treewidth?

Let $\eta(H)$ be the maximum integer $t$ such that $K_{t}$ is a minor of $H$,
sometimes called the _Hadwiger number_ of $H$. For example, $\eta(H)\leqslant
1$ if and only if $H$ is edgeless, and $\eta(H)\leqslant 2$ if and only if $H$
is a forest. Ding et al. [76] conjectured that for every graph $G$ and integer
$k\in[1,\eta(G)]$, $G$ is $k$-colourable with $\eta(H)\leqslant\eta(G)-k+1$
for each monochromatic subgraph $H$ of $G$. The case $k=\eta(G)$ is Hadwiger’s
Conjecture. Alternately 2-colouring the layers in a BFS layering proves this
conjecture for $k=2$. Gonçalves [114] proved it for $k=3$.
$\raisebox{1.55pt}{\scalebox{1.2}{$\chi$}}_{\eta}(\mathcal{D}_{\Delta})$ also
looks interesting.

### Acknowledgements

Many thanks to Jan van den Heuvel, Sergey Norin, Alex Scott, Paul Seymour,
Patrice Ossona de Mendez, Bojan Mohar, Sang-il Oum and Bruce Reed with whom I
have collaborated on defective and clustered colourings. This survey has also
greatly benefited from insightful comments from Zdeněk Dvořák, Louis Esperet,
Jacob Fox, Frédéric Havet, Gwenaël Joret, Chun-Hung Liu and Tibor Szabó, for
which I am extremely grateful. I am particularly thankful to Frédéric Havet
for allowing his unpublished proof of Lemma 29 to be included. Many thanks to
the referees for detailed and insightful comments that have greatly improved
the paper.

## References

  * Abu-Khzam and Langston [2003] Faisal N. Abu-Khzam and Michael A. Langston.  Graph coloring and the immersion order.  In _Proc. International Conference on Computing and Combinatorics (COCOON ’03)_ , vol. 2697 of _Lecture Notes in Comput. Sci._ , pp. 394–403. Springer, 2003.  doi:10.1007/3-540-45071-8“˙40.  MR: 2063516.
  * Achuthan et al. [1996] Nirmala Achuthan, N. R. Achuthan, and M. Simanihuruk.  On defective colourings of complementary graphs.  _Australas. J. Combin._ , 13:175–196, 1996.  MR: 1383416.
  * Achuthan et al. [2011a] Nirmala Achuthan, N. R. Achuthan, and M. Simanihuruk.  The Nordhaus-Gaddum problem for the $k$-defective chromatic number of a $P_{4}$-free graph.  _Australas. J. Combin._ , 49:3–13, 2011a.  MR: 2790956.
  * Achuthan et al. [2011b] Nirmala Achuthan, N. R. Achuthan, and M. Simanihuruk.  On minimal triangle-free graphs with prescribed $k$-defective chromatic number.  _Discrete Math._ , 311(13):1119–1127, 2011b.  doi:10.1016/j.disc.2010.08.013.  MR: 2793222.
  * Addario-Berry et al. [2010] Louigi Addario-Berry, Louis Esperet, Ross J. Kang, Colin J. H. McDiarmid, and Alexandre Pinlou.  Acyclic improper colourings of graphs with bounded maximum degree.  _Discrete Math._ , 310(2):223–229, 2010.  doi:10.1016/j.disc.2008.09.009.  MR: 2563038.
  * Akdemir and Ekim [2015] Ahu Akdemir and Tı naz Ekim.  Advances on defective parameters in graphs.  _Discrete Optim._ , 16:62–69, 2015.  doi:10.1016/j.disopt.2015.01.002.  MR: 3327669.
  * Albar and Gonçalves [2017] Boris Albar and Daniel Gonçalves.  On triangles in ${K}_{r}$-minor free graphs.  _J. Graph Theory_ , 2017.  doi:10.1002/jgt.22203.  arXiv: 1304.5468.
  * Albertson et al. [2011] Michael O. Albertson, Debra L. Boutin, and Ellen Gethner.  More results on $r$-inflated graphs: arboricity, thickness, chromatic number and fractional chromatic number.  _Ars Math. Contemp._ , 4(1):5–24, 2011.  MR: 2729287.
  * Aleksandrov and Djidjev [1996] Lyudmil G. Aleksandrov and Hristo N. Djidjev.  Linear algorithms for partitioning embedded graphs of bounded genus.  _SIAM J. Discrete Math._ , 9(1):129–150, 1996.  doi:10.1137/S0895480194272183.  MR: 1375420.
  * Alon [2000] Noga Alon.  Degrees and choice numbers.  _Random Structures & Algorithms_, 16(4):364–368, 2000.  doi: 10.1002/1098-2418(200007)16:4$<$3C364::AID-RSA5$>$3E3.0.CO;2-0 MR: 1761581.
  * Alon et al. [2003] Noga Alon, Guoli Ding, Bogdan Oporowski, and Dirk Vertigan.  Partitioning into graphs with only small components.  _J. Combin. Theory Ser. B_ , 87(2):231–243, 2003.  doi:10.1016/S0095-8956(02)00006-0.  MR: 1957474.
  * Alon et al. [1990] Noga Alon, Paul Seymour, and Robin Thomas.  A separator theorem for nonplanar graphs.  _J. Amer. Math. Soc._ , 3(4):801–808, 1990.  doi:10.2307/1990903.  MR: 1065053.
  * Anderson [1979] Ian Anderson.  Infinite families of biembedding numbers.  _J. Graph Theory_ , 3(3):263–268, 1979.  doi:10.1002/jgt.3190030309.  MR: 542548.
  * Anderson [1982] Ian Anderson.  Triples, current graphs and biembeddings.  _Aequationes Math._ , 24(2-3):230–242, 1982.  doi:10.1007/BF02193046.  MR: 706972.
  * Anderson and Cook [1974] Ian Anderson and Roger J. Cook.  Bi-embeddings of graphs.  _Glasgow Math. J._ , 15:162–165, 1974.  doi:10.1017/S0017089500002354.  MR: 0366714.
  * Andrews and Jacobson [1985] James A. Andrews and Michael S. Jacobson.  On a generalization of chromatic number.  In _Proc. 16th Southeastern International Conference on Combinatorics, Graph Theory and Computing_ , vol. 47 of _Congr. Numer._ , pp. 33–48. 1985.  MR: 830668.
  * Andrews and Jacobson [1987] James A. Andrews and Michael S. Jacobson.  On a generalization of chromatic number and two kinds of Ramsey numbers.  _Ars Combin._ , 23:97–102, 1987.  MR: 886944.
  * Angelini et al. [2017] Patrizio Angelini, Michael A. Bekos, Felice De Luca, Walter Didimo, Michael Kaufmann, Stephen G. Kobourov, Fabrizio Montecchiani, Chrysanthi N. Raftopoulou, Vincenzo Roselli, and Antonios Symvonis.  Vertex-coloring with defects.  _J. Graph Algorithms Appl._ , 21(3):313–340, 2017.  doi:10.7155/jgaa.00418.  MR: 3621539.
  * Appel and Haken [1989] Kenneth Appel and Wolfgang Haken.  _Every planar map is four colorable_ , vol. 98 of _Contemporary Mathematics_.  American Mathematical Society, 1989.  doi:10.1090/conm/098.  MR: 1025335.
  * Araujo et al. [2012] Julio Araujo, Jean-Claude Bermond, Frédéric Giroire, Frédéric Havet, Dorian Mazauric, and Remigiusz Modrzejewski.  Weighted improper colouring.  _J. Discrete Algorithms_ , 16:53–66, 2012.  doi:10.1016/j.jda.2012.07.001.  MR: 2960344.
  * Archdeacon [1987] Dan Archdeacon.  A note on defective colorings of graphs in surfaces.  _J. Graph Theory_ , 11(4):517–519, 1987.  doi:10.1002/jgt.3190110408.  MR: 917198.
  * Archetti et al. [2015] Claudia Archetti, Nicola Bianchessi, Alain Hertz, Adrien Colombet, and François Gagnon.  Directed weighted improper coloring for cellular channel allocation.  _Discrete Appl. Math._ , 182:46–60, 2015.  doi:10.1016/j.dam.2013.11.018.  MR: 3301934.
  * Barát et al. [2011] János Barát, Gwenaël Joret, and David R. Wood.  Disproof of the list Hadwiger conjecture.  _Electron. J. Combin._ , 18(1):#P232, 2011.  http://www.combinatorics.org/v18i1p232.  MR: 2861411.
  * Belmonte et al. [2017] Rémy Belmonte, Michael Lampis, and Valia Mitsou.  Defective coloring on classes of perfect graphs.  In Gerhard J. Woeginger Hans L. Bodlaender, ed., _Graph-Theoretic Concepts in Computer Science (WG ’17)_ , vol. 10520 of _Lecture Notes in Comput. Sci._ 2017\.  doi:10.1007/978-3-319-68705-6“˙9.  arXiv: 1702.08903.
  * Berger et al. [2017] Eli Berger, Zdeněk Dvořák, and Sergey Norin.  Treewidth of grid subsets.  _Combinatorica_ , 2017.  doi:10.1007/s00493-017-3548-5.
  * Berke [2008] Robert Berke.  _Coloring and Transversals of Graphs_.  Ph.D. thesis, ETH Zurich, 2008.  Diss. ETH No. 17797.
  * Berke and Szabó [2007] Robert Berke and Tibor Szabó.  Relaxed two-coloring of cubic graphs.  _J. Combin. Theory Ser. B_ , 97(4):652–668, 2007.  doi:10.1016/j.jctb.2006.12.001.  MR: 2325804.
  * Berke and Szabó [2009] Robert Berke and Tibor Szabó.  Deciding relaxed two-colourability: a hardness jump.  _Combin. Probab. Comput._ , 18(1-2):53–81, 2009.  doi:10.1017/S0963548309009663.  MR: 2497374.
  * Bernardi [1987] Claudio Bernardi.  On a theorem about vertex colorings of graphs.  _Discrete Math._ , 64(1):95–96, 1987.  doi:10.1016/0012-365X(87)90243-3.  MR: 882615.
  * Bernhart and Kainen [1979] Frank R. Bernhart and Paul C. Kainen.  The book thickness of a graph.  _J. Combin. Theory Ser. B_ , 27(3):320–331, 1979.  doi:10.1016/0095-8956(79)90021-2.  MR: 554297.
  * Blain et al. [2007] Paul Blain, Garry Bowlin, Thomas Fleming, Joel Foisy, Jacob Hendricks, and Jason Lacombe.  Some results on intrinsically knotted graphs.  _J. Knot Theory Ramifications_ , 16(6):749–760, 2007.  doi:10.1142/S021821650700552X.  MR: 2341314.
  * Bodlaender [1993] Hans L. Bodlaender.  A tourist guide through treewidth.  _Acta Cybernet._ , 11(1-2):1–21, 1993.
  * Bodlaender [1998] Hans L. Bodlaender.  A partial $k$-arboretum of graphs with bounded treewidth.  _Theoret. Comput. Sci._ , 209(1-2):1–45, 1998.  doi:10.1016/S0304-3975(97)00228-4.
  * Boiron et al. [1999] Pierre Boiron, Éric Sopena, and Laurence Vignal.  Acyclic improper colorings of graphs.  _J. Graph Theory_ , 32(1):97–107, 1999.  doi: 10.1002/(SICI)1097-0118(199909)32:1$<$97::AID-JGT9$>$3.3.CO;2-F.  MR: 1704140.
  * Borodin [1989] Oleg V. Borodin.  On the total coloring of planar graphs.  _J. Reine Angew. Math._ , 394:180–185, 1989.  doi:10.1515/crll.1989.394.180.  MR: 977440.
  * Borodin [2013] Oleg V. Borodin.  Colorings of plane graphs: A survey.  _Discrete Math._ , 313(4):517–539, 2013.  doi:10.1016/j.disc.2012.11.011.  MR: 3004485.
  * Borodin and Ivanova [2009a] Oleg V. Borodin and Anna O. Ivanova.  Almost proper 2-colorings of vertices of sparse graphs.  _Diskretn. Anal. Issled. Oper._ , 16(2):16–20, 98, 2009a.  doi:10.1134/S1990478910010047.  MR: 2574306.
  * Borodin and Ivanova [2009b] Oleg V. Borodin and Anna O. Ivanova.  Partitioning sparse planar graphs into two subgraphs of lower degree.  _Sib. Èlektron. Mat. Izv._ , 6:13–16, 2009b.  http://semr.math.nsc.ru/v6.html.  MR: 2586676.
  * Borodin and Ivanova [2011] Oleg V. Borodin and Anna O. Ivanova.  List strong linear 2-arboricity of sparse graphs.  _J. Graph Theory_ , 67(2):83–90, 2011.  doi:10.1002/jgt.20516.  MR: 2828410.
  * Borodin et al. [2010] Oleg V. Borodin, Anna O. Ivanova, Mickaël Montassier, Pascal Ochem, and André Raspaud.  Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most $k$.  _J. Graph Theory_ , 65(2):83–93, 2010.  doi:10.1002/jgt.20467.  MR: 2724489.
  * Borodin et al. [2011] Oleg V. Borodin, Anna O. Ivanova, Mickaël Montassier, and André Raspaud.  $(k,j)$-coloring of sparse graphs.  _Discrete Appl. Math._ , 159(17):1947–1953, 2011.  doi:10.1016/j.dam.2011.06.021.  MR: 2832323.
  * Borodin et al. [2012] Oleg V. Borodin, Anna O. Ivanova, Mickaël Montassier, and André Raspaud.  $(k,1)$-coloring of sparse graphs.  _Discrete Math._ , 312(6):1128–1135, 2012.  doi:10.1016/j.disc.2011.11.031.  MR: 2876359.
  * Borodin and Kostochka [1977] Oleg V. Borodin and Alexandr V. Kostochka.  On an upper bound of a graph’s chromatic number, depending on the graph’s degree and density.  _J. Combinatorial Theory Ser. B_ , 23(2-3):247–250, 1977.  doi:10.1016/0095-8956(77)90037-5.  MR: 0469803.
  * Borodin and Kostochka [2011a] Oleg V. Borodin and Alexandr V. Kostochka.  Vertex decompositions of sparse graphs into an independent set and a subgraph of maximum degree at most 1.  _Sibirsk. Mat. Zh._ , 52(5):1004–1010, 2011a.  doi:10.1134/S0037446611050041.  MR: 2908122.
  * Borodin and Kostochka [2011b] Oleg V. Borodin and Alexandr V. Kostochka.  Vertex decompositions of sparse graphs into an independent vertex set and a subgraph of maximum degree at most 1.  _Sib. Math. J._ , 52:796–801, 2011b.  doi:10.1134/S0037446611050041.  MR: 2908122.
  * Borodin and Kostochka [2014] Oleg V. Borodin and Alexandr V. Kostochka.  Defective 2-colorings of sparse graphs.  _J. Combin. Theory Ser. B_ , 104:72–80, 2014.  doi:10.1016/j.jctb.2013.10.002.  MR: 3132745.
  * Borodin et al. [2013] Oleg V. Borodin, Alexandr V. Kostochka, and Matthew Yancey.  On 1-improper 2-coloring of sparse graphs.  _Discrete Math._ , 313(22):2638–2649, 2013.  doi:10.1016/j.disc.2013.07.014.  MR: 3095439.
  * Borodin and Sanders [1994] Oleg V. Borodin and Daniel P. Sanders.  On light edges and triangles in planar graphs of minimum degree five.  _Math. Nachr._ , 170:19–24, 1994.  doi:10.1002/mana.19941700103.  MR: 1302363.
  * Borowiecki et al. [2011] Mieczysław Borowiecki, Katarzyna Jesse-Józefczyk, and Elżbieta Sidorowicz.  The complexity of some acyclic improper colourings.  _Discrete Math._ , 311(8-9):732–737, 2011.  doi:10.1016/j.disc.2011.01.023.  MR: 2774229.
  * Bose et al. [2004] Prosenjit Bose, Michiel Smid, and David R. Wood.  Light edges in degree-constrained graphs.  _Discrete Math._ , 282(1–3):35–41, 2004.  doi:10.1016/j.disc.2003.12.003.  MR: 2059504.
  * Broere et al. [2002] Izak Broere, Samantha Dorfling, and Elizabeth Jonck.  Generalized chromatic numbers and additive hereditary properties of graphs.  _Discuss. Math. Graph Theory_ , 22(2):259–270, 2002.  doi:10.7151/dmgt.1174.  MR: 1961207.
  * Broersma et al. [2006] Hajo Broersma, Fedor V. Fomin, Jan Kratochvíl, and Gerhard J. Woeginger.  Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult.  _Algorithmica_ , 44(4):343–361, 2006.  doi:10.1007/s00453-005-1176-8.  MR: 2212055.
  * Burr and Jacobson [1990] Stefan A. Burr and Michael S. Jacobson.  On inequalities involving vertex-partition parameters of graphs.  In _Proc. 20th Southeastern Conference on Combinatorics, Graph Theory, and Computing_ , vol. 70, pp. 159–170. 1990.  MR: 1041597.
  * Cabaniss [1990] Sharon Cabaniss.  A survey of biembeddings of graphs.  In _Proc. 20th Southeastern Conference on Combinatorics, Graph Theory, and Computing_ , vol. 70 of _Congr. Numer._ , pp. 171–180. 1990.  MR: 1041598.
  * Chappell and Gimbel [2017] Glenn G. Chappell and John Gimbel.  On subgraphs without large components.  _Math. Bohem._ , 142(1):85–111, 2017.  doi:10.21136/MB.2017.0013-14.  MR: 3619989.
  * Chen et al. [2016] Ming Chen, Yingqian Wang, Peipei Liu, and Jinghan Xu.  Planar graphs without cycles of length 4 or 5 are $(2,0,0)$-colorable.  _Discrete Math._ , 339(2):886–905, 2016.  doi:10.1016/j.disc.2015.10.029.  MR: 3431403.
  * Chen et al. [2008] Yongzhu Chen, Weiyi Zhu, and Weifan Wang.  Improper choosability of graphs of nonnegative characteristic.  _Comput. Math. Appl._ , 56(8):2073–2078, 2008.  doi:10.1016/j.camwa.2008.03.036.  MR: 2466712.
  * Choi et al. [2017] Hojin Choi, Ilkyoo Choi, Jisu Jeong, and Geewon Suh.  $(1,k)$-coloring of graphs with girth at least five on a surface.  _J. Graph Theory_ , 84(4):521–535, 2017.  doi:10.1002/jgt.22039.  MR: 3623392.
  * Choi and Esperet [2016] Ilkyoo Choi and Louis Esperet.  Improper coloring of graphs on surfaces, 2016.  arXiv: 1603.02841.
  * Choi and Raspaud [2015] Ilkyoo Choi and André Raspaud.  Planar graphs with girth at least $5$ are $(3,5)$-colorable.  _Discrete Math._ , 338(4):661–667, 2015.  doi:10.1016/j.disc.2014.11.012.  MR: 3300755.
  * Colin de Verdière [1990] Yves Colin de Verdière.  Sur un nouvel invariant des graphes et un critère de planarité.  _J. Combin. Theory Ser. B_ , 50(1):11–21, 1990.  doi:10.1016/0095-8956(90)90093-F.  MR: 1070462.
  * Colin de Verdière [1993] Yves Colin de Verdière.  On a new graph invariant and a criterion for planarity.  In _Graph structure theory_ , vol. 147 of _Contemp. Math._ , pp. 137–147. Amer. Math. Soc., 1993.  doi:10.1090/conm/147/01168.  MR: 1224700.
  * Conway and Gordon [1983] John H. Conway and Cameron McA. Gordon.  Knots and links in spatial graphs.  _J. Graph Theory_ , 7:445–453, 1983.  doi:10.1002/jgt.3190070410.  MR: 722061.
  * Corrêa et al. [2009] Ricardo Corrêa, Frédéric Havet, and Jean-Sébastien Sereni.  About a Brooks-type theorem for improper colouring.  _Australas. J. Combin._ , 43:219–230, 2009.  https://ajc.maths.uq.edu.au/pdf/43/ajc_v43_p219.pdf.  MR: 2489421.
  * Cowen et al. [1997] Lenore Cowen, Wayne Goddard, and C. Esther Jesurum.  Defective coloring revisited.  _J. Graph Theory_ , 24(3):205–219, 1997.  doi: 10.1002/(SICI)1097-0118(199703)24:3$<$205::AID-JGT2$>$3.0.CO;2-T.  MR: 1431666.
  * Cowen et al. [1986] Lenore J. Cowen, Robert Cowen, and Douglas R. Woodall.  Defective colorings of graphs in surfaces: partitions into subgraphs of bounded valency.  _J. Graph Theory_ , 10(2):187–195, 1986.  doi:10.1002/jgt.3190100207.  MR: 890224.
  * Cranston and Rabern [2015] Daniel W. Cranston and Landon Rabern.  Brooks’ theorem and beyond.  _J. Graph Theory_ , 80(3):199–225, 2015.  doi:10.1002/jgt.21847.  MR: 3403726.
  * Cushing and Kierstead [2010] William Cushing and Hal A. Kierstead.  Planar graphs are 1-relaxed, 4-choosable.  _European J. Combin._ , 31(5):1385–1397, 2010.  doi:10.1016/j.ejc.2009.11.013.  MR: 2644426.
  * Dai et al. [2017] Lifeng Dai, Yingqian Wang, and Jinghan Xu.  Every planar graph without cycles of length 4 or 9 is $(1,1,0)$-colorable.  _Discrete Math._ , 340(9):2108–2122, 2017.  doi:10.1016/j.disc.2017.04.006.  MR: 3665065.
  * de Klerk et al. [2014] Etienne de Klerk, Dmitrii V. Pasechnik, and Gelasio Salazar.  Book drawings of complete bipartite graphs.  _Discrete Appl. Math._ , 167:80–93, 2014.  doi:10.1016/j.dam.2013.11.001.  MR: 3166108.
  * Deuber and Zhu [1998] Walter A. Deuber and Xuding Zhu.  Relaxed coloring of a graph.  _Graphs and Combinatorics_ , 14(2):121–130, 1998.  doi:10.1007/s003730050020.  MR: 1628117.
  * DeVos et al. [2004] Matt DeVos, Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, Bruce Reed, Paul Seymour, and Dirk Vertigan.  Excluding any graph as a minor allows a low tree-width 2-coloring.  _J. Combin. Theory Ser. B_ , 91(1):25–41, 2004.  doi:10.1016/j.jctb.2003.09.001.  MR: 2047529.
  * DeVos et al. [2014] Matt DeVos, Zdeněk Dvořák, Jacob Fox, Jessica McDonald, Bojan Mohar, and Diego Scheide.  A minimum degree condition forcing complete graph immersion.  _Combinatorica_ , 34(3):279–298, 2014.  doi:10.1007/s00493-014-2806-z.  MR: 3223965.
  * DeVos et al. [2013] Matt DeVos, Jessica McDonald, Bojan Mohar, and Diego Scheide.  A note on forbidding clique immersions.  _Electron. J. Combin._ , 20(3):#P55, 2013.  http://www.combinatorics.org/v20i3p55.  MR: 3118963.
  * Ding and Oporowski [1995] Guoli Ding and Bogdan Oporowski.  Some results on tree decomposition of graphs.  _J. Graph Theory_ , 20(4):481–499, 1995.  doi:10.1002/jgt.3190200412.  MR: 1358539.
  * Ding et al. [2000] Guoli Ding, Bogdan Oporowski, Daniel P. Sanders, and Dirk Vertigan.  Surfaces, tree-width, clique-minors, and partitions.  _J. Combin. Theory Ser. B_ , 79(2):221–246, 2000.  doi:10.1006/jctb.2000.1962.  MR: 1769192.
  * Dirac [1952] Gabriel A. Dirac.  A property of $4$-chromatic graphs and some remarks on critical graphs.  _J. London Math. Soc._ , 27:85–92, 1952.  doi:10.1112/jlms/s1-27.1.85.  MR: 0045371.
  * Djidjev [1987] Hristo N. Djidjev.  On the constants of separator theorems.  _C. R. Acad. Bulgare Sci._ , 40(10):31–34, 1987.  MR: 940049.
  * Dorbec et al. [2014] Paul Dorbec, Tomáš Kaiser, Mickaël Montassier, and André Raspaud.  Limits of near-coloring of sparse graphs.  _J. Graph Theory_ , 75(2):191–202, 2014.  doi:10.1002/jgt.21731.  MR: 3150573.
  * Dujmović et al. [2017] Vida Dujmović, David Eppstein, and David R. Wood.  Structure of graphs with locally restricted crossings.  _SIAM J. Disc. Math._ , 31(2):805–824, 2017.  doi:10.1137/16M1062879.  MR: 3639571.
  * Dujmović et al. [2017] Vida Dujmović, Pat Morin, and David R. Wood.  Layered separators in minor-closed graph classes with applications.  _J. Combin. Theory Ser. B_ , 127:111–147, 2017.  doi:10.1016/j.jctb.2017.05.006.  MR: 3704658.
  * Dujmović et al. [2016] Vida Dujmović, Anastasios Sidiropoulos, and David R. Wood.  Layouts of expander graphs.  _Chicago J. Theoret. Comput. Sci._ , 2016(1), 2016.  doi:10.4086/cjtcs.2016.001.  MR: 3457464.
  * Dujmović and Wood [2004] Vida Dujmović and David R. Wood.  On linear layouts of graphs.  _Discrete Math. Theor. Comput. Sci._ , 6(2):339–358, 2004.  http://dmtcs.episciences.org/317.  MR: 2081479.
  * Dvořák and Norin [2017] Zdeněk Dvořák and Sergey Norin.  Islands in minor-closed classes. I. Bounded treewidth and separators.  2017\.  arXiv: 1710.02727.
  * Dvořák and Wollan [2016] Zdeněk Dvořák and Paul Wollan.  A structure theorem for strong immersions.  _J. Graph Theory_ , 83(2):152–163, 2016.  doi:10.1002/jgt.21990.  MR: 3539094.
  * Eaton and Hull [1999] Nancy Eaton and Thomas Hull.  Defective list colorings of planar graphs.  _Bull. Inst. Combin. Appl_ , 25:79–87, 1999.  MR: 1668108.
  * Edwards et al. [2015] Katherine Edwards, Dong Yeap Kang, Jaehoon Kim, Sang-il Oum, and Paul Seymour.  A relative of Hadwiger’s conjecture.  _SIAM J. Discrete Math._ , 29(4):2385–2388, 2015.  doi:10.1137/141002177.  MR: 3432847.
  * Edwards and Farr [2001] Keith Edwards and Graham Farr.  Fragmentability of graphs.  _J. Comb. Theory, Ser. B_ , 82(1):30–37, 2001.  doi:10.1006/jctb.2000.2018.  MR: 1828433.
  * Edwards and Farr [2005] Keith Edwards and Graham Farr.  On monochromatic component size for improper colourings.  _Discrete Applied Math._ , 148(1):89–105, 2005.  doi:10.1016/j.dam.2004.10.005.  MR: 2132063.
  * Edwards and Farr [2013] Keith Edwards and Graham Farr.  Graph fragmentability.  In _Topics in structural graph theory_ , vol. 147 of _Encyclopedia Math. Appl._ , pp. 203–218. Cambridge Univ. Press, 2013.  MR: 3026762.
  * Edwards and McDiarmid [1994] Keith Edwards and Colin McDiarmid.  New upper bounds on harmonious colorings.  _J. Graph Theory_ , 18(3):257–267, 1994.  doi:10.1002/jgt.3190180305.  MR: 1268774.
  * Enomoto et al. [1999] Hikoe Enomoto, Miki Shimabara Miyauchi, and Katsuhiro Ota.  Lower bounds for the number of edge-crossings over the spine in a topological book embedding of a graph.  _Discrete Appl. Math._ , 92(2-3):149–155, 1999.  doi:10.1016/S0166-218X(99)00044-X.  MR: 1697548.
  * Eppstein [2003] David Eppstein.  Dynamic generators of topologically embedded graphs.  In _Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’03, pp. 599–608. SIAM, 2003.  http://dl.acm.org/citation.cfm?id=644108.644208.  MR: 1974971.
  * Erdős and Sachs [1963] Paul Erdős and Horst Sachs.  Reguläre Graphen gegebener Taillenweite mit minimaler Knotenzahl.  _Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe_ , 12:251–257, 1963.
  * Erdős [1959] Paul Erdős.  Graph theory and probability.  _Canad. J. Math._ , 11:34–38, 1959.  doi:10.4153/CJM-1959-003-9.  MR: 0102081.
  * Erdős and Lovász [1975] Paul Erdős and László Lovász.  Problems and results on $3$-chromatic hypergraphs and some related questions.  In _Infinite and Finite Sets_ , vol. 10 of _Colloq. Math. Soc. János Bolyai_ , pp. 609–627. North-Holland, 1975.  https://www.renyi.hu/~p_erdos/1975-34.pdf.  MR: 0382050.
  * Esperet and Joret [2014] Louis Esperet and Gwenaël Joret.  Colouring planar graphs with three colours and no large monochromatic components.  _Combinatorics, Probability & Computing_, 23(4):551–570, 2014\.  doi:10.1017/S0963548314000170.  MR: 3217360.
  * Esperet and Ochem [2016] Louis Esperet and Pascal Ochem.  Islands in graphs on surfaces.  _SIAM J. Discrete Math._ , 30(1):206–219, 2016.  doi:10.1137/140957883.  MR: 3455135.
  * Farkasová and Soták [2015] Zuzana Farkasová and Roman Soták.  Fractional and circular 1-defective colorings of outerplanar graphs.  _Australas. J. Combin._ , 63:1–11, 2015.  MR: 3385814.
  * Fiedorowicz and Sidorowicz [2014] Anna Fiedorowicz and Elżbieta Sidorowicz.  Acyclic improper colouring of graphs with maximum degree 4.  _Sci. China Math._ , 57(12):2485–2494, 2014.  doi:10.1007/s11425-014-4828-9.  MR: 3275398.
  * Fiedorowicz and Sidorowicz [2016] Anna Fiedorowicz and Elżbieta Sidorowicz.  Acyclic colorings of graphs with bounded degree.  _Sci. China Math._ , 59(7):1427–1440, 2016.  doi:10.1007/s11425-016-5126-5.  MR: 3515041.
  * Foisy [2002] Joel Foisy.  Intrinsically knotted graphs.  _J. Graph Theory_ , 39(3):178–187, 2002.  doi:10.1002/jgt.10017.  MR: 1883594.
  * Frick [1993] Marietjie Frick.  A survey of $(m,k)$-colorings.  In John Gimbel, John W. Kennedy, and Louis V. Quintas, eds., _Quo vadis, graph theory?_ , vol. 55 of _Annals of Discrete Mathematics_ , pp. 45–57. North-Holland, 1993.  MR: 1217975.
  * Frick and Henning [1994] Marietjie Frick and Michael A. Henning.  Extremal results on defective colorings of graphs.  _Discrete Math._ , 126(1–3):151–158, 1994.  doi:10.1016/0012-365X(94)90260-7.  MR: 1264483.
  * Gale [1979] David Gale.  The game of Hex and the Brouwer fixed-point theorem.  _The American Mathematical Monthly_ , 86(10):818–827, 1979.  doi:10.2307/2320146.  MR: 0551501.
  * Gauthier et al. [2017] Gregory Gauthier, Tien-Nam Le, and Paul Wollan.  Forcing clique immersions through chromatic number.  2017\.  arXiv: 1703.08235.
  * Gerencsér [1965] László Gerencsér.  On coloring problems.  _Mat. Lapok_ , 16:274–277, 1965.  MR: 0211913.
  * Gethner and Sulanke [2009] Ellen Gethner and Thom Sulanke.  Thickness-two graphs. II. More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs.  _Graphs Combin._ , 25(2):197–217, 2009.  doi:10.1007/s00373-008-0833-5.  MR: 2511878.
  * Gilbert et al. [1984] John R. Gilbert, Joan P. Hutchinson, and Robert E. Tarjan.  A separator theorem for graphs of bounded genus.  _J. Algorithms_ , 5(3):391–407, 1984.  doi:10.1016/0196-6774(84)90019-1.  MR: 756165.
  * Glebov and Zambalaeva [2007] Aleksei N. Glebov and D. Zh. Zambalaeva.  Path partitions of planar graphs.  _Sib. Èlektron. Mat. Izv._ , 4:450–459, 2007.  MR: 2465436.
  * Goddard and Xu [2016] Wayne Goddard and Honghai Xu.  Fractional, circular, and defective coloring of series-parallel graphs.  _J. Graph Theory_ , 81(2):146–153, 2016.  doi:10.1002/jgt.21868.  MR: 3433636.
  * Goldberg et al. [2014] Noam Goldberg, Thomas W. Mattman, and Ramin Naimi.  Many, many more intrinsically knotted graphs.  _Algebr. Geom. Topol._ , 14(3):1801–1823, 2014.  doi:10.2140/agt.2014.14.1801.  MR: 3212585.
  * Gomory and Hu [1961] Ralph E. Gomory and Te Chiang Hu.  Multi-terminal network flows.  _J. Soc. Indust. Appl. Math._ , 9:551–570, 1961.  MR: 0135624.
  * Gonçalves [2011] Daniel Gonçalves.  On vertex partitions and some minor-monotone graph parameters.  _J. Graph Theory_ , 66(1):49–56, 2011.  doi:10.1002/jgt.20490.  MR: 2742188.
  * Goodall et al. [2018] Andrew J. Goodall, Miki Hermann, Tomer Kotek, Johann A. Makowsky, and Steven D. Noble.  On the complexity of generalized chromatic polynomials.  _Advances in Applied Math._ , 94:71–102, 2018.  doi:10.1016/j.aam.2017.04.005.
  * Hadwiger [1943] Hugo Hadwiger.  Über eine Klassifikation der Streckenkomplexe.  _Vierteljschr. Naturforsch. Ges. Zürich_ , 88:133–142, 1943.  MR: 0012237.
  * Han and Zhu [2016] Ming Han and Xuding Zhu.  Locally planar graphs are 2-defective 4-paintable.  _European J. Combin._ , 54:35–50, 2016.  doi:10.1016/j.ejc.2015.12.004.  MR: 3459051.
  * Harvey and Wood [2017] Daniel J. Harvey and David R. Wood.  Parameters tied to treewidth.  _J. Graph Theory_ , 84(4):364–385, 2017.  doi:10.1002/jgt.22030.  MR: 3623383.
  * Havet and Sereni [2006] Frédéric Havet and Jean-Sébastien Sereni.  Improper choosability of graphs and maximum average degree.  _J. Graph Theory_ , 52(3):181–199, 2006.  doi:10.1002/jgt.20155.  MR: 2230831.
  * Haxell et al. [2003] Penny Haxell, Tibor Szabó, and Gábor Tardos.  Bounded size components—partitions and transversals.  _J. Combin. Theory Ser. B_ , 88(2):281–297, 2003.  doi:10.1016/S0095-8956(03)00031-5.  MR: 1983359.
  * Haxell [2001] Penny E. Haxell.  A note on vertex list colouring.  _Combin. Probab. Comput._ , 10(4):345–347, 2001.  doi:10.1017/S0963548301004758.  MR: 1860440.
  * Heath and Rosenberg [1992] Lenwood S. Heath and Arnold L. Rosenberg.  Laying out graphs using queues.  _SIAM J. Comput._ , 21(5):927–958, 1992.  doi:10.1137/0221055.  MR: 1181408.
  * Hertz et al. [2016] Alain Hertz, Romain Montagné, and François Gagnon.  Constructive algorithms for the partial directed weighted improper coloring problem.  _J. Graph Algorithms Appl._ , 20(2):159–188, 2016.  doi:10.7155/jgaa.00389.  MR: 3472163.
  * van den Heuvel and Wood [2018] Jan van den Heuvel and David R. Wood.  Improper colourings inspired by Hadwiger’s conjecture.  _J. London Math. Soc._ , accepted in 2018.  arXiv: 1704.06536.
  * Hilton [1996] Anthony J. W. Hilton.  Some improper list colouring theorems.  _Congr. Numer._ , 113:171–178, 1996.  MR: 1393708.
  * Hilton et al. [1998] Anthony J. W. Hilton, David S. G. Stirling, and Tomaž Slivnik.  A vertex-splitting lemma, de Werra’s theorem, and improper list colourings.  _J. Combin. Theory Ser. B_ , 72(1):91–103, 1998.  doi:10.1006/jctb.1997.1793.  MR: 1604693.
  * van der Holst et al. [1999] Hein van der Holst, László Lovász, and Alexander Schrijver.  _The Colin de Verdière graph parameter_ , vol. 7 of _Bolyai Soc. Math. Stud._ , pp. 29–85.  János Bolyai Math. Soc., 1999.  MR: 1673503.
  * Hopkins and Staton [1986] Glenn Hopkins and William Staton.  Vertex partitions and $k$-small subsets of graphs.  _Ars Combin._ , 22:19–24, 1986.  MR: 867729.
  * Hutchinson [1993] Joan P. Hutchinson.  Coloring ordinary maps, maps of empires and maps of the moon.  _Math. Mag._ , 66(4):211–226, 1993.  doi:10.2307/2690733.  MR: 1240669.
  * Ivančo [1992] Jaroslav Ivančo.  The weight of a graph.  In _Proc. 4th Czechoslovakian Symposium on Combinatorics, Graphs and Complexity_ , vol. 51 of _Ann. Discrete Math._ , pp. 113–116. North-Holland, 1992.  doi:10.1016/S0167-5060(08)70614-9.  MR: 1206252.
  * Jackson and Ringel [2000] Brad Jackson and Gerhard Ringel.  Variations on Ringel’s earth-moon problem.  _Discrete Math._ , 211(1-3):233–242, 2000.  doi:10.1016/S0012-365X(99)00278-2.  MR: 1735339.
  * Jakobsen [1971] Ivan T. Jakobsen.  Weakenings of the conjecture of Hadwiger for 8- and 9-chromatic graphs.  Tech. Rep. 22, Matematisk Institut, Aarhus Universitet, Denmark, 1971\.  Preprint series 1970/71.
  * Jendro’l and Madaras [1996] Stanislav Jendro’l and Tomáš Madaras.  On light subgraphs in plane graphs of minimum degree five.  _Discuss. Math. Graph Theory_ , 16(2):207–217, 1996.  doi:10.7151/dmgt.1035.  MR: 1446358.
  * Jendro’l and Tuhársky [2006] Stanislav Jendro’l and Milan Tuhársky.  A Kotzig type theorem for non-orientable surfaces.  _Mathematica Slovaca_ , 56(3):245–253, 2006.  http://dml.cz/dmlcz/130967.  MR: 2250077.
  * Jendro’l and Voss [2001] Stanislav Jendro’l and Heinz-Jürgen Voss.  Light subgraphs of multigraphs on compact 2-dimensional manifolds.  _Discrete Math._ , 233(1–3):329–351, 2001.  doi:10.1016/S0012-365X(00)00250-8.  MR: 1825625.
  * Jendro’l and Voss [2002] Stanislav Jendro’l and Heinz-Jürgen Voss.  Light subgraphs of graphs embedded in 2-dimensional manifolds of Euler characteristic $\leqslant 0$. A survey.  In _Paul Erdős and his Mathematics, II_ , vol. 11 of _Bolyai Soc. Math. Stud._ , pp. 375–411. János Bolyai Math. Soc., 2002\.  MR: 1954735.
  * Jendro’l and Voss [2013] Stanislav Jendro’l and Heinz-Jürgen Voss.  Light subgraphs of graphs embedded in the plane–A survey.  _Discrete Math._ , 313:406–421, 2013.  doi:10.1016/j.disc.2012.11.007.  MR: 3004475.
  * Jones [1974] Rhys Price Jones.  Hereditary properties and $P$-chromatic numbers.  In _Combinatorics (Proc. British Combinatorial Conf. 1973)_ , vol. 13 of _London Math. Soc. Lecture Note Ser._ , pp. 83–88. Cambridge Univ. Press, 1974.  MR: 0384590.
  * Jørgensen [1994] Leif K. Jørgensen.  Contractions to $K_{8}$.  _J. Graph Theory_ , 18(5):431–448, 1994.  doi:10.1002/jgt.3190180502.  MR: 1283309.
  * Kang and Oum [2016] Dong Yeap Kang and Sang-il Oum.  Improper coloring of graphs with no odd clique minor.  2016\.  arXiv: 1612.05372.
  * Kang [2013] Ross J. Kang.  Improper choosability and property B.  _J. Graph Theory_ , 73(3):342–353, 2013.  doi:10.1002/jgt.21680.  MR: 3062803.
  * Kang and McDiarmid [2010] Ross J. Kang and Colin McDiarmid.  The $t$-improper chromatic number of random graphs.  _Combin. Probab. Comput._ , 19(1):87–98, 2010.  doi:10.1017/S0963548309990216.  MR: 2575099.
  * Kang and McDiarmid [2015] Ross J. Kang and Colin McDiarmid.  Colouring random graphs.  In _Topics in chromatic graph theory_ , vol. 156 of _Encyclopedia Math. Appl._ , pp. 199–229. Cambridge Univ. Press, Cambridge, 2015.  MR: 3380173.
  * Kang et al. [2008] Ross J. Kang, Tobias Müller, and Jean-Sébastien Sereni.  Improper colouring of (random) unit disk graphs.  _Discrete Math._ , 308(8):1438–1454, 2008.  doi:10.1016/j.disc.2007.07.070.  MR: 2392061.
  * Karasev [2013] Roman N. Karasev.  An analogue of Gromov’s waist theorem for coloring the cube.  _Discrete & Computational Geometry_, 49(3):444–453, 2013.  doi:10.1007/s00454-013-9490-4.  MR: 3038523.
  * Kawarabayashi [2008] Ken-ichi Kawarabayashi.  A weakening of the odd Hadwiger’s conjecture.  _Combin. Probab. Comput._ , 17(6):815–821, 2008.  doi:10.1017/S0963548308009462.  MR: 2463413.
  * Kawarabayashi and Mohar [2007] Ken-ichi Kawarabayashi and Bojan Mohar.  A relaxed Hadwiger’s conjecture for list colorings.  _J. Combin. Theory Ser. B_ , 97(4):647–651, 2007.  doi:10.1016/j.jctb.2006.11.002.  MR: 2325803.
  * Kawarabayashi and Thomassen [2012] Ken-ichi Kawarabayashi and Carsten Thomassen.  From the plane to higher surfaces.  _J. Comb. Theory, Ser. B_ , 102(4):852–868, 2012.  doi:10.1016/j.jctb.2012.03.001.  MR: 2927410.
  * Kim et al. [2014] Jaehoon Kim, Alexandr Kostochka, and Xuding Zhu.  Improper coloring of sparse graphs with a given girth, I: $(0,1)$-colorings of triangle-free graphs.  _European J. Combin._ , 42:26–48, 2014.  doi:10.1016/j.ejc.2014.05.003.  MR: 3240135.
  * Kim et al. [2016] Jaehoon Kim, Alexandr Kostochka, and Xuding Zhu.  Improper coloring of sparse graphs with a given girth, II: constructions.  _J. Graph Theory_ , 81(4):403–413, 2016.  doi:10.1002/jgt.21886.  MR: 3528002.
  * Kleinberg et al. [1997] Jon M. Kleinberg, Rajeev Motwani, Prabhakar Raghavan, and Suresh Venkatasubramanian.  Storage management for evolving databases.  In _38th Annual Symposium on Foundations of Computer Science (FOCS ’97)_ , pp. 353–362. IEEE, 1997.  doi:10.1109/SFCS.1997.646124.
  * Klostermeyer [2002] William Klostermeyer.  Defective circular coloring.  _Australas. J. Combin._ , 26:21–32, 2002.  MR: 1918139.
  * Kostochka [1982] Alexandr V. Kostochka.  The minimum Hadwiger number for graphs with a given mean degree of vertices.  _Metody Diskret. Analiz._ , 38:37–58, 1982.  MR: 0713722.
  * Kostochka [1984] Alexandr V. Kostochka.  Lower bound of the Hadwiger number of graphs by their average degree.  _Combinatorica_ , 4(4):307–316, 1984.  doi:10.1007/BF02579141.  MR: 0779891.
  * Kotek et al. [2011] Tomer Kotek, Johann A. Makowsky, and Boris Zilber.  On counting generalized colorings.  In _Model theoretic methods in finite combinatorics_ , vol. 558 of _Contemp. Math._ , pp. 207–241. Amer. Math. Soc., 2011.  doi:10.1090/conm/558/11052.
  * Lawrence [1978] Jim Lawrence.  Covering the vertex set of a graph with subgraphs of smaller degree.  _Discrete Math._ , 21(1):61–68, 1978.  doi:10.1016/0012-365X(78)90147-4.  MR: 523419.
  * Lescure and Meyniel [1989] François Lescure and Henri Meyniel.  On a problem upon configurations contained in graphs with given chromatic number.  In _Graph Theory in Memory of G.A. Dirac_ , vol. 41 of _Ann. Discrete Math._ , pp. 325–331. North-Holland, Amsterdam, 1989.  doi:10.1016/S0167-5060(08)70470-9.  MR: 976011.
  * Lih et al. [2001] Ko-Wei Lih, Zengmin Song, Weifan Wang, and Kemin Zhang.  A note on list improper coloring planar graphs.  _Appl. Math. Lett._ , 14(3):269–273, 2001.  doi:10.1016/S0893-9659(00)00147-6.  MR: 1820611.
  * Linial et al. [2008] Nathan Linial, Jiří Matoušek, Or Sheffet, and Gábor Tardos.  Graph colouring with no large monochromatic components.  _Combin. Probab. Comput._ , 17(4):577–589, 2008.  doi:10.1017/S0963548308009140.  MR: 2433942.
  * Lipton and Tarjan [1979] Richard J. Lipton and Robert E. Tarjan.  A separator theorem for planar graphs.  _SIAM J. Appl. Math._ , 36(2):177–189, 1979.  doi:10.1137/0136016.  MR: 0524495.
  * Lipton and Tarjan [1980] Richard J. Lipton and Robert E. Tarjan.  Applications of a planar separator theorem.  _SIAM J. Comput._ , 9(3):615–627, 1980.  doi:10.1137/0209046.  MR: 584516.
  * Liu [2015] Chun-Hung Liu.  2-list partitioning graphs with bounded treewidth and bounded max degree into graphs with no large monochromatic components.  2015\.  Unpublished manuscript.
  * Liu and Oum [2017] Chun-Hung Liu and Sang-il Oum.  Partitioning $H$-minor free graphs into three subgraphs with no large components.  _J. Combin. Theory Ser. B_ , 2017.  doi:10.1016/j.jctb.2017.08.003.
  * Lovász [1966] László Lovász.  On decomposition of graphs.  _Studia Sci. Math. Hungar._ , 1:237–238, 1966.  MR: 0202630.
  * MacGillivray et al. [2014] Gary MacGillivray, André Raspaud, and Jacobus Swarts.  Obstructions to locally injective oriented improper colourings.  _European J. Combin._ , 35:402–412, 2014.  doi:10.1016/j.ejc.2013.06.023.  MR: 3090513.
  * Maddox [1988] Randall B. Maddox.  On $k$-dependent subsets and partitions of $k$-degenerate graphs.  In _Proc. 19th Southeastern Conference on Combinatorics, Graph Theory, and Computing_ , vol. 66 of _Congr. Numer._ , pp. 11–14. 1988.  MR: 992882.
  * Mader [1967] Wolfang Mader.  Homomorphieeigenschaften und mittlere Kantendichte von Graphen.  _Math. Ann._ , 174:265–268, 1967.  doi:10.1007/BF01364272.  MR: 0220616.
  * Mader [1968a] Wolfgang Mader.  Homomorphiesätze für Graphen.  _Math. Ann._ , 178:154–168, 1968a.  doi:10.1007/BF01350657.  MR: 0229550.
  * Mader [1968b] Wolfgang Mader.  Über trennende Eckenmengen in homomorphiekritischen Graphen.  _Math. Ann._ , 175:243–252, 1968b.  doi:10.1007/BF02052726.  MR: 0220618.
  * Matdinov [2013] Marsel Matdinov.  Size of components of a cube coloring.  _Discrete & Computational Geometry_, 50(1):185–193, 2013.  doi:10.1007/s00454-013-9504-2.  MR: 3070545.
  * Matoušek and Nešetřil [1998] Jiří Matoušek and Jaroslav Nešetřil.  _Invitation to discrete mathematics_.  Clarendon Press, 1998.  MR: 1668997.
  * Matoušek and Přívětivý [2008] Jiří Matoušek and Aleš Přívětivý.  Large monochromatic components in two-colored grids.  _SIAM J. Discrete Math._ , 22(1):295–311, 2008.  doi:10.1137/070684112.  MR: 2383243.
  * Miao [2003] Zhengke Miao.  Improper choosability of graphs embedded on the surface of genus $r$.  _Discrete Math._ , 269(1-3):311–314, 2003.  doi:10.1016/S0012-365X(03)00060-8.  MR: 1989472.
  * Mihók et al. [2011] Peter Mihók, Janka Oravcová, and Roman Soták.  Generalized circular colouring of graphs.  _Discuss. Math. Graph Theory_ , 31(2):345–356, 2011.  doi:10.7151/dmgt.1550.  MR: 2865664.
  * Mirzakhani [1996] Maryam Mirzakhani.  A small non-$4$-choosable planar graph.  _Bull. Inst. Combin. Appl._ , 17:15–18, 1996.  MR: 1386951.
  * Mohar et al. [2017] Bojan Mohar, Bruce Reed, and David R. Wood.  Colourings with bounded monochromatic components in graphs of given circumference.  _Australas. J. Combin._ , 69(2):236–242, 2017.
  * Mohar and Thomassen [2001] Bojan Mohar and Carsten Thomassen.  _Graphs on surfaces_.  Johns Hopkins University Press, 2001.  MR: 1844449.
  * Montassier and Ochem [2015] Mickaël Montassier and Pascal Ochem.  Near-colorings: non-colorable graphs and NP-completeness.  _Electron. J. Combin._ , 22(1):#P1.57, 2015.  http://www.combinatorics.org/v22i1p57.  MR: 3336571.
  * Mutzel et al. [1998] Petra Mutzel, Thomas Odenthal, and Mark Scharbrodt.  The thickness of graphs: a survey.  _Graphs Combin._ , 14(1):59–73, 1998.  doi:10.1007/PL00007219.  MR: 1617664.
  * Nešetřil and Ossona de Mendez [2012] Jaroslav Nešetřil and Patrice Ossona de Mendez.  _Sparsity_ , vol. 28 of _Algorithms and Combinatorics_.  Springer, 2012.  doi:10.1007/978-3-642-27875-4.  MR: 2920058.
  * Nešetřil et al. [2011] Jaroslav Nešetřil, Patrice Ossona de Mendez, and David R. Wood.  Characterisations and examples of graph classes with bounded expansion.  _European J. Combinatorics_ , 33(3):350–373, 2011.  doi:10.1016/j.ejc.2011.09.008.  MR: 2864421.
  * Norin [2015] Sergey Norin.  Conquering graphs of bounded treewidth.  2015\.  Unpublished manuscript.
  * Norin et al. [2017] Sergey Norin, Alex Scott, Paul Seymour, and David R. Wood.  Clustered colouring in minor-closed classes, 2017.  arXiv: 1708.02370.
  * Norin and Thomas [2008] Sergey Norin and Robin Thomas.  $K_{t}$-minors, 2008.  Presented at the Banff Graph Minors Workshop.
  * Ossona de Mendez et al. [2017] Patrice Ossona de Mendez, Sang-il Oum, and David R. Wood.  Defective colouring of graphs excluding a subgraph or minor.  _Combinatorica_ , accepted in 2017.  arXiv: 1611.09060.
  * Ozawa and Tsutsumi [2007] Makoto Ozawa and Yukihiro Tsutsumi.  Primitive spatial graphs and graph minors.  _Rev. Mat. Complut._ , 20(2):391–406, 2007.  doi:10.5209/rev“˙REMA.2007.v20.n2.16496.  MR: 2351115.
  * Pach and Tóth [1997] János Pach and Géza Tóth.  Graphs drawn with few crossings per edge.  _Combinatorica_ , 17(3):427–439, 1997.  doi:10.1007/BF01215922.  MR: 1606052.
  * Pemmaraju [1992] Sriram V. Pemmaraju.  _Exploring the Powers of Stacks and Queues via Graph Layouts_.  Ph.D. thesis, Virginia Polytechnic Institute and State University, U.S.A., 1992.
  * Poh [1990] Roger K. S. Poh.  On the linear vertex-arboricity of a planar graph.  _J. Graph Theory_ , 14(1):73–75, 1990.  doi:10.1002/jgt.3190140108.  MR: 1037422.
  * Rackham [2011] Tom Rackham.  The number of defective colorings of graphs on surfaces.  _J. Graph Theory_ , 68(2):129–136, 2011.  doi:10.1002/jgt.20546.  MR: 2833955.
  * Ramírez Alfonsín [2005] J. L. Ramírez Alfonsín.  Knots and links in spatial graphs: a survey.  _Discrete Math._ , 302(1-3):225–242, 2005.  doi:10.1016/j.disc.2004.07.035.  MR: 2179645.
  * Raymond and Thilikos [2016] Jean-Florent Raymond and Dimitrios M. Thilikos.  Recent techniques and results on the Erdős-Pósa property.  2016\.  arXiv: 1603.04615.
  * Reed [1997] Bruce A. Reed.  Tree width and tangles: a new connectivity measure and some applications.  In _Surveys in combinatorics_ , vol. 241 of _London Math. Soc. Lecture Note Ser._ , pp. 87–162. Cambridge Univ. Press, 1997.  doi:10.1017/CBO9780511662119.006.
  * Reed [2003] Bruce A. Reed.  Algorithmic aspects of tree width.  In _Recent advances in algorithms and combinatorics_ , vol. 11, pp. 85–107. Springer, 2003.  doi:10.1007/0-387-22444-0“˙4.
  * Ringel [1959] Gerhard Ringel.  _Färbungsprobleme auf Flächen und Graphen_ , vol. 2 of _Mathematische Monographien_.  VEB Deutscher Verlag der Wissenschaften, Berlin, 1959.
  * Robertson et al. [1997] Neil Robertson, Daniel P. Sanders, Paul Seymour, and Robin Thomas.  The four-colour theorem.  _J. Combin. Theory Ser. B_ , 70(1):2–44, 1997.  doi:10.1006/jctb.1997.1750.  MR: 1441258.
  * Robertson and Seymour [1986] Neil Robertson and Paul Seymour.  Graph minors. V. Excluding a planar graph.  _J. Combin. Theory Ser. B_ , 41(1):92–114, 1986.  doi:10.1016/0095-8956(86)90030-4.  MR: 0854606.
  * Robertson et al. [1993a] Neil Robertson, Paul Seymour, and Robin Thomas.  Hadwiger’s conjecture for ${K}_{6}$-free graphs.  _Combinatorica_ , 13(3):279–361, 1993a.  doi:10.1007/BF01202354.  MR: 1238823.
  * Robertson et al. [1993b] Neil Robertson, Paul Seymour, and Robin Thomas.  A survey of linkless embeddings.  In Neil Robertson and Paul Seymour, eds., _Graph structure theory. Proc. of AMS-IMS-SIAM Joint Summer Research Conf. on Graph Minors_ , vol. 147 of _Contempory Mathematics_ , pp. 125–136. American Mathematical Society, 1993b.  doi:10.1090/conm/147/01167.  MR: 1224699.
  * Robertson et al. [1995] Neil Robertson, Paul Seymour, and Robin Thomas.  Sachs’ linkless embedding conjecture.  _J. Combin. Theory Series B_ , 64:185–227, 1995.  doi:10.1006/jctb.1995.1032.  MR: 1339849.
  * Sachs [1983] Horst Sachs.  On a spatial analogue of Kuratowski’s theorem on planar graphs — an open problem.  In M. Borowiecki, J. W. Kennedy, and M. M. Syslo, eds., _Proc. Conf. on Graph Theory (Lagow, 1981)_ , vol. 1018 of _Lecture Notes in Mathematics_ , pp. 230–241. Springer, 1983.  doi:10.1007/BFb0071633.  MR: 730653.
  * Schrijver [1997] Alexander Schrijver.  Minor-monotone graph invariants.  In _Surveys in combinatorics_ , vol. 241 of _London Math. Soc. Lecture Note Ser._ , pp. 163–196. Cambridge Univ. Press, 1997.  doi:10.1017/CBO9780511662119.007.  MR: 1477747.
  * Seymour [2015] Paul Seymour.  Hadwiger’s conjecture.  In John Forbes Nash Jr. and Michael Th. Rassias, eds., _Open Problems in Mathematics_ , pp. 417–437. Springer, 2015.  doi:10.1007/978-3-319-32162-2.  MR: MR3526944.
  * Simanihuruk et al. [1997a] M. Simanihuruk, Nirmala Achuthan, and N. R. Achuthan.  On defective colourings of triangle-free graphs.  _Australas. J. Combin._ , 16:259–283, 1997a.  MR: 1477535.
  * Simanihuruk et al. [1997b] M. Simanihuruk, Nirmala Achuthan, and N. R. Achuthan.  On minimal triangle-free graphs with prescribed $1$-defective chromatic number.  _Australas. J. Combin._ , 16:203–227, 1997b.  MR: 1477532.
  * Škrekovski [2000] Riste Škrekovski.  List improper colorings of planar graphs with prescribed girth.  _Discrete Math._ , 214(1-3):221–233, 2000.  doi:10.1016/S0012-365X(99)00145-4.  MR: 1743637.
  * Song and Thomas [2006] Zi-Xia Song and Robin Thomas.  The extremal function for $K_{9}$ minors.  _J. Combin. Theory Ser. B_ , 96(2):240–252, 2006.  doi:10.1016/j.jctb.2005.07.008.  MR: 2208353.
  * Thomas [2009] Robin Thomas.  $K_{t}$ minors in large $t$-connected graphs,  In Jiří Fiala, Jan Kratochvíl, Mirka Miller, eds., _Proc. 20th International Workshop on Combinatorial Algorithms_ (IWOCA 2009),  vol. 5874 of _Lecture Notes in Computer Science_ , p. 19, Springer, 2009.  doi:10.1007/978-3-642-10217-2“˙4.
  * Thomason [1984] Andrew Thomason.  An extremal function for contractions of graphs.  _Math. Proc. Cambridge Philos. Soc._ , 95(2):261–265, 1984.  doi:10.1017/S0305004100061521.  MR: 0735367.
  * Thomason [2001] Andrew Thomason.  The extremal function for complete minors.  _J. Combin. Theory Ser. B_ , 81(2):318–338, 2001.  doi:10.1006/jctb.2000.2013.  MR: 1814910.
  * Thomassen [1994] Carsten Thomassen.  Every planar graph is $5$-choosable.  _J. Combin. Theory Ser. B_ , 62(1):180–181, 1994.  doi:10.1006/jctb.1994.1062.  MR: 1290638.
  * Tuza [1989] Zsolt Tuza.  Vertex partitions of graphs into $k$-stable and $k$-complete subgraphs.  _Ars Combin._ , 27:61–62, 1989.  MR: 989447.
  * Voigt [1993] Margit Voigt.  List colourings of planar graphs.  _Discrete Math._ , 120(1-3):215–219, 1993.  doi:10.1016/0012-365X(93)90579-I.  MR: 1235909.
  * Škrekovski [1999] Riste Škrekovski.  List improper colourings of planar graphs.  _Combin. Probab. Comput._ , 8(3):293–299, 1999.  doi:10.1017/S0963548399003752.  MR: 1702609.
  * Wang et al. [2017] Wei Wang, Jianguo Qian, and Zhidan Yan.  Towards a version of Ohba’s conjecture for improper colorings.  _Graphs Combin._ , 33(2):489–501, 2017.  doi:10.1007/s00373-017-1763-x.  MR: 3612207.
  * Wang and Xu [2013] Yingqian Wang and Lingji Xu.  Improper choosability of planar graphs without 4-cycles.  _SIAM J. Discrete Math._ , 27(4):2029–2037, 2013.  doi:10.1137/120885140.  MR: 3138095.
  * Weaver and West [1994] Margaret L. Weaver and Douglas B. West.  Relaxed chromatic numbers of graphs.  _Graphs and Combinatorics_ , 10(1):75–93, 1994.  doi:10.1007/BF01202473.  MR: 1273014.
  * Williams et al. [2012] Lee Williams, Jennifer Vandenbussche, and Gexin Yu.  Equitable defective coloring of sparse planar graphs.  _Discrete Math._ , 312(5):957–962, 2012.  doi:10.1016/j.disc.2011.10.024.  MR: 2872937.
  * Wollan [2015] Paul Wollan.  The structure of graphs not admitting a fixed immersion.  _J. Combin. Theory Ser. B._ , 110:47–66, 2015.  doi:10.1016/j.jctb.2014.07.003.  MR: 3279386.
  * Wood [2009] David R. Wood.  On tree-partition-width.  _European J. Combin._ , 30(5):1245–1253, 2009.  doi:10.1016/j.ejc.2008.11.010.  MR: 2514645.
  * Wood [2010] David R. Wood.  Contractibility and the Hadwiger conjecture.  _European J. Combin._ , 31(8):2102–2109, 2010.  doi:10.1016/j.ejc.2010.05.015.  MR: 2718284.
  * Wood [2016] David R. Wood.  Cliques in graphs excluding a complete graph minor.  _Electronic J. Combinatorics_ , 23(3):#R18, 2016.  http://www.combinatorics.org/v23i3p18/.  MR: 3558055.
  * Wood and Woodall [2009] Rupert G. Wood and Douglas R. Woodall.  Defective choosability of graphs without small minors.  _Electron. J. Combin._ , 16(1):R92, 2009.  http://www.combinatorics.org/v16i1r92.  MR: 2529801.
  * Woodall [1990] Douglas Woodall.  Improper colourings of graphs.  In _Graph colourings_ , vol. 218 of _Pitman Res. Notes Math. Ser._ , pp. 45–63. Longman, 1990.  MR: 1210067.
  * Woodall [2001] Douglas R. Woodall.  List colourings of graphs.  In _Surveys in combinatorics_ , vol. 288 of _London Math. Soc. Lecture Note Ser._ , pp. 269–301. Cambridge Univ. Press, 2001.  MR: 1850711.
  * Woodall [2002] Douglas R. Woodall.  Defective choosability results for outerplanar and related graphs.  _Discrete Math._ , 258(1-3):215–223, 2002.  doi:10.1016/S0012-365X(02)00300-X.  MR: 2002082.
  * Woodall [2004] Douglas R. Woodall.  Defective choosability of graphs with no edge-plus-independent-set minor.  _J. Graph Theory_ , 45(1):51–56, 2004.  doi:10.1002/jgt.10153.  MR: 2024815.
  * Woodall [2011] Douglas R. Woodall.  Defective choosability of graphs in surfaces.  _Discuss. Math. Graph Theory_ , 31(3):441–459, 2011.  doi:10.7151/dmgt.1557.  MR: 2866099.
  * Xu [0809] Baogang Xu.  On $(3,1)^{\ast}$-coloring of plane graphs.  _SIAM J. Discrete Math._ , 23(1):205–220, 2008/09.  doi:10.1137/06066093X.  MR: 2476823.
  * Yan et al. [2015] Zhidan Yan, Wei Wang, and Nini Xue.  On improperly chromatic-choosable graphs.  _Graphs Combin._ , 31(5):1807–1814, 2015.  doi:10.1007/s00373-014-1438-9.  MR: 3386049.
  * Yancey [2012] Matthew Yancey.  Thickness for improper colorings.  2012\.  http://www.math.illinois.edu/~dwest/regs/impthic.html.
  * Zhang [2004] Haihui Zhang.  Improper choosability of planar graphs without adjacent triangles.  _Graph Theory Notes N. Y._ , 47:34–37, 2004.  MR: 2134217.
  * Zhang [2013] Haihui Zhang.  On $(4,1)^{*}$-choosability of toroidal graphs without chordal 7-cycles and adjacent 4-cycles.  _Comment. Math. Univ. Carolin._ , 54(3):339–344, 2013.  MR: 3090414.
  * Zhang [2015] Haihui Zhang.  The result on $(3,1)^{\ast}$-choosability of graphs of nonnegative characteristic without 4-cycles and intersecting triangles.  _Ars Combin._ , 121:353–360, 2015.  MR: 3408534.
  * Zhang [2016] Haihui Zhang.  $(3,1)^{*}$-choosability of graphs of nonnegative characteristic without intersecting short cycles.  _Proc. Indian Acad. Sci. Math. Sci._ , 126(2):159–165, 2016.  doi:10.1007/s12044-016-0272-9.  MR: 3489154.
  * Zhang [2012] Li Zhang.  A $(3,1)^{\ast}$-choosable theorem on toroidal graphs.  _Discrete Appl. Math._ , 160(3):332–338, 2012.  doi:10.1016/j.dam.2011.10.019.  MR: 2862339.


# On the universal family of Hilbert schemes of points on a surface

Lei Song  Department of Mathematics and Statistics, University of Illinois at
Chicago, Chicago, IL 60607 Department of Mathematics, University of Kansas,
Lawrence, KS 66045<EMAIL_ADDRESS>
###### Abstract.

For a smooth quasi-projective surface $X$ and an integer $n\geq 3$, we show
that the universal family $Z^{n}$ over the Hilbert scheme $\text{Hilb}^{n}(X)$
of $n$ points has non $\mathbb{Q}$-Gorenstein, rational singularities, and
that the Samuel multiplicity $\mu$ at a closed point on $Z^{n}$ can be
computed in terms of the dimension of the socle. We also show that $\mu\leq
n$.

###### Key words and phrases:

Hilbert scheme of points on a surface, universal family, rational
singularities, Samuel multiplicity

##  1\. Introduction

Let $X$ be a smooth quasi-projective surface over an algebraically closed
field $k$ of characteristic $0$. Let $\text{Hilb}^{n}(X)$ denote the Hilbert
scheme of zero dimensional closed subschemes of $X$ of length $n$. Fogarty’s
fundamental result [5] claims that $\text{Hilb}^{n}(X)$ is a smooth,
irreducible variety of dimension $2n$. When $X$ is complete, one may consider
$\text{Hilb}^{n}(X)$ as a natural compactification of the space of $n$
unlabeled distinct points on $X$. For this reason, $\text{Hilb}^{n}(X)$ is a
quite useful tool for dealing with infinitely near points on $X$.

The universal family $Z^{n}\subset\text{Hilb}^{n}(X)\times X$, with the
induced projection $\pi:Z^{n}\rightarrow\text{Hilb}^{n}(X)$, is a finite flat
cover of degree $n$ over $\text{Hilb}^{n}(X)$. The importance of $Z^{n}$ lies
in its role in inductive approaches for the study of Hilbert schemes, e.g. in
deduction of the Picard scheme of $\text{Hilb}^{n}(X)$ [6], and in calculation
of the Nakajima constants [4]. While $Z^{2}$ is simply the blow up of $X\times
X$ along the diagonal, $Z^{n}$ is complicated in general. It is well known
that $Z^{n}$ is irreducible, singular (except $n$=2), and Cohen-Macaulay. By
[6], $Z^{n}$ is also normal with $R_{3}$ condition. More precisely, we prove
in this note

######  Theorem 1.1.

The universal family $Z^{n}$ is non $\mathbb{Q}$-Gorenstein, and has rational
singularities. For a closed point $\zeta=(\xi,p)\in Z^{n}$, the Samuel
multiplicity $\mu={b_{2}+1\choose 2}$, where
$b_{2}=b_{2}(\mathcal{O}_{\xi,p})$ is the dimension of the socle of
$\mathcal{O}_{\xi,p}$.

We note that $b_{2}+1$ equals the minimal number of generators of the ideal
$\mathscr{I}_{\xi,p}\subset\mathcal{O}_{X,p}$; see Lemma 2.1.

For $i>0$, let $V^{i}=\left\\{(\xi,p)\in
Z^{n}\;|\;b_{2}(\mathcal{O}_{\xi,p})=i\;\right\\}$. The locally closed subsets
$V^{i}$ form a stratification of $Z^{n}$. A proposition due to Ellingsrud and
Lehn [3] says that $\text{codim}(V^{i},\text{Hilb}^{n}(X)\times X)\geq 2i$.
This kind of codimension estimate is an ingredient in proving the
irreducibility of $\text{Hilb}^{n}(X)$ and more generally, that of certain
quot schemes. An immediate consequence of their estimate is that $b_{2}\leq
n+1$. In fact, we have

######  Theorem 1.2.

$b_{2}\leq\left\lfloor\frac{\sqrt{1+8n}-1}{2}\right\rfloor,$

and the bound is optimal. Consequently, one has $\mu\leq n$.

Haiman [8, Prop 3.5.3] proves a similar result on multiplicity, namely
$\dim_{k}\mathcal{O}_{\xi,p}\geq{b_{2}+1\choose 2}$, which implies that
$\mu\leq n$. We need to point out that $\mu\neq\dim_{k}\mathcal{O}_{\xi,p}$ in
general.

Acknowledgments: I am grateful to Lawrence Ein and Steven Sam for valuable
discussions.

##  2\. Preliminaries

For a point $p\in X$, $\mathfrak{m}_{p}$ denotes the maximal ideal of the
local ring $\mathcal{O}_{X,p}$ and $k(p)$ denotes the residue field. Let
$\xi\subset X$ be a zero dimensional closed subscheme with the defining ideal
$\mathscr{I}_{\xi}$. The socle $\text{Soc}\left(\mathcal{O}_{\xi,p}\right)$ is
defined to be $\text{Hom}_{\mathcal{O}_{X,p}}(k(p),\mathcal{O}_{\xi,p})$. We
denote the minimal number of generators of $\mathscr{I}_{\xi,p}$ by
$e(\mathscr{I}_{\xi,p})$. By Nakayama lemma
$e(\mathscr{I}_{\xi,p})=\dim_{k(p)}{\mathscr{I}_{\xi,p}\otimes k(p)}$.

Since $X$ is smooth and of dimension two, $\mathcal{O}_{\xi,p}$ has a minimal
free resolution

(2.1)
$0\rightarrow{\overset{b_{2}}{\oplus}\mathcal{O}_{X,p}}\xrightarrow{\varphi}{\overset{b_{1}}{\oplus}\mathcal{O}_{X,p}}\rightarrow{\mathcal{O}_{X,p}}\rightarrow\mathcal{O}_{\xi,p}\rightarrow
0,$

where obviously $b_{2}+1=b_{1}$, and $\varphi$ is represented by a matrix with
entries in $\mathfrak{m}_{p}$. The Hilbert-Burch theorem [2, 20.4] says that
all the $b_{2}\times b_{2}$ minors of $\varphi$ generate the ideal
$\mathscr{I}_{\xi,p}$. A standard computation of homological algebra shows

######  Lemma 2.1.

With the notations above,
$\dim_{k(p)}\text{Soc}\left(\mathcal{O}_{\xi,p}\right)=b_{2}=e(\mathscr{I}_{\xi,p})-1$.∎

We recall that the incidence correspondence Hilbert scheme
$\text{Hilb}^{n,n-1}(X)$ is defined as

$\\{(\xi,\xi^{\prime})\;|\;\xi^{\prime}\;\text{is a closed subscheme of
}\;\xi\\}\subset\text{Hilb}^{n}(X)\times\text{Hilb}^{n-1}(X)$

For such $(\xi,\xi^{\prime})$, one has a unique point $p$ which fits into the
exact sequence

$0\rightarrow\mathscr{I}_{\xi}\rightarrow\mathscr{I}_{\xi^{\prime}}\rightarrow
k(p)\rightarrow{0}.$

So naturally associated to $\text{Hilb}^{n,n-1}(X)$, there are two morphisms

$\textstyle{\text{Hilb}^{n,n-1}(X)\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\phi}$$\scriptstyle{\psi}$$\textstyle{Z^{n}}$$\textstyle{\text{Hilb}^{n-1}(X)\times
X}$

by $\psi:(\xi,\xi^{\prime})\mapsto(\xi,p)$ and
$\phi:(\xi,\xi^{\prime})\mapsto(\xi^{\prime},p)$.

We collect a few facts about $\text{Hilb}^{n,n-1}(X)$ that will be needed in
the next section.

######  Proposition 2.2 ([9], [1]).

$\text{Hilb}^{n,n-1}(X)$ is a smooth irreducible variety of dimension $2n$.

######  Proposition 2.3 ([4]).

  1. (1)

$\text{Hilb}^{n,n-1}(X)\simeq\mathbb{P}(\omega_{Z^{n}})$, where
$\omega_{Z^{n}}$ is the dualizing sheaf. In particular,
$\text{Hilb}^{n,n-1}(X)$ is a resolution of singularities of $Z^{n}$.

  2. (2)

$\text{Hilb}^{n,n-1}(X)\simeq\text{Bl}_{Z^{n-1}}(\text{Hilb}^{n-1}(X)\times
X)\simeq\mathbb{P}\left(\mathscr{I}_{Z^{n-1}\subseteq{\text{Hilb}^{n-1}(X)\times
X}}\right)$.

  3. (3)

For a closed point $(\xi,p)\in Z^{n}$,
$\psi^{-1}((\xi,p))\simeq\mathbb{P}^{b_{2}-1}_{k}$.

##  3\. Proofs

We denote the discriminant divisor of the finite map
$\pi:Z^{n}\rightarrow\text{Hilb}^{n}(X)$ by $B^{n}$, which is a prime divisor
parameterizing all non-reduced subschemes of $X$ of length $n$.

###### Proof of Theorem 1.1.

In the proof of [6, Thm 7.6], Fogarty shows that there are precisely two prime
Weil divisors on $Z^{n}$ dominating $B^{n}$, which are described as

$\displaystyle E^{n}_{1}$ $\displaystyle=$
$\displaystyle\overline{\\{(\xi,p)\;|\;\xi\;\text{has
type}\;(2,1,\cdots,1),\text{and}\;l_{p}(\xi)=2\\}},$ $\displaystyle E^{n}_{2}$
$\displaystyle=$ $\displaystyle\overline{\\{(\xi,p)\;|\;\xi\;\text{non
reduced},l_{p}(\xi)=1\\}},$

with the reduced induced closed subscheme structure. Moreover he proves that
neither $E^{n}_{1}$ nor $E^{n}_{2}$ is $\mathbb{Q}$-Cartier.

Let $r_{i}$ be the ramification index of $E^{n}_{i}$ over $B^{n}$, and
$K(\ast)$ the field of functions of $\ast$. From the identity

$r_{1}[K(E^{n}_{1}):K(B^{n})]+r_{2}[K(E^{n}_{2}):K(B^{n})]=n,$

and $[K(E^{n}_{1}):K(B^{n})]=1,[K(E^{n}_{2}):K(B^{n})]=n-2$, we see that
$r_{1}=2$ and $r_{2}=1$.

Then Riemann-Hurwitz formula for finite maps claims that

(3.1)
$K_{Z^{n}}+(2c-1)E^{n}_{1}+cE^{n}_{2}=\pi^{*}(K_{\text{Hilb}^{n}(X)}+cB^{n}),$

for all $c\in\mathbb{Q}$. Thereby we deduce that $K_{Z^{n}}$ cannot be
$\mathbb{Q}$-Cartier by setting $c=\frac{1}{2}$ or $0$.

It thus remains to show the rational singularities of $Z^{n}$ and compute the
Samuel multiplicity. Let $R$ be the local ring
$\mathcal{O}_{\text{Hilb}^{n}(X)\times X,\zeta}$. Since $Z^{n}$ is a
codimension two Cohen-Macaulay subscheme of $\text{Hilb}^{n}(X)\times X$, one
has the minimal free resolution of $\mathcal{O}_{Z^{n},\zeta}$

(3.2)
$0\rightarrow{\overset{b_{2}}{\oplus}R}\rightarrow{\overset{b_{1}}{\oplus}R}\rightarrow{R}\rightarrow\mathcal{O}_{Z^{n},\zeta}\rightarrow
0.$

Claim A: $b_{2}$ in (3.2) equals $b_{2}(\mathcal{O}_{\xi,p})$.

###### Proof of Claim A.

Let $\\{\xi\\}\times{X}$ denote the fibre of $\text{Hilb}^{n}(X)\times X$ over
$\xi$. Tensoring (3.2) with $\mathcal{O}_{\\{\xi\\}\times{X},p}$ yields the
complex

(3.3)
$0\rightarrow{\overset{b_{2}}{\oplus}\mathcal{O}_{X,p}}\rightarrow{\overset{b_{1}}{\oplus}\mathcal{O}_{X,p}}\rightarrow{\mathcal{O}_{X,p}}\rightarrow\mathcal{O}_{\xi,p}\rightarrow
0.$

The complex is exact. In fact, for $i=1,2$,

$\displaystyle\text{Tor}^{R}_{i}(\mathcal{O}_{Z^{n},\zeta},\mathcal{O}_{\\{\xi\\}\times{X},p})$
$\displaystyle\simeq$
$\displaystyle\text{Tor}^{R}_{i}(\mathcal{O}_{Z^{n},\zeta},R\otimes_{\mathcal{O}_{\text{Hilb}^{n}(X),\xi}}k(\xi))$
$\displaystyle\simeq$
$\displaystyle\text{Tor}^{\mathcal{O}_{\text{Hilb}^{n}(X),\xi}}_{i}(\mathcal{O}_{Z^{n},\zeta},k(\xi))$
$\displaystyle=$ $\displaystyle 0,$

where the last step is by the flatness of $\mathcal{O}_{Z^{n},\zeta}$ over
$\mathcal{O}_{\text{Hilb}^{n}(X),\xi}$.

Clearly $(\ref{complex})$ is minimal, so it is a minimal free resolution of
$\mathcal{O}_{\xi,p}$, and we are done. ∎

By taking dual $\text{Hom}_{R}(\cdot,R)$ for (3.2), one gets the exact
sequence

${\overset{b_{1}}{\oplus}R}\rightarrow{\overset{b_{2}}{\oplus}R}\rightarrow{\text{Ext}^{2}_{R}(\mathcal{O}_{Z^{n},\zeta},R)}\rightarrow
0.$

Since $R$ is regular, one has $R\simeq\omega_{R}$, the canonical module. By
duality,
$\text{Ext}^{2}_{R}(\mathcal{O}_{Z^{n},\zeta},R)\simeq\omega_{Z^{n},\zeta}$,
and hence
$\mathbb{P}(\omega_{Z^{n},\zeta})\hookrightarrow{\mathbb{P}:=\mathbb{P}^{b_{2}-1}_{R}}$.
Writing $\rho$ for the projection $\mathbb{P}\rightarrow\textrm{spec}\,R$, one
has the commutative diagram

$\textstyle{\mathbb{P}(\omega_{Z^{n},\zeta})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\rho}$$\textstyle{\mathbb{P}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\rho}$$\textstyle{\textrm{spec}\,\mathcal{O}_{Z^{n},\zeta}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\textrm{spec}\,R}$

Claim B: $\mathbb{P}(\omega_{Z^{n},\zeta})$ is a local complete intersection
in $\mathbb{P}$.

###### Proof of Claim B.

We have the diagram

$\textstyle{\overset{b_{1}}{\oplus}\mathcal{O}_{\mathbb{P}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\sigma}$$\textstyle{\overset{b_{2}}{\oplus}\mathcal{O}_{\mathbb{P}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathcal{O}_{\mathbb{P}}(1)}$

where $\mathcal{O}_{\mathbb{P}}(1)$ is the tautological invertible sheaf and
the column map comes from the Euler sequence.

$\mathbb{P}(\omega_{Z^{n},\zeta})$ is defined scheme-theoretically by the
vanishing of $\sigma$, and hence has $b_{1}$ defining equations. On the other
hand, $\dim\mathbb{P}(\omega_{Z^{n},\zeta})=2n=\dim\mathbb{P}-b_{1}$, i.e.
$\text{codim}(\mathbb{P}(\omega_{Z^{n},\zeta}),\mathbb{P})=b_{1}$ as required.
∎

In view of Claim B, the Koszul complex

(3.4)
$0\rightarrow\bigwedge^{b_{1}}(\overset{b_{1}}{\oplus}\mathcal{O}_{\mathbb{P}}(-1))\rightarrow\cdots\rightarrow\bigwedge^{2}(\overset{b_{1}}{\oplus}\mathcal{O}_{\mathbb{P}}(-1))\rightarrow{\overset{b_{1}}{\oplus}\mathcal{O}_{\mathbb{P}}(-1)}\rightarrow\mathcal{O}_{\mathbb{P}}\rightarrow\mathcal{O}_{\mathbb{P}(\omega_{Z^{n},\zeta})}\rightarrow
0$

is exact.

Observing that for all $j>0$ and $b_{2}-1\geq i\geq 0$,

$R^{j}\rho_{*}\left(\bigwedge^{i}\overset{b_{1}}{\oplus}\mathcal{O}_{\mathbb{P}}(-1)\right)=R^{j}\rho_{*}\left(\overset{b_{1}\choose
i}{\oplus}\mathcal{O}_{\mathbb{P}}(-i)\right)=0,$

thus by splitting sequence (3.4) into short ones, we obtain that for all
$j>0$,

$R^{j}\rho_{*}\mathcal{O}_{\mathbb{P}(\omega_{Z^{n},\zeta})}=0.$

Consider the fibred product for all closed point $\zeta\in Z^{n}$, cf. Prop.
2.3,

$\textstyle{\mathbb{P}(\omega_{Z^{n},\zeta})\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\rho}$$\textstyle{\text{Hilb}^{n,n-1}(X)\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\psi}$$\textstyle{\textrm{spec}\,\mathcal{O}_{Z^{n},\zeta}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\nu}$$\textstyle{Z^{n}.}$

Since $\nu$ is flat,

$R^{j}\psi_{*}\mathcal{O}_{\text{Hilb}^{n,n-1}(X)}\otimes_{\mathcal{O}_{Z^{n}}}\mathcal{O}_{Z^{n},\zeta}=0,$

by base change theorem. It then follows that $Z^{n}$ has rational
singularities, as $\text{Hilb}^{n,n-1}(X)$ is smooth, Prop. 2.2.

As for multiplicity, we use its relation with the Segre class $s_{t}(\cdot)$
and the invariance of Segre class under a birational morphism (cf. [7, Chap.
4]), which give

$\mu=s_{0}\left(\\{\zeta\\},Z^{n}\right)=s_{b_{2}-1}\left(\mathbb{P}^{b_{2}-1},\text{Hilb}^{n,n-1}(X)\right)=s_{b_{2}-1}(\mathcal{N}),$

where
$\mathcal{N}:=\mathcal{N}_{\mathbb{P}^{b_{2}-1}/{\text{Hilb}^{n,n-1}(X)}}$. We
note that
$\mathcal{N}\simeq\mathcal{N}_{\mathbb{P}^{b_{2}-1}/\mathbb{P}(\omega_{Z^{n},\zeta})}$.

By the exact sequence

$0\rightarrow\mathcal{N}\rightarrow\mathcal{N}_{\mathbb{P}^{b_{2}-1}/\mathbb{P}}\rightarrow\mathcal{N}_{\mathbb{P}(\omega_{Z^{n},\zeta})/{\mathbb{P}}}\big{|}_{\mathbb{P}^{b_{2}-1}}\rightarrow{0},$

and observing
$\mathcal{N}_{\mathbb{P}^{b_{2}-1}/\mathbb{P}}=\overset{2n+2}{\oplus}\mathcal{O}_{\mathbb{P}^{b_{2}-1}}$
and
$\mathcal{N}_{\mathbb{P}(\omega_{Z^{n},\zeta})/{\mathbb{P}}}\big{|}_{\mathbb{P}^{b_{2}-1}}\simeq\overset{b_{1}}{\oplus}\mathcal{O}_{\mathbb{P}^{b_{2}-1}}(1)$,
we get

$\mu=s_{b_{2}-1}(\mathcal{N})=c_{b_{2}-1}\left(\overset{b_{1}}{\oplus}\mathcal{O}_{\mathbb{P}^{b_{2}-1}}(1)\right)={b_{1}\choose
b_{2}-1}={b_{2}+1\choose 2},$

where $c$ is the Chern class. ∎

######  Remark 3.1.

As a smooth surface varies, the universal families over Hilbert schemes of $n$
points easily patch together. More precisely, let $f:X\rightarrow C$ be a
smooth, projective morphism from a 3-fold $X$ to a smooth curve $C$ over $k$.
By [5, Thm. 2.9], the relative Hilbert scheme of $n$ points
$\text{Hilb}^{n}(X/C)$ is smooth over $C$. The composite morphism
$h:Z^{n}_{X/C}\rightarrow\text{Hilb}^{n}(X/C)\rightarrow C$ from the universal
family is a flat morphism, so one gets a flat family of algebraic varieties
with non $\mathbb{Q}$-Gorenstein and rational singularities.

###### Proof of Theorem 1.2.

We can assume that $\textrm{supp}(\xi)=\\{p\\}$. Let $(A,\mathfrak{m})$ denote
the local ring $\mathcal{O}_{X,p}$ and $I$ the defining ideal of $\xi$. Since
$A/I$ is Artinian local $k$-algebra, one has $A/I\simeq{\hat{A}}/{\hat{I}}$ as
$k$-algebras, where $\hat{A}$, the $\mathfrak{m}$-adic completion of $A$, is
isomorphic to $k[\\![x,y]\\!]$.

Let $(R,\mathfrak{n})$ be the local ring $\mathcal{O}_{\mathbb{A}^{2},O}$ of
$\mathbb{A}^{2}$ at the origin. For $r\gg 0$, one has the surjection
$R/{{\mathfrak{n}}^{r}}\simeq\hat{A}/{\hat{\mathfrak{m}}^{r}}\rightarrow\hat{A}/{\hat{I}}\rightarrow
0$, so there exists an ideal $J\subset R$ such that
$R/J\simeq{\hat{A}}/{\hat{I}}$ as $k$-algebras. Therefore it suffices to
consider the case that $X=\mathbb{A}^{2}$ and $\textrm{supp}(\xi)=\\{O\\}$.

Fix a monomial order $>$ for monomials in $k[x,y]$ and let $in_{>}I$ be the
initial ideal of $I$. By [2, Thm. 15.17, Prop. 15.16], there exists a flat
family of length $n$ subschemes of $X$ over a curve such that the central
fibre corresponds to $k[x,y]/in_{>}I$, and the other fibres correspond to
rings isomorphic to $k[x,y]/I$. Because $b_{2}$ is an upper semi-continuous
function on the set of closed points on $Z^{n}$, it suffices to treat the case
when $I$ is a monomial ideal.

Figure 1.

In the monomial case, as shown in Figure 1, a set of minimal generators of $I$
corresponds to the black nodes, $n$ the number of boxes, and $b_{2}$ the
number of gray nodes. Then it becomes clear that $\frac{(b_{2}+1)b_{2}}{2}\leq
n$ and $\left\lfloor\frac{\sqrt{1+8n}-1}{2}\right\rfloor$ is the optimal upper
bound for $b_{2}$. ∎

## References

  * [1] Jan Cheah, _On the cohomology of Hilbert schemes of points_ , Journal of Algebraic Geometry 5 (1996), no. 3, 479–512.
  * [2] David Eisenbud, _Commutative algebra: with a view toward algebraic geometry_ , vol. 150, Springer, 1995.
  * [3] Geir Ellingsrud and Manfred Lehn, _Irreducibility of the punctual quotient scheme of a surface_ , Arkiv för Matematik 37 (1999), no. 2, 245–254.
  * [4] Geir Ellingsrud and Stein Strømme, _An intersection number for the punctual Hilbert scheme of a surface_ , Transactions of the American Mathematical Society 350 (1998), no. 6, 2547–2552.
  * [5] John Fogarty, _Algebraic families on an algebraic surface_ , American Journal of Mathematics 90 (1968), no. 2, 511–521.
  * [6] by same author, _Algebraic families on an algebraic surface, ii, the Picard scheme of the punctual Hilbert scheme_ , American Journal of Mathematics 95 (1973), no. 3, 660–687.
  * [7] W. Fulton, _Intersection theory_ , vol. 2, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), Springer-Verlag, Berlin, 1998.
  * [8] Mark Haiman, _Hilbert schemes, polygraphs and the Macdonald positivity conjecture_ , Journal of the American Mathematical Society 14 (2001), no. 4, 941–1006.
  * [9] AS Tikhomirov, _On Hilbert schemes and flag varieties of points on algebraic surfaces_ , preprint (1992).