On the choosability of $H$-minor-free graphs

Abstract

Given a graph $H$, let us denote by $f_\chi (H)$ and $f_\ell (H)$, respectively, the maximum chromatic number and the maximum list chromatic number of $H$-minor-free graphs. Hadwiger’s famous colouring conjecture from 1943 states that $f_\chi (K_t)=t-1$ for every $t \ge 2$. A closely related problem that has received significant attention in the past concerns $f_\ell (K_t)$, for which it is known that $2t-o(t) \le f_\ell (K_t) \le O(t (\!\log \log t)^6)$. Thus, $f_\ell (K_t)$ is bounded away from the conjectured value $t-1$ for $f_\chi (K_t)$ by at least a constant factor. The so-called $H$-Hadwiger’s conjecture, proposed by Seymour, asks to prove that $f_\chi (H)={\textrm{v}}(H)-1$ for a given graph $H$ (which would be implied by Hadwiger’s conjecture).

In this paper, we prove several new lower bounds on $f_\ell (H)$, thus exploring the limits of a list colouring extension of $H$-Hadwiger’s conjecture. Our main results are:

• For every $\varepsilon \gt 0$ and all sufficiently large graphs $H$ we have $f_\ell (H)\ge (1-\varepsilon )({\textrm{v}}(H)+\kappa (H))$, where $\kappa (H)$ denotes the vertex-connectivity of $H$.

• For every $\varepsilon \gt 0$ there exists $C=C(\varepsilon )\gt 0$ such that asymptotically almost every $n$-vertex graph $H$ with $\left \lceil C n\log n\right \rceil$ edges satisfies $f_\ell (H)\ge (2-\varepsilon )n$.

The first result generalizes recent results on complete and complete bipartite graphs and shows that the list chromatic number of $H$-minor-free graphs is separated from the desired value of $({\textrm{v}}(H)-1)$ by a constant factor for all large graphs $H$ of linear connectivity. The second result tells us that for almost all graphs $H$ with superlogarithmic average degree $f_\ell (H)$ is separated from $({\textrm{v}}(H)-1)$ by a constant factor arbitrarily close to $2$. Conceptually these results indicate that the graphs $H$ for which $f_\ell (H)$ is close to the conjectured value $({\textrm{v}}(H)-1)$ for $f_\chi (H)$ are typically rather sparse.

1. Introduction

All graphs considered in this paper are finite, have no loops and no parallel edges. Given graphs $G$ and $H$ , we say that $G$ contains $H$ as a minor, in symbols, $G\succeq H$ , if a graph isomorphic to $H$ can be obtained from a subgraph of $G$ by contracting edges.

Hadwiger’s colouring conjecture, first stated in 1943 by Hugo Hadwiger [8], is among the most famous and important open problems in graph theory. It claims a deep relationship between the chromatic number of graphs and their containment of graph minors, as follows.

Conjecture 1 (Hadwiger [8]). Let $t \in \mathbb{N}$ . If a graph $G$ is $K_t$ -minor-free, then $\chi (G)\le t-1$ .

Hadwiger’s conjecture has been proved for all values $t \le 6$ , see [26] for the most recent result in this sequence, resolving the $K_6$ -minor-free case. For $t=5$ , the conjecture states that $K_5$ -minor-free graphs are $4$ -colorable. Since planar graphs are $K_5$ -minor-free, this special case already generalises the famous four colour theorem that was proved in 1976 by Appel, Haken and Koch [1, 2].

Given that during 80 years of study little progress has been made towards resolving Hadwiger’s conjecture for $t \ge 7$ , it seems natural to approach the conjecture via meaningful relaxations. For instance, much of recent work has focused on its asymptotic version. The so-called linear Hadwiger conjecture states that for some absolute constant $C\ge 1$ , every $K_t$ -minor-free graph is $\lfloor Ct \rfloor$ -colorable. Starting with a breakthrough result by Norin, Postle and Song [20] in 2019, there has been a set of papers providing some exciting progress towards this conjecture [21, 23–25]. This culminated in the currently best known upper bound of $O(t \log \log t)$ for the chromatic number of $K_t$ -minor-free graphs by Delcourt and Postle [6] in 2021.

Another natural relaxation, proposed by Seymour [27, 28], suggests replacing the condition that the considered graphs exclude $K_t$ as a minor by the stronger condition that they exclude a particular, possibly non-complete graph $H$ on $t$ vertices as a minor.

Conjecture 2 ( $H$ -Hadwiger’s conjecture [27, 28]). $H$ -minor-free graphs are $({\textrm{v}}(H)-1)$ -colorable.

Note that Hadwiger’s conjecture would imply the truth of this statement for every $H$ . Also note that this upper bound on the chromatic number would be best possible for every $H$ , as the complete graph $K_{{\textrm{v}}(H)-1}$ has chromatic number ${\textrm{v}}(H)-1$ but is too small to host an $H$ -minor.

$H$ -Hadwiger’s conjecture can easily be verified using a degeneracy-colouring approach if $H$ is a forest, and it is also known to be true for spanning subgraphs of the Petersen graph [9]. A particular case of $H$ -Hadwiger’s conjecture which has received special attention in the past is when $H=K_{s,t}$ is a complete bipartite graph. Woodall [37] conjectured in 2001 that every $K_{s,t}$ -minor-free graph is $(s+t-1)$ -colorable. Also this problem remains open, but if true it would resolve $H$ -Hadwiger’s conjecture for all bipartite $H$ . Several special cases of this conjecture have been solved by now. Most notably, Kostochka [14, 15] proved that for some function $t_0(s)=O(s^3\log ^3 s)$ , $H$ -Hadwiger’s conjecture holds whenever $H=K_{s,t}$ and $t \ge t_0(s)$ . The conjecture is also true for $H=K_{3,3}$ , which can be seen using the structure theorem for $K_{3,3}$ -minor-free graphs by Wagner [35] and the fact that planar graphs are $5$ -colorable. In addition, the statement has been proved for $H=K_{2,t}$ when $t \ge 1$ [5, 18, 37, 38], for $H=K_{3,t}$ when $t \ge 6300$ [16] and for $H=K_{3,4}$ [10]. In a different direction, Norin and Turcotte [22] recently proved $H$ -Hadwiger’s conjecture for all sufficiently large bipartite graphs of bounded maximum degree that belong to a class of graphs with strongly sublinear separators.

1.1. List colouring $H$ -minor-free graphs

In this paper, we shall be concerned with the list chromatic number of graphs that exclude a fixed graph $H$ as a minor. List colouring is a well-known and popular subject in the area of graph colouring, whose introduction dates back to the seminal paper of Erdős, Rubin and Taylor [7]. A list assignment for a graph $G$ is a mapping $L:V(G)\rightarrow 2^{\mathbb{N}}$ assigning to every vertex $v \in V(G)$ a finite set $L(v)$ of colours, also called the list of $v$ . An $L$ -colouring of $G$ is a proper colouring $c:V(G)\rightarrow \mathbb{N}$ for which every vertex must choose a colour from its list, that is, $c(v) \in L(v)$ for every $v \in V(G)$ . Finally, we say that $G$ is $k$ -choosable for some integer $k \ge 1$ if there exists a proper $L$ -colouring for every list assignment $L$ satisfying $|L(v)|\ge k$ for all $v \in V(G)$ . The list chromatic number of $G$ , denoted $\chi _\ell (G)$ , is the smallest integer $k$ such that $G$ is $k$ -choosable. Note that trivially $\chi (G)\le \chi _\ell (G)$ for every graph $G$ , but conversely no relationship holds, as $\chi _\ell (G)$ is unbounded even on bipartite graphs $G$ , see [7].

The first open problem regarding list colouring of minor-closed graph classes was raised already in 1979 in the seminal paper by Erdős, Rubin and Taylor [7], who asked to determine the maximum list chromatic number of planar graphs. This question was answered in the 1990s in work of Thomassen [33] and Voigt [34]. Thomassen proved that every planar graph is $5$ -choosable, and Voigt gave the first examples of planar graphs $G$ with list chromatic number $\chi _\ell (G)=5$ .

The latter result also answered a question by Borowiecki [4] in the negative, who had asked whether one could potentially strengthen Hadwiger’s conjecture to the list colouring setting by asserting that every $K_t$ -minor-free graph $G$ satisfies $\chi _\ell (G)\le t-1$ .

Given the previous discussion, it is natural to study the maximum list chromatic number of $K_t$ -minor-free graphs, see also [39] for an open problem garden entry about this problem. To make the following presentation more convenient, for every graph $H$ we denote by $f_\chi (H)$ and $f_\ell (H)$ , respectively, the maximum (list) chromatic number of $H$ -minor-free graphs. Note that with this notation, the $H$ -Hadwiger’s conjecture amounts to saying that $f_\chi (H)={\textrm{v}}(H)-1$ .

Let us briefly summarise previous work regarding bounds on $f_\ell (K_t)$ . The construction of Voigt mentioned above shows that $f_\ell (K_5)\ge 5$ . Thomassen’s result regarding the $5$ -choosability of planar graphs was later extended by Škrekovski [29] to $K_5$ -minor-free graphs, thus proving that $f_\ell (K_5)=5$ . Until today none of the values $f_\ell (K_t)$ with $t \ge 6$ have been determined precisely, a list of the currently best known lower and upper bounds for $f_\ell (K_t)$ for small values of $t$ can be found in [3]. In 2007, Kawarabayashi and Mohar [12] made two conjectures regarding the asymptotic behaviour of $f_\ell (K_t)$ , namely that (A) $f_\ell (K_t)=O(t)$ , this is known as the list linear Hadwiger conjecture, and that (B) $f_\ell (K_t)\le \frac{3}{2}t$ for every $t$ . In 2010, Wood [36], inspired by the fact that $f_\ell (K_5)=5$ , proposed an even stronger conjecture stating that $f_\ell (K_t)=t$ for every $t \ge 5$ . This strong conjecture was refuted in 2011 by Barát, Joret and Wood, who gave a construction showing that $f_\ell (K_t) \ge \frac{4}{3}t-O(1)$ . However, the weaker conjecture (B) by Kawarabayashi and Mohar still remained open. Recently, a new lower bound of $f_\ell (K_t) \ge 2t-o(t)$ was established by the second author [30], thus refuting conjecture (B). As for upper bounds, the best currently known bound is $f_\ell (K_t) \le Ct (\!\log \log t)^6$ , which was established in 2020 by Postle [25]. Some previous work also addressed bounds on $f_\ell (H)$ when $H$ is non-complete. In particular, Woodall [27] conjectured in 2001 that $f_\ell (K_{s,t})=s+t-1$ for all integers $s, t \ge 1$ , and proved this in the case when $s=t=3$ . From the previously mentioned works [5, 18, 37, 38] it was also known that $f_\ell (K_{2,t})=t+1$ for $t \ge 1$ . Additionally, a result by Jørgensen [10] implied the truth of the conjecture for $K_{3,4}$ , and Kawarabayashi [11] proved that $f_\ell (K_{4,t})\le 4t$ for every $t$ . Despite this positive evidence, Woodall’s conjecture was recently disproved by the second author [31] showing that $f_\ell (K_{s,t})\ge (1-o(1))( 2s+t)$ for all large values of $s \le t$ . A positive result comes from the aforementioned result of Norin and Turcotte [22], which also works for list colourings and shows that $f_\ell (H)={\textrm{v}}(H)-1$ for all large bipartite graphs $H$ of bounded maximum degree in a graph class with strongly sublinear separators.

1.2. Our contribution

The above discussion shows that when excluding a sufficiently large complete or a sufficiently large balanced complete bipartite graph $H$ , the value of $f_\ell (H)$ exceeds the trivial lower bound $f_\ell (H) \ge{\textrm{v}}(H)-1$ by at least a constant factor. This means that, in a strong sense, one cannot hope for extending Hadwiger’s conjecture to list colouring with the same quantitative bounds. However, note that if $H$ is a complete or a balanced complete bipartite graph, then $H$ is quite dense in the sense that it has a quadratic number of edges. On the other extreme of the spectrum, the previously mentioned result by Norin and Turcotte [22] shows that $f_\ell (H)={\textrm{v}}(H)-1$ does hold for large classes of graphs $H$ with a constant maximum degree (and thus, with a linear number of edges). This naturally opens up a new question, as follows: How sparse must the desired minor $H$ be, such that one can hope for a list colouring extension of $H$ -Hadwiger’s conjecture? Concretely, which structural and density properties of graphs $H$ guarantee that $f_\ell (H)={\textrm{v}}(H)-1$ ? While one might be tempted to hope for a nice description of the class of all graphs $H$ satisfying $f_\ell (H)={\textrm{v}}(H)-1$ , Theorem 3 below speaks a word of caution: Any given graph $F$ can be augmented, by the addition of sufficiently many isolated vertices, to a graph $H$ in this class.

Theorem 3. For every graph $F$ there exists $k_0=k_0(F)$ such that for every $k \ge k_0$ the graph $H$ obtained from $F$ by the addition of $k$ isolated vertices satisfies $f_\ell (H)={\textrm{v}}(H)-1$ . In fact, every $H$ -minor-free graph is $({\textrm{v}}(H)-2)$ -degenerate.

This shows that arbitrary graphs $F$ can show up as induced subgraphs of graphs $H$ with $f_\ell (H)={\textrm{v}}(H)-1$ . To avoid such artificial constructions and to make a nice structural description of the graph class at hand more likely, it seems natural to ask for the largest class that is closed under taking subgraphs such that all members $H$ of this class satisfy $f_\ell (H)={\textrm{v}}(H)-1$ . ¹

Problem 4. Characterise the class $\mathcal{H}$ of graphs $H$ such that $f_\ell (H')={\textrm{v}}(H')-1$ for all $H'\subseteq H$ .

The main contributions of this paper are Theorems 5 and 7 below, which establish new lower bounds on $f_\ell (H)$ and strongly limit the horizon for positive instances of Problem 4. The first result proves a lower bound on $f_\ell (H)$ in terms of ${\textrm{v}}(H)$ and the vertex-connectivity $\kappa (H)$ , implying that $f_\ell (H)$ exceeds ${\textrm{v}}(H)$ by a constant factor for all large graphs of linear connectivity. ²

Theorem 5. For every $\varepsilon \gt 0$ there exists $n_0=n_0(\varepsilon )\in \mathbb{N}$ such that every graph $H$ on at least $n_0$ vertices satisfies $f_\ell (H)\ge (1-\varepsilon )({\textrm{v}}(H)+\kappa (H))$ .

In particular, this result immediately generalises both of the lower bounds of $f_\ell (K_t)\ge 2t-o(t)$ and $f_\ell (K_{s,t})\ge (1-o(1))(2s+t)$ previously established by the second author in [30, 31] by noting that $\kappa (K_t)=t-1$ and $\kappa (K_{s,t})=s$ for $s \le t$ . It also has the following simple consequence, showing that the graphs in $\mathcal{H}$ have a subquadratic number of edges.

Corollary 6. For every $n \in \mathbb{N}$ , let $h(n)$ denote the maximum possible number of edges of an $n$ -vertex graph in $\mathcal{H}$ . Then $\lim _{n\rightarrow \infty }\frac{h(n)}{n^2}=0$ .

Proof. Towards a contradiction, suppose the statement is not true. Then there is some constant $\delta \gt 0$ such that there exist arbitrarily large graphs $H \in \mathcal{H}$ with average degree at least $\delta{\textrm{v}}(H)$ . By a classical result of Mader [17], every graph of average degree at least $4(k-1)$ for some integer $k \ge 2$ contains a $k$ -connected subgraph. As $\mathcal{H}$ is closed under subgraphs, this implies that there are arbitrarily large graphs $H \in \mathcal{H}$ with connectivity at least $\frac{\delta }{4}{\textrm{v}}(H)$ . Then, using $\varepsilon \;:\!=\; \frac{\delta }{8}$ and Theorem 5, for sufficiently large $H \in \mathcal{H}$ with average degree at least $\delta{\textrm{v}}(H)$ , we have $f_\ell (H) \geq (1-\varepsilon )(1+\frac{\delta }{4}){\textrm{v}}(H) = (1+\frac{\delta }{8}-\frac{\delta ^2}{32}){\textrm{v}}(H) \gt{\textrm{v}}(H)$ . However, we have $f_\ell (H) ={\textrm{v}}(H)-1$ by the definition of $\mathcal{H}$ , which yields the desired contradiction and concludes the proof.

Our second result addresses to what extent sparsity of $H$ can push $f_\ell (H)$ closer to the trivial lower bound ${\textrm{v}}(H)-1$ , by showing that for any fixed $\varepsilon \gt 0$ , asymptotically almost all $n$ -vertex graphs $H$ with average degree of order $C\log n$ for a sufficiently large constant $C$ are far from being in $\mathcal{H}$ , in the sense that $f_\ell (H)$ is separated from ${\textrm{v}}(H)-1$ by a factor of at least $2-\varepsilon$ .

Theorem 7. For every $\varepsilon \gt 0$ there exists a constant $C=C(\varepsilon )\gt 0$ such that asymptotically almost every graph $H$ on $n$ vertices with $\lceil C n\log n \rceil$ edges satisfies $f_\ell (H)\ge (2-\varepsilon ) n$ .

Together with Corollary 6, this hints at the graphs in $\mathcal{H}$ typically being quite sparse. It also shows that the lower bound $f_\ell (K_t)\ge 2t-o(t)$ for complete graphs from [30] applies in equal strength to almost all $t$ -vertex graphs $H$ with $\omega (t \log t)$ edges, despite them being (much) sparser than $K_t$ .

Our proofs of Theorems 5 and 7 are based on several extensions and refinements of the probabilistic approach for lower bounding $f_\ell (K_t)$ and $f_\ell (K_{s,t})$ introduced by the second author in [30, 31]. However, several new ideas are required to overcome obstacles arising from the largely increased generality of the setup. For instance, to prove Theorem 7 one has to construct graphs avoiding rather sparse graphs $H$ as a minor. While the constructions in [30, 31] were based on the fact that clique sums of graphs under mild assumptions preserve $K_t$ - and $K_{s,t}$ -minor-freeness, a corresponding statement is no longer true for sparse graphs $H$ of much lower connectivity.

1.3. Organisation of the paper

In Section 2 we prove two probabilistic results on random bipartite graphs that exhibit properties of these graphs that are crucial for our constructions in the proofs of Theorems 5 and 7. We then present the proofs of our main results Theorem 5 and Theorem 7 in, respectively, Section 3 and Section 4. Finally, in Section 5 we separately prove Theorem 3. The latter proof is self-contained and independent of the results in the other three sections.

1.4. Notation and terminology

By $\kappa (G)$ we denote the vertex-connectivity of a graph $G$ , i.e., the minimum $k$ such that $G$ is $k$ -connected. Given integers $m, n \ge 1$ and an edge-probability $p \in [0,1]$ , we use $G(m,n;p)$ to denote the bipartite Erdős-Rényi random graph with bipartition classes $A$ and $B$ of sizes $m$ and $n$ , respectively, and in which a pair $ab$ with $a\in A$ and $b \in B$ is chosen as an edge of $G(m,n;p)$ independently with probability $p$ . For integers $m, n \ge 1$ we denote by $G(n;m)$ a random graph drawn uniformly from all graphs on vertex set $[n]=\{1,\ldots,n\}$ with exactly $m$ edges.

While the original definition of the graph minor-containment relation $\succeq$ is via edge contractions and deletions, for proving the results in this paper it will be more convenient to think about graph minor models. Given a graph $G$ and a graph $H$ , an $H$ -minor model is a collection $(Z_h)_{h \in V(H)}$ of pairwise disjoint and non-empty subsets of $V(G)$ with the property that $G[Z_h]$ is a connected graph for every $h \in V(H)$ and such that for every edge $h_1h_2 \in E(H)$ , there exists at least one edge in $G$ with endpoints in $Z_{h_1}$ and $Z_{h_2}$ . The sets $Z_h, h \in V(H)$ are also called the branch sets of the minor model. It is well-known and easy to see that for every pair of graphs $G$ and $H$ we have $G \succeq H$ if and only if there exists an $H$ -minor model in $G$ .

2. Probabilistic lemmas

In this short preparatory section we prove two simple auxiliary results (Lemmas 9 and 11) that will be used in the proofs of both our main results in Section 3 and 4. The lemmas capture two simple but important properties exhibited by bipartite Erdős-Rényi random graphs. These properties will later be used to lower bound the list chromatic number of the graphs in our constructions for Theorems 5 and 7 and to argue that they exclude a given graph as a minor.

Two basic tools from probability theory that we will use in the following are the classical Chernoff concentration bounds, stated below. A standard application of the Chernoff bounds yields an upper bound on the maximum degree of bipartite graphs with linear expected degree, stated below without proof.

Lemma 8 (Chernoff). Let $X$ be a binomially distributed random variable. Then the following bounds hold for every $\delta \in (0,1]$ :

\begin{equation*}\mathbb {P}(X\ge (1+\delta )\mathbb {E}(X)) \le \exp\!\left (-\frac {\delta ^2}{3}\mathbb {E}(X)\right ), \ \mathbb {P}(X\le (1-\delta )\mathbb {E}(X)) \le \exp\!\left (-\frac {\delta ^2}{2}\mathbb {E}(X)\right ).\end{equation*}

Lemma 9. Let $p \in (0,1]$ be a constant. Then w.h.p. the random bipartite graph $G=G(n, n; p)$ has maximum degree at most $2pn$ .

In order to compactly state and refer to our next lemma below, it is convenient for us to introduce a technical definition for the following relationship between a graph $H$ and a bipartite graph $G$ with vertex bipartition $A,B$ . Let $G^\complement$ denote the graph complement of $G$ . We are interested in the existence of $\widetilde{H}$ -minor models in $G^\complement$ , where $\widetilde{H}$ is a subgraph of $H$ . For fixed integers $k,l$ , consider the situation where $X_1, \ldots, X_{k} \subseteq A, Y_1, \ldots, Y_k \subseteq B$ are pairwise disjoint subsets of $A$ and $B$ and $x_1,\ldots,x_k, y_1, \ldots, y_l \in V(H)$ are distinct vertices of $H$ . Let $\widetilde{H}$ be the induced subgraph by the vertices $\{x_1,\ldots,x_k, y_1, \ldots, y_l\}$ and let $Z_{x_1} \;:\!=\; X_1, \ldots, Z_{x_k} \;:\!=\; X_k, Z_{y_1} \;:\!=\; Y_1, \ldots, Z_{y_l} \;:\!=\; Y_l$ . Then the branch sets $(Z_v)_{v \in V(\widetilde{H})}$ form an $\widetilde{H}$ -minor model in $G^\complement$ if and only if each branch set is connected and for each edge of the form $x_i y_j \in E(H)$ there is an edge between $Z_{x_i}$ and $Z_{y_j}$ in $G^\complement$ . Therefore, $(Z_v)_{v \in V(\widetilde{H})}$ is not an $\widetilde{H}$ -minor model in $G^\complement$ if there is an edge $x_i y_j \in E(H)$ such that $G$ contains all edges between $X_{i}$ and $Y_{j}$ . This relationship, with some additional constraints on branch set size and subgraph size, is captured by the following property.

Definition 10 (Property $\textsf{P}$ ). Let $0\lt \delta \lt 1$ , $s \in \mathbb{N}$ and let $H$ be a graph on $n$ vertices. We say that a bipartite graph $G$ with bipartition $\{A, B\}$ satisfies property $\textsf{P}(H, \delta,s)$ if for all integers $k, l \geq \delta n$ the following holds:

If $x_1,\ldots,x_k, y_1, \ldots, y_l \in V(H)$ are distinct vertices satisfying ${\textrm{e}}_H(\{x_1,\ldots,x_k\},\{y_1,\ldots,y_l\}) \ge s$ and $X_1, \ldots, X_{k} \subseteq A$ , $Y_1, \ldots, Y_{l} \subseteq B$ are pairwise disjoint sets of size at most $\frac{1}{\delta }$ each, then there exists an index pair $(i,j) \in [k]\times [l]$ such that $x_iy_j \in E(H)$ and $xy \in E(G)$ for every $(x,y) \in X_i \times Y_j$ .

Lemma 11. Let $\delta, p \in (0,1)$ be constants. Then there exists a constant $D=D(\delta,p)\gt 1$ and a sequence $q_n=1-o(1)$ such that with $s=s(n)\;:\!=\;\lceil D n \log n \rceil$ for every $n$ -vertex graph $H$ the random bipartite graph $G = G (n,n;p)$ satisfies $\textsf{P}(H, \delta,s)$ with probability at least $q_n$ .

Proof. Choose any constant $D\gt \max \{1,3p^{-(1/\delta ^2)}\}$ . Let $A, B$ be the vertex bipartition of $G$ with $|A| = |B| = n$ , let $H$ be an $n$ -vertex graph and let $k, l \ge \delta n$ . There are at most $n^n$ choices of distinct vertices $x_1, \ldots, x_k, y_1, \ldots, y_l \in V(H)$ and at most $n^{2n}$ choices of disjoint vertex sets $X_1, \ldots, X_k \subseteq A, \ Y_1, \ldots, Y_l \subseteq B$ . Consider a fixed such choice satisfying the premises in Definition 10 and the random event that for every pair $(i,j) \in [k]\times [l]$ such that $x_iy_j \in E(H)$ , not all of the potential edges between $X_i$ and $Y_j$ are included in $G$ . The probability that this holds is $\prod _{x_iy_j \in E(H)}(1-p^{|X_i||Y_j|}) \leq (1-p^{(1/\delta ^2)})^{Dn\log n}$ , where we used the premises that the sets $X_i, Y_j$ are of size at most $\frac{1}{\delta }$ and that there are at least $s\ge Dn\log n$ edges of the form $x_iy_j\in E(H)$ . Using a union bound over the choices described above, we have

\begin{align*}\mathbb {P}(G\text { does not satisfy property }\textsf {P}(H,\delta,s)) &\le n^{3n} (1-p^{(1/\delta ^2)})^{Dn\log n} \\[5pt] &\le \exp\!(3n\log n - p^{(1/\delta ^2)} Dn\log n).\end{align*}

We have $3-p^{(1/\delta ^2)}D\lt 0$ and thus the above expression tends to $0$ as $n\rightarrow \infty$ . Setting $q_n\;:\!=\;1-\exp\!((3-p^{(1/\delta ^2)}D)n\log n)$ then concludes the proof of the lemma.

3. Proof of Theorem 5

In this section, we present the proof of Theorem 5. We start off by making use of Lemmas 9 and 11 from the previous section to establish the existence of small $H$ -minor-free graphs that are in a sense “almost complete”, as follows.

Lemma 12. For every $\varepsilon \in (0,\frac{1}{2})$ there exists an integer $N=N(\varepsilon )$ such that for every $n \ge N$ and every $n$ -vertex graph $H$ with $\kappa (H)\ge \varepsilon n$ there exists a graph $F$ with the following properties:

• • The vertex set of $F$ can be partitioned into two disjoint sets $A$ and $B$ such that both $A$ and $B$ form cliques in $F$ and $|A|=\lfloor (1-2\varepsilon )\kappa (H)\rfloor$ , $|B|=\lfloor (1-2\varepsilon )n\rfloor$ .

• • Every vertex in $B$ has at most $\varepsilon n$ non-neighbors in $F$ .

• • $F$ is $H$ -minor-free.

Proof. Define $p\;:\!=\;\frac{\varepsilon }{2}$ and $\delta \;:\!=\;\varepsilon ^2$ . By Lemma 9 there is a sequence $p_n=1-o(1)$ such that $G(n,n;p)$ has maximum degree at most $2pn=\varepsilon n$ with probability at least $p_n$ , and by Lemma 11 there exists an absolute constant $D\gt 0$ and a sequence $q_n=1-o(1)$ such that for every $n$ -vertex graph $H$ the probability that $G(n,n;p)$ satisfies property $\textsf{P}(H, \delta, \lceil Dn\log n\rceil )$ is at least $q_n$ . Let $n_1$ be such that $p_n, q_n\gt \frac{1}{2}$ for every $n \ge n_1$ . Moreover, let $n_2 \in \mathbb{N}$ be chosen large enough such that the inequality $\delta ^2 n^2\ge D n \log n$ holds for every $n \ge n_2$ . Finally, we put $N\;:\!=\;\max \{n_1,n_2\}$ and let $n \geq N$ be arbitrary. By our choice of $N$ , there then exists at least one bipartite graph $G$ with bipartition $\{A',B'\}$ such that $|A'|=|B'|=n$ , $G$ has maximum degree at most $\varepsilon n$ , and $G$ satisfies property $\textsf{P}(H,\delta, \lceil Dn\log n\rceil )$ . Let $A \subseteq A', B \subseteq B'$ be chosen (arbitrarily) such that $|A|=\lfloor (1-2\varepsilon )\kappa (H)\rfloor$ , $|B|=\lfloor (1-2\varepsilon )n\rfloor$ . Note that this is possible as $\kappa (H)\lt{\textrm{v}}(H)=n$ . We now define $F$ as the graph complement of the induced subgraph $G[A \cup B]$ of $G$ . Since $A$ and $B$ are independent sets in $G$ , they form cliques in $F$ . Thus the first item of the lemma is satisfied. To verify the second item, it suffices to note that since $G$ has maximum degree at most $\varepsilon n$ , the same is true for $G[A \cup B]$ , and thus every vertex in $F$ can have at most $\varepsilon n$ non-neighbors in $F$ .

It thus remains to prove that $F$ is indeed $H$ -minor-free. Towards a contradiction, suppose that there exists an $H$ -minor model $(Z_h)_{h \in V(H)}$ in $F$ . Let $X_A, X_B, X_{AB}$ be the partition of $V(H)$ defined as follows: $X_A\;:\!=\;\{h \in V(H)|Z_h \subseteq A\}$ and $X_B\;:\!=\;\{h \in V(H)|Z_h \subseteq B\}$ contain those branch sets which are subsets of $A$ or of $B$ , respectively, and $X_{AB}\;:\!=\;\{h \in V(H)|Z_h \cap A \neq \emptyset \neq Z_h \cap B\}$ contains the branch sets which overlap with both $A$ and $B$ .

Our goal now is to find at least $\delta n$ vertices in $X_A$ and in $X_B$ whose corresponding vertex subsets of $A$ or of $B$ have size at most $\frac{1}{\delta }$ and which have at least $D n \log n$ edges between them. We will then be able to use property $\textsf{P}(H,\delta,\lceil Dn\log n\rceil )$ to complete the proof.

Note that we have $|X_B|+|X_{AB}|\le |B|\le (1-2\varepsilon )n$ as the sets in $(Z_h)_{h \in V(H)}$ are pairwise disjoint. Given that $|X_A|+|X_B|+|X_{AB}|={\textrm{v}}(H)=n$ , this implies that $|X_A| \ge 2\varepsilon n$ . Since the sets $(Z_h)_{h \in X_A}$ are disjoint and since $|A|\le (1-2\varepsilon )\kappa (H)\lt (1-2\varepsilon )n\lt n$ , there cannot be more than $\delta n$ sets of size greater than $\frac{1}{\delta }$ in the collection $(Z_h)_{h \in X_A}$ . Hence, there exists $k \ge 2\varepsilon n-\delta n\ge \delta n$ and $k$ distinct vertices $x_1, \ldots,x_k \in X_A$ such that $|Z_{x_i}| \le \frac{1}{\delta }$ for $i=1,\ldots,k$ . Note that $H$ has minimum degree at least $\kappa (H)$ , for otherwise one could separate a vertex in $H$ from the rest of the graph by deleting fewer than $\kappa (H)$ vertices. Using this, we have

\begin{equation*}|N_H(x_i) \cap X_B|\ge \deg _H(x_i)-|X_A \cup X_{AB}| \ge \delta (H)-|A|\end{equation*}

\begin{equation*}\ge \kappa (H)-(1-2\varepsilon )\kappa (H) =2\varepsilon \kappa (H) \ge 2\varepsilon ^2n=2\delta n\end{equation*}

for every $i=1,\ldots,k$ , where in the last step we used that $\kappa (H)\ge \varepsilon n$ by assumption. Consider for any fixed index $i \in [k]$ the set collection $(Z_h)_{h \in N_H(x_i) \cap X_B}$ . Since the sets are pairwise disjoint and contained in the set $B$ of size at most $n$ , as above it follows that at most $\delta n$ sets in this collection can be of size greater than $\frac{1}{\delta }$ . Consequently, for each $i \in [k]$ there exists a subset $N_i \subseteq N_H(x_i) \cap X_B$ of size at least $2\delta n-\delta n=\delta n$ such that $|Z_h| \le \frac{1}{\delta }$ for every $h \in N_i$ and $i \in [k]$ . Let $y_1,\ldots,y_l \in X_B$ be distinct vertices such that $\{y_1,\ldots,y_l\}=\bigcup _{i=1}^{k}{N_i}$ . Then clearly, $l \ge |N_1|\ge \delta n$ . Furthermore, we have

\begin{equation*}{\textrm {e}}_H(\{x_1,\ldots,x_k\},\{y_1,\ldots,y_l\})\ge \sum _{i=1}^{k}{|N_i|} \ge k\cdot \delta n\ge \delta ^2 n^2\ge D n\log n,\end{equation*}

where in the last step we used our assumption that $n \ge N \ge n_2$ .

We can now use that $G$ satisfies property $\textsf{P}(H,\delta,\lceil Dn\log n\rceil )$ , which directly implies that there exists a pair $(i,j) \in [k]^2$ such that $x_iy_j \in E(H)$ and $G$ contains all edges of the form $xy$ where $(x,y) \in Z_{x_i}\times Z_{y_j}$ . However, by definition of $F$ this means that there exists no edge in $F$ which has endpoints in both $Z_{x_i}$ and $Z_{y_j}$ . This is a contradiction to our initial assumption that $(Z_h)_{h \in V(H)}$ form an $H$ -minor model in $F$ . Thus, $F$ does not contain $H$ as a minor, which establishes the third item of the lemma and concludes the proof.

Our next lemma below guarantees that for sufficiently well-connected graphs $H$ , the property of being $H$ -minor-free is preserved when pasting together two graphs along a sufficiently small clique. This statement will then be used in the proof of Theorem 5 to glue several copies of the $H$ -minor-free graph from Lemma 12 along a common clique, thus eventually creating a graph that is still $H$ -minor-free but has an increased list chromatic number. The lemma is folklore in the graph minors community, see also Section 3.1 in [19].

Lemma 13. Let $G_1, G_2$ be $H$ -minor-free graphs and let $C\;:\!=\;V(G_1) \cap V(G_2)$ . If $C$ forms a clique in both $G_1$ and $G_2$ and if $|C|\lt \kappa (H)$ , then the graph union $G_1 \cup G_2$ is also $H$ -minor-free.

The last ingredient required to complete the proof of Theorem 5 is a simple but important idea on how to lower-bound the list chromatic number of a graph that is obtained from a fixed graph $F$ by repeated pasting along the same clique. Since the statement will also be reused for the proof of Theorem 7 in the next section, we decided to isolate it here. We use the following terminology:

Definition 14 (Pasting). Let $F$ be a graph, let $S \subseteq V(F)$ and $K \in \mathbb{N}$ . A $K$ -fold pasting of $F$ at $S$ is any graph that can be expressed as the union of $K$ isomorphic copies $F_1, \ldots,F_K$ of $F$ with the property that $V(F_i) \cap V(F_j)=S$ for all $1 \le i \lt j \le K$ .

Lemma 15. Let $m,n,d \in \mathbb{N}$ with $d \le m$ and let $F$ be a graph whose vertex set is partitioned into two cliques $A$ , $B$ such that every vertex in $B$ has at least $|A|-d$ neighbours in $A$ . Let $K = (|A|+|B|-1)^{|A|}$ and let $F^{(K)}$ be a $K$ -fold pasting of $F$ at $A$ . Then $\chi _\ell (F^{(K)}) \geq |A|+|B|-d$ .

Proof. Let $F_1,\ldots,F_K$ be an ordering of the copies of $F$ in the pasting graph $F^{(K)}$ , and let $B_1,\ldots,B_K$ be the corresponding copies of $B$ . Let $f : [|A|+|B|-1]^A \rightarrow [K]$ be an arbitrary bijection and let $c_1,\ldots,c_K : A \rightarrow [|A|+|B|-1]$ be the ordering of colour assignments to $A$ that satisfies $f(c_i) = i$ for all $i \in [K]$ . Consider the list assignment $L : V(F^{(K)}) \rightarrow 2^{[|A|+|B|-1]}$ defined as follows:

• $L(a) \;:\!=\; [|A|+|B|-1]$ for all $a \in A$

• $L(b) \;:\!=\; [|A|+|B|-1] \setminus \{c_i(a) \mid a \in A \setminus N_{F_i}(b) \}$ for all $b \in B_i$ for all $i \in [K]$

Given that every vertex in $B$ by assumption has at most $d$ non-neighbors in $F$ , we have $|L(v)| \geq |A|+|B|-1-d$ for all $v \in V(F^{(K)})$ . Now assume towards a contradiction that $F^{(K)}$ admits a proper $L$ -colouring $c$ and let $i \in [K]$ be the unique index satisfying $c_i(a) = c(a)$ for all $a \in A$ . Then let $c_{F_i} : A \cup B_i \rightarrow [|A|+|B|-1]$ be the colouring $c$ restricted to the graph $F_i$ . Since ${\textrm{v}}(F_i) = |A|+|B|$ , there exist by the pigeonhole principle vertices $u,v \in V(F_i)$ with $c(u) = c(v)$ . Since $c$ is proper and $A$ , $B$ are cliques, we have $uv \notin E(F_i)$ and $u \in A$ , $v \in B$ without loss of generality. However, $c(u) \notin L(v)$ by the construction of $L$ , a contradiction.

By assembling the previously established pieces, we can now easily deduce Theorem 5.

Proof of Theorem 5. Let a constant $\varepsilon \gt 0$ be given choose $\tilde{\varepsilon }\in (0, \frac{\varepsilon }{4})$ . Let $N=N(\tilde{\varepsilon })$ be as in Lemma 12. We now set $n_0\;:\!=\;\max \{N,\lceil \frac{4}{\varepsilon ^2}\rceil \rceil \}$ and claim that Theorem 5 holds for this choice of $n_0$ .

Let $H$ be a graph on $n \ge n_0$ vertices. We have to prove that $f_\ell (H)\ge (1-\varepsilon )(n+\kappa (H))$ . If $\kappa (H)\lt \varepsilon n$ , then this follows directly from the trivial lower bound via

\begin{equation*}f_\ell (H) \ge {\textrm {v}}(H)-1=n-1\ge (1-\varepsilon ^2)n=(1-\varepsilon )(n+\varepsilon n)\gt (1-\varepsilon )(n+\kappa (H)).\end{equation*}

Thus, we may now assume $\kappa (H)\ge \varepsilon n$ , in particular, $\kappa (H) \ge \tilde{\varepsilon } n$ . Using $n \ge N$ and Lemma 12 we now find that there exists an $H$ -minor-free graph $F$ whose vertex set is partitioned into two cliques $A, B$ such that $|A|=\lfloor (1-2\tilde{\varepsilon })\kappa (H)\rfloor \lt \kappa (H)$ and $|B|=\lfloor (1-2\tilde{\varepsilon })n\rfloor$ , and such that every vertex in $B$ has at most $\tilde{\varepsilon }n$ non-neighbors in $F$ . Let $d\;:\!=\;\lfloor \tilde{\varepsilon }n \rfloor$ and $K\;:\!=\;(|A|+|B|-1)^{|A|}$ . Let $F^{(K)}$ denote a $K$ -fold pasting of $F$ at the clique $A$ . Since every vertex in $B$ has at least $|A|-d$ neighbours in $A$ , we can apply Lemma 15 to find that

\begin{equation*}\chi _\ell (F^{(K)}) \ge |A|+|B|-d \ge (1-2\tilde {\varepsilon })(\kappa (H)+n)-2-\tilde {\varepsilon }n\end{equation*}

\begin{equation*}\ge (1-3\tilde {\varepsilon })(n+\kappa (H))-2\ge (1-\varepsilon )(n+\kappa (H)),\end{equation*}

using $n \ge n_0 \ge \frac{4}{\varepsilon ^2}$ in the last step. In addition, since $|A|\lt \kappa (H)$ , the graph $F^{(K)}$ is $H$ -minor-free by repeated application of Lemma 13. We conclude that $f_\ell (H)\ge (1-\varepsilon )({\textrm{v}}(H)+\kappa (H))$ , as desired.

4. Proof of Theorem 7

In this section, we present the proof of Theorem 7. The theorem claims a lower bound on $f_\ell (H)$ for almost all graphs $H$ on $n$ vertices and $\lceil C n \log n\rceil$ edges for some large constant $C\gt 0$ . However, in fact the only condition on the graph $H$ our lower bound proof relies upon is the following pseudo-random graph property, guaranteeing the existence of many edges between every pair of disjoint linear-size vertex subsets in $H$ .

Definition 16 (Property $\textsf{Q}$ , graph family $\mathcal{Q}_n$ ). Let $\delta \gt 0$ and $D \gt 1$ be arbitrary. We say that a graph $H$ with $n$ vertices satisfies property $\textsf{Q}(\delta, D)$ if for every two disjoint vertex sets $A, B \subseteq V(H)$ with $|A|,|B| \geq \delta n$ , we have ${\textrm{e}}_H(A,B)\ge D n \log n$ . Let $\mathcal{Q}_{n} (\delta, D)$ denote the family of $n$ -vertex graphs $H$ that satisfy property $\textsf{Q}(\delta, D)$ .

Crucially, property $\textsf{Q}(\delta,D)$ is satisfied for almost all graphs on $n$ vertices with an average degree of $C\log n$ for a large enough constant $C$ . The proof uses a standard probabilistic argument and is therefore omitted.

Lemma 17. Let $\delta \gt 0$ , $D \gt 1$ be arbitrary and let $m:\mathbb{N}\rightarrow \mathbb{N}$ be defined as $m(n) = \lceil \frac{D^2}{ \delta ^2} n\log n\rceil$ . Then with high probability as $n \rightarrow \infty$ , a random graph $H = G(n;m(n))$ drawn uniformly from all $n$ -vertex graphs with $m(n)$ edges satisfies property $\textsf{Q}(\delta, D)$ .

In our next step towards proving Theorem 7, we establish the following statement somewhat analogous to Lemma 12, showing how to build small and close-to-complete $H$ -minor-free graphs for a given graph $H \in \mathcal{Q}_n(\delta,D)$ .

Lemma 18. Let $\delta \in (0,1)$ , $D \gt 1$ , $n \in \mathbb N$ , and $H \in \mathcal{Q}_{n}(\delta, D)$ be arbitrary. Moreover, let $G$ be a bipartite graph with bipartition $\{A, B\}$ , $|A| = |B| = \lfloor (1-3\delta )n\rfloor$ satisfying property $\textsf{P}(H, \delta,s)$ for $s=\lceil Dn\log n\rceil$ . Then its complement graph $G^\complement$ does not contain $H[U]$ as a minor for any $U \subseteq V(H)$ with $|U| \geq (1-\delta )n$ .

Proof. Assume $G^\complement$ contains $H[U]$ as a minor for some $U \subseteq V(H)$ with $|U| \geq (1-\delta )n$ . Let $(Z_h)_{h \in U}$ be an $H[U]$ -minor model in $G^\complement$ and define $X_A \;:\!=\; \{h \in U \mid Z_h \subseteq A\}$ , $X_B \;:\!=\; \{h \in U \mid Z_h \subseteq B\}$ , and $X_{AB} \;:\!=\; \{h \in U \mid Z_h \cap A \neq \emptyset \neq \ Z_h \cap B\}$ . We have $|X_A| + |X_{AB}| \leq |A|$ , $|X_B| + |X_{AB}| \leq |B|$ , and $|X_A| + |X_B| + |X_{AB}|=|U| \geq (1-\delta )n$ , which implies $|X_A|, |X_B| \ge (1-\delta )n-(1-3\delta )n=2\delta n$ .

Since the branch sets $(Z_h)_{h \in X_A}$ in $A$ and the branch-sets $(Z_h)_{h \in X_B}$ in $B$ are pairwise disjoint, at most $\delta (1-3\delta ) n\lt \delta n$ branch sets in each of $(Z_h)_{h \in X_A}$ and $(Z_h)_{h \in X_B}$ can be larger than $\frac{1}{\delta }$ . Thus, there are at least $2\delta n-\delta n=\delta n$ branch sets of size at most $\frac{1}{\delta }$ in $(Z_h)_{h \in X_A}$ as well as in $(Z_h)_{h \in X_B}$ . Thus for $k\;:\!=\;l\;:\!=\; \lceil \delta n \rceil$ , there exist distinct vertices $x_1, \ldots, x_{k} \in X_A$ , $y_1,\ldots,y_l \in X_B$ such that $|Z_{x_i}|, |Z_{y_j}| \le \frac{1}{\delta }$ for all $1 \le i, j \le k=l$ . Since $H\in \mathcal{Q}_n(\delta,D)$ , we have ${\textrm{e}}_H(\{x_1,\ldots,x_k\},\{y_1,\ldots,y_l\})\ge \lceil D n \log n\rceil =s$ . Next we use our assumption that $G$ satisfies property $\textsf{P}(H, \delta,s)$ . It implies that there exists an edge $x_i y_j \in E(H)$ with $(i,j) \in [k]\times [l]$ such that $G$ contains all the edges $xy$ with $(x,y) \in Z_{x_i} \times Z_{y_j}$ . Then, however, there is an edge between vertices $x_i$ and $y_j$ in $H$ , but no edge between the corresponding branch sets $Z_{x_i}$ and $Z_{y_j}$ in $G^\complement$ , a contradiction.

The next auxiliary statement we need is Lemma 19 below, which establishes a weak analogue of Lemma 13 for graphs $H\in \mathcal{Q}_n(\delta,D)$ . Note that as these graphs may have sublinear minimum degree and connectivity, Lemma 13 cannot be used to obtain the same statement.

Lemma 19. Let $\delta \gt 0$ , $D \gt 1$ , $H \in \mathcal{Q}_n(\delta, D)$ and let $F$ be a graph with a clique $W \subseteq V(F)$ of size $\lfloor (1-3\delta )n\rfloor$ . Let $K \in \mathbb{N}$ and let $F^{(K)}$ be a $K$ -fold pasting of $F$ at $W$ . If $F^{(K)}$ contains $H$ as a minor, then there exists $U \subseteq V(H)$ with $|U|\ge (1-\delta )n$ such that $F$ contains $H[U]$ as a minor.

Proof. In the following, let $F_1, \ldots, F_K$ denote the copies of $F$ such that $F^{(K)}=\bigcup _{i=1}^{K}{F_i}$ .

Suppose $F^{(K)}$ has an $H$ -minor and fix an $H$ -minor model $(Z_h)_{h\in V(H)}$ in $H$ . Let us denote $X_W \;:\!=\; \{h \in V(H) \mid Z_h \cap W \neq \emptyset \}$ and $\xi _W\;:\!=\;|X_W|$ , and $X_i \;:\!=\; \{h \in V(H) \mid Z_h \subseteq V(F_i) \setminus W\}$ and $\xi _i\;:\!=\;|X_i|$ for every $i \in [K]$ . Note that since every branch-set $Z_h$ induces a connected subgraph of $F$ , every vertex $h \in V(H)$ appears in exactly one of the sets $X_W, X_1,\ldots,X_K$ , i.e., they form a partition of $V(H)$ . In particular, we have $\xi _W+\sum _{i=1}^{K}{\xi _i}={\textrm{v}}(H)=n$ .

We have $\xi _W \leq |W|\le n-3\delta n$ and thus $\sum _{i=1}^{K} \xi _i=n-\xi _W \geq 3 \delta n$ . In the following, let us w.l.o.g. assume $[K]$ is ordered such that $\xi _1 \geq \xi _2 \geq \cdots \geq \xi _K$ . We claim that $\xi _1\ge (1-\delta )n-\xi _W$ . Towards a contradiction, suppose in the following that $\xi _1 \lt (1-\delta )n - \xi _W$ . We first note that using this assumption, we have that $\sum _{i=2}^K \xi _i=n-(\xi _W+\xi _1) \gt n-(1-\delta )n=\delta n$ .

Now suppose for a first case that $\xi _1 \ge \delta n$ . Then the two disjoint sets of vertices $X_1$ and $\bigcup _{i=2}^{K}{X_i}$ in $H$ are both of size at least $\delta n$ . By property $\textsf{Q}(\delta,D)$ this implies that ${\textrm{e}}_H(X_1,\bigcup _{i=2}^{K}{X_i})\ge Dn\log n\gt 0$ . In particular there exists $2 \le i \le K$ and an edge $uv\in E(H)$ for some $u \in X_1$ and $v \in X_i$ . This implies that there must exist an edge in $F^{(K)}$ connecting a vertex in $Z_u\subseteq V(F_1)\setminus W$ to a vertex in $Z_v\subseteq V(F_i)\setminus W$ . However, by construction of $F^{(K)}$ no such edges exist, and so we arrive at the desired contradiction in this first case.

For the second case, suppose that $\xi _1\lt \delta n$ (and thus in particular $\xi _i\lt \delta n$ for all $i \in [K]$ ). Let $j \in [K]$ be the smallest index such that $\sum _{i=1}^{j}{\xi _i}\gt \delta n$ (this is well-defined, since $\sum _{i=1}^K{\xi _i}\ge 3\delta n$ , see above). By the minimality of $j$ , we have $\sum _{i=1}^{j}{\xi _i}=\xi _j+\sum _{i=1}^{j-1}{\xi _j}\le \delta n+\delta n=2\delta n$ . This implies that $\sum _{i=j+1}^K{\xi _i}=\sum _{i=1}^K{\xi _i}-\sum _{i=1}^j{\xi _i}\ge 3\delta n - 2\delta n =\delta n$ . In consequence, we find that the two disjoint vertex sets $\bigcup _{i=1}^{j}{X_i}, \bigcup _{i=j+1}^{K}{X_i}$ in $H$ are both of size at least $\delta n$ . Hence, using property $\textsf{Q}(\delta,D)$ we have ${\textrm{e}}_H(\bigcup _{i=1}^{j}{X_i},\bigcup _{i=j+1}^{K}{X_i})\ge Dn\log n\gt 0$ . Similar as above, this implies the existence of two indices $i,i'$ with $1 \le i\le j\lt i'\le K$ such that there exists an edge between $V(F_i)\setminus W$ and $V(F_{i'})\setminus W$ in $F^{(K)}$ . As this is impossible by construction of $F^{(K)}$ , a contradiction follows also in the second case. Thus our initial assumption $\xi _1\lt (1-\delta )n-\xi _W$ was false.

We therefore have $|X_1 \cup X_W|=\xi _1+\xi _W \geq (1-\delta )n$ . Let $U\;:\!=\;X_1 \cup X_W$ . For every $h \in U$ , let $Z_h'\;:\!=\;Z_h$ if $h \in X_1$ and $Z_h'\;:\!=\;Z_h \cap V(F_1)$ if $h \in X_W$ . We now show that $(Z_h')_{h \in U}$ is an $H[U]$ -minor model in $F_1$ , which will then conclude the proof of the lemma.

First of all, note that $F_1[Z_h']$ is a connected graph for every $h \in U$ . If $h \in X_1$ , then $F_1[Z_h']=F^{(K)}[Z_h]$ is connected since $(Z_h)_{h \in V(H)}$ is an $H$ -minor model. And if $h \in X_W$ , then the connectivity of $F_1[Z_h']=F^{(k)}[Z_h \cap V(F_1)]$ follows since (1) $F^{(K)}[Z_h]$ is connected and (2) every path connecting two vertices in $Z_h'$ that is contained in $F^{(K)}[Z_h]$ can be shortened to a path whose vertex set is completely contained in $V(F_1)$ by short-cutting every segment of the path that starts and ends in the clique $W$ by the direct connection between its endpoints.

Let us now consider any edge $uv \in E(H[U])$ . Then there must exist an edge $xy \in E(F^{(K)})$ with $x \in Z_u, y \in Z_v$ . If we have $x, y\in V(F_1)$ , then this witnesses the existence of an edge between $Z_u'$ and $Z_v'$ in $F_1$ , as desired. If on the other hand at least one of $x,y$ lies outside of $V(F_1)$ , then we necessarily must have $Z_u \cap W \neq \emptyset \neq Z_v \cap W$ , and thus there exists an edge in the clique induced by $W$ (and thus also in $F_1$ ) that connects a vertex in $Z_u'$ to a vertex in $Z_v'$ . All in all, this shows that $F_1$ contains $H[U]$ as a minor. Since $|U| \ge (1-\delta )n$ , this concludes the proof.

With the previous auxiliary results at hand, we can now deduce Theorem 7.

Proof of Theorem 7. Let a constant $\varepsilon \in (0,1)$ be given. Let $\delta \gt 0$ be chosen small enough such that $7\delta \lt \varepsilon$ , set $p\;:\!=\;\frac{\delta }{2}$ , let $D=D(\delta,p)\gt 1$ be the constant given by Lemma 11, and let $C \;:\!=\; \frac{D^2}{\delta ^2}$ .

For every $n \in \mathbb{N}$ , put $s=s(n)=\lceil Dn\log n\rceil$ . By Lemma 17, a random graph $H = G(n; \lceil Cn \log n\rceil )$ chosen uniformly from all $n$ -vertex graphs with $\lceil Cn\log n\rceil$ edges satisfies property $\textsf{Q}(\delta,D)$ w.h.p. as $n \rightarrow \infty$ . Now assume the graph $H$ satisfies property $\textsf{Q}(\delta,D)$ . By Lemmas 9 and 11, w.h.p. as $n \rightarrow \infty$ , the random bipartite graph $G = G(\lfloor (1-3\delta )n\rfloor, \lfloor (1-3\delta )n\rfloor ; p )$ has maximum degree at most $2p\lfloor (1-3\delta )n\rfloor \le \delta n$ and satisfies property $\textsf{P}(H, \delta,s)$ . Now fix $n$ large enough and consider a graph $G$ with bipartition $\{A,B\}$ , $|A|=|B|=\lfloor (1-3\delta n)\rfloor$ satisfying these two properties. By Lemma 18, $G^\complement$ does not contain any induced subgraph $H[U]$ as a minor for any $U \subseteq V(H)$ with $|U| \geq (1-\delta ) n$ . Let $K \;:\!=\; (|A|+|B|-1)^{|A|}$ and let $(G^\complement )^{(K)}$ be a $K$ -fold pasting of $G^\complement$ at $A$ . Then by Lemma 19, $(G^\complement )^{(K)}$ does not contain $H$ as a minor. Moreover, by Lemma 15, applied with $d=\lfloor \delta n\rfloor$ , we find that $(G^\complement )^{(K)}$ has list chromatic number at least $|A|+|B|-d\gt 2(1-3\delta )n - \delta n -2 \gt (2-\varepsilon )n$ for $n$ large enough. This shows that w.h.p. the random graph $H=G(n;\lceil Cn \log n\rceil )$ satisfies $f_\ell (H)\ge (2-\varepsilon )n$ , which concludes the proof.

5. Proof of Theorem 3

In this section we give the proof of Theorem 3, which is self-contained and independent of the results in the previous sections. A basic tool from extremal graph theory used in the proof is Turán’s theorem, in the following form:

Theorem 20 (Turán). Let $k \in \mathbb{N}$ , $k \ge 2$ and let $G$ be a graph. If ${\textrm{e}}(G)\gt (1-\frac{1}{k-1})\frac{{\textrm{v}}(G)^2}{2}$ then $G$ contains a clique on $k$ vertices.

We also use the following classical result regarding the minimum degree of $K_t$ -minor-free graphs, as independently proved by Kostochka [13] and Thomason [32].

Theorem 21 ([13, 32]). For every integer $t \ge 1$ there exists an integer $d=d(t)=O(t \sqrt{\log t})$ such that every graph of minimum degree at least $d$ contains $K_t$ as a minor. In particular, for every graph $F$ there exists $d=d(F) \in \mathbb{N}$ such that all graphs of minimum degree at least $d$ contain $F$ as a minor.

Proof of Theorem 3. We start by fixing an integer $d \in \mathbb{N}$ as guaranteed by Theorem 21, i.e. such that every graph of minimum degree at least $d$ contains $F$ as a minor. We now define $k_0(F)\;:\!=\;\min \{d+1,9\cdot{\textrm{v}}(F)^3\}$ . Let $k \ge k_0(F)$ be any given integer. Let $H$ denote the graph obtained from $F$ by adding $k$ isolated vertices. We will now show that every $H$ -minor-free graph is $({\textrm{v}}(H)-2)$ -degenerate, which then easily implies $f_\ell (H)={\textrm{v}}(H)-1$ .

Towards a contradiction, suppose that there exists an $H$ -minor-free graph $G$ which is not $({\textrm{v}}(H)-2)$ -degenerate, and let $G$ be chosen such that ${\textrm{v}}(G)$ is minimised. Note that the minimality assumption on $G$ immediately implies that $\delta (G)\ge{\textrm{v}}(H)-1={\textrm{v}}(F)+k-1$ . Observe that since $\delta (G)\ge k\gt d$ , the graph $G-x$ for some $x \in V(G)$ has minimum degree at least $d$ and thus must contain $F$ as a minor. Let $X \subseteq V(G)$ be chosen of minimum size subject to $G[X]$ containing $F$ as a minor. Note that from the above it follows that $|X|\le{\textrm{v}}(G)-1$ and hence that $V(G)\setminus X \neq \emptyset$ . Let $(Z_f)_{f \in V(F)}$ be an $F$ -minor model in $G[X]$ . By minimality of $X$ , we have that $(Z_f)_{f \in V(F)}$ forms a partition of $X$ . With the goal of bounding the number of edges in $G-X$ , we present our next argument as a separate claim. We will later use this bound and Turán’s theorem to show the existence of an $F$ -subgraph in $G-X$ .

Claim 22. For every $v \in V(G)\setminus X$ and every $f \in V(F)$ , we have $|N(v) \cap Z_f| \lt 9{\textrm{v}}(F)$ .

Proof. Let $v \in V(G)\setminus X$ and $f \in V(F)$ be arbitrary. For $|Z_f|=1$ the inequality $|N(v) \cap Z_f|\le 1\lt 9{\textrm{v}}(F)$ trivially holds for every $v \in V(G)\setminus X$ . We may therefore assume $|Z_f|\ge 2$ . Let $T_f$ denote a spanning tree of the connected graph $G[Z_f]$ , and let $L_f\subseteq Z_f$ be the set of leaves in $T_f$ .

We first show that $T_f$ has at most ${\textrm{v}}(F)-1$ leaves. Note that for every $l \in L_f$ the graph $G[Z_f\setminus \{l\}]$ is still connected. However, by minimality of $X$ , $G[X \setminus \{l\}]$ does not contain $F$ as a minor, and thus in particular the set system consisting of $Z_f\setminus \{l\}$ together with the remaining branch-sets $(Z_{f'})_{f' \in V(F), f' \neq f}$ cannot be an $F$ -minor model in $G$ . In consequence, there has to exist some $f' \in V(F)\setminus \{f\}$ such that among all vertices in $Z_f$ , the vertex $l$ is the only one that has a neighbour in $Z_{f'}$ . Since the above argument applies to any choice of $l \in L_f$ , and since the respective elements $f'$ have to be distinct for different choices of $l$ , it follows that $|L_f|\le |V(F)\setminus \{f\}|={\textrm{v}}(F)-1$ .

We next describe a decomposition of $T_f$ into strictly less than $2{\textrm{v}}(F)$ edge-disjoint and internal-vertex-disjoint paths. Let $T_f'$ be a tree without degree $2$ -vertices such that $T_f$ is a subdivision of $T_f'$ , i.e., every edge in $T_f'$ corresponds to one maximal path of $T_f$ all whose internal vertices are of degree $2$ . Then, since $T_f'$ is a tree and thus has average degree strictly less than $2$ , it has more leaves than vertices of degree $3$ or more. As the number of leaves in $T_f'$ is exactly $|L_f|$ , we have ${\textrm{v}}(T_f')\le |L_f|+(|L_f|-1)\le 2{\textrm{v}}(F)-3$ and therefore ${\textrm{e}}(T_f')={\textrm{v}}(T_f')-1\le 2{\textrm{v}}(F)-4\lt 2{\textrm{v}}(F)$ . This means that $T_f$ can be expressed as the edge-disjoint union of a collection of paths $(P_i)_{i=1}^r$ where $r\lt 2{\textrm{v}}(F)$ and the internal vertices of each path $P_i$ are of degree $2$ in $T_f$ .

Now choose a vertex set $Y\subseteq Z_f$ of size at most ${\textrm{v}}(F)-1$ as follows: For each edge $ff' \in E(F)$ , pick some vertex $y_{f'} \in Z_f$ that has at least one neighbour in $Z_{f'}$ and add it to $Y$ . Let $\mathcal{R}$ denote the collection of internally disjoint paths in $T_f$ obtained from $(P_i)_{i=1}^r$ by splitting each path $P_i$ into its maximal subpaths that do not contain internal vertices in $Y$ . It is easy to see that $|\mathcal{R}| \le r+|Y|\lt 2{\textrm{v}}(F)+{\textrm{v}}(F)=3{\textrm{v}}(F)$ , and that $T_f$ equals the union of the paths in $\mathcal{R}$ .

We next claim that for every vertex $v \in V(G)\setminus X$ and every $R \in \mathcal{R}$ , we have $|N(v) \cap V(R)|\le 3$ . Indeed, suppose that $v$ has at least $4$ distinct neighbours on $R$ . Let $x$ and $y$ be the two neighbours of $v$ on $R$ that are closest to the endpoints of $R$ . Define $R'$ as the path obtained from $R$ by replacing its subpath between $x$ and $y$ (which has to contain at least two internal vertices) by the path $x-v-y$ of length two. Let $A$ be the set of vertices on $R$ strictly between $x$ and $y$ and observe that $|A| \geq 2$ and $A \cap Y = \emptyset$ . For $X'\;:\!=\;(X\setminus A) \cup \{v\}$ we have $|X'|\lt |X|$ and we can find an $F$ -minor model in $G[X']$ , namely the branch-sets $(Z_f\setminus A) \cup \{x\}$ together with $(Z_{f'})_{f' \in V(F), f'\neq f}$ . Notice that $G[(Z_f\setminus A) \cup \{x\}]$ is indeed connected as all the internal vertices of $R$ are of degree $2$ in $T_f$ . Also, since $Y\subseteq Z_f\setminus A$ , there still exists a connection from a vertex in $(Z_f\setminus A) \cup \{x\}$ (namely, $y_{f'}$ ) to a vertex in $Z_{f'}$ for every edge $ff'\in E(F)$ . This contradicts our initial choice of $X$ and proves that our assumption was wrong, so indeed every vertex $v \in V(G)\setminus X$ satisfies $|N(v) \cap V(R)|\le 3$ for every $R\in \mathcal{R}$ .

Therefore, we have $|N(v) \cap Z_f| \le \sum _{R \in \mathcal{R}}{|N(v) \cap V(R)|}\le 3|\mathcal{R}|\lt 9{\textrm{v}}(F)$ for every $v \in V(G)\setminus X$ , which concludes the proof of the claim.

It follows immediately from Claim 22 that $|N(v) \cap X| \le \sum _{f \in V(F)}{|N(v) \cap Z_f|} \lt 9{\textrm{v}}(F)^2$ for every $v \in V(G)\setminus X$ . Additionally recalling that $\delta (G) \ge{\textrm{v}}(F)+k-1\ge k$ , we find that for every $v \in V(G)\setminus X$ , we have $\text{deg}_{G-X}(v)=|N(v) \setminus X|=\text{deg}(v)-|N(v) \cap X|\gt k-9{\textrm{v}}(F)^2$ . Having established $V(G)\setminus X \neq \emptyset$ at the beginning of the proof, it now follows that $G-X$ is a graph of minimum degree greater than $k-9{\textrm{v}}(F)^2$ . Also note that since $G[X]$ contains $F$ as a minor, we are not able to find $k$ distinct vertices in $V(G)\setminus X$ as these could be used to augment the $F$ -minor in $G[X]$ to an $H$ -minor in $G$ , contradicting our assumptions. We thus have ${\textrm{v}}(G-X)\lt k$ . Using our choice of $k_0$ and $k \ge k_0$ , it now follows that

\begin{equation*}\delta (G-X) \gt k-9{\textrm {v}}(F)^2\gt \left (1-\frac {1}{{\textrm {v}}(F)-1}\right )k \gt \left (1-\frac {1}{{\textrm {v}}(F)-1}\right ){\textrm {v}}(G-X).\end{equation*}

Therefore, $G-X$ has more than $\bigl (1-\frac{1}{{\textrm{v}}(F)-1}\bigr )\frac{{\textrm{v}}(G-X)^2}{2}$ edges and thus Theorem 20 implies the existence of a clique on ${\textrm{v}}(F)$ vertices in $G-X$ . In particular, $G-X$ and thus $G$ contain a subgraph isomorphic to $F$ . Let $K \subseteq V(G)$ be the vertex set of such a copy of $F$ . Then, since ${\textrm{v}}(G)\ge \delta (G)+1\ge{\textrm{v}}(F)+k$ , there are at least $k$ vertices outside of $K$ in $G$ , which can be added to the copy of $F$ on vertex set $K$ to create a subgraph of $G$ that is isomorphic to $H$ . In particular, this means that $G$ contains $H$ as a minor, a contradiction. All in all, we find that our initial assumption, namely regarding the existence of a smallest counterexample $G$ to our claim, was wrong. This concludes the proof that all $H$ -minor-free graphs are $({\textrm{v}}(H)-2)$ -degenerate.

It is a well-known fact and easy to prove by induction that for every $a \in \mathbb{N}$ all $a$ -degenerate graphs are $(a+1)$ -choosable. Thus what we have proved also implies that every $H$ -minor-free graph is $({\textrm{v}}(H)-1)$ -choosable, as desired. All in all, it follows that $f_\ell (H)={\textrm{v}}(H)-1$ , concluding the proof of the theorem.