# Weak coloring numbers of minor-closed graph classes

Jędrzej Hodor, Xuan Hoang La, Piotr Micek, Clément Rambaud

► To cite this version:

Jędrzej Hodor, Xuan Hoang La, Piotr Micek, Clément Rambaud. Weak coloring numbers of minor-closed graph classes. ACM-SIAM Symposium on Discrete Algorithms (SODA25), Jan 2025, New Orleans, United States. pp.3325-3334, 10.1137/1.9781611978322.107 . hal-04819269

HAL Id: hal-04819269

https://inria.hal.science/hal-04819269v1

Submitted on 4 Dec 2024

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
WEAK COLORING NUMBERS OF MINOR-CLOSED GRAPH CLASSES

JĘDRZEJ HODOR, HOANG LA, PIOTR MICEK, AND CLÉMENT RAMBAUD

ABSTRACT. We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free graphs is polynomial in $r$. We determine this polynomial up to a factor of $O(r \log r)$. Moreover, we tie the exponent of the polynomial to a structural property of $X$, namely, 2-treedepth. As a result, for a fixed graph $X$ and an $X$-minor-free graph $G$, we show that $wcol_r(G) = O(r^{\mathrm{td}(X)-1} \log r)$, which improves on the bound $wcol_r(G) = O(r^{g(\mathrm{td}(X))})$ given by Dujmović et al. (SODA, 2024), where $g$ is an exponential function. In the case of planar graphs of bounded treewidth, we show that the maximum $r$-th weak coloring number is in $O(r^2 \log r)$, which is best possible.

<footnote>(J. Hodor) THEORETICAL COMPUTER SCIENCE DEPARTMENT, FACULTY OF MATHEMATICS AND COMPUTER SCIENCE AND DOCTORAL SCHOOL OF EXACT AND NATURAL SCIENCES, JAGIELLONIAN UNIVERSITY, KRAKÓW, POLAND</footnote>

<footnote>(H. La) LISN, UNIVERSITÉ PARIS-SACLAY, CNRS, GIF-SUR-YVETTE, FRANCE</footnote>

<footnote>(P. Micek) THEORETICAL COMPUTER SCIENCE DEPARTMENT, FACULTY OF MATHEMATICS AND COMPUTER SCIENCE, JAGIELLONIAN UNIVERSITY, KRAKÓW, POLAND</footnote>

<footnote>(C. Rambaud) UNIVERSITÉ CÔTE D'AZUR, CNRS, INRIA, I3S, SOPHIA-ANTIPOLIS, FRANCE</footnote>

<footnote>E-mail addresses: jedrzej.hodor@gmail.com, hoang.la.research@gmail.com, piotr.micek@uj.edu.pl, clement.rambaud@inria.fr.</footnote>

<footnote>This research was funded by the National Science Center of Poland under grant UMO-2023/05/Y/ST6/00079 within the WEAVE-UNISONO program. J. Hodor was partially supported by a Polish Ministry of Education and Science grant (Perły Nauki; PN/01/0265/2022). C. Rambaud was partially supported by the French Agence Nationale de la Recherche under contract Digraphs ANR-19-CE48-0013-01.</footnote>
# 1. INTRODUCTION

Let $G$ be a graph, let $\Pi(G)$ be the set of all vertex orderings of $G$, let $\sigma \in \Pi(G)$, and let $r$ be a nonnegative integer. For all $u$ and $v$ vertices of $G$, we say that $v$ is weakly $r$-reachable from $u$ in $(G, \sigma)$, if there exists a path between $u$ and $v$ in $G$ containing at most $r$ edges such that for every vertex $w$ on the path, $v \leq_{\sigma} w$. Let $WReach_r[G, \sigma, u]$ be the set of vertices that are weakly $r$-reachable from $u$ in $(G, \sigma)$. The $r$-th weak coloring number of $G$ is defined as

$$ wcol_r(G) = \min_{\sigma \in \Pi(G)} \max_{u \in V(G)} |WReach_r[G, \sigma, u]|. $$

Let $X$ be a graph. The *treedepth* of $X$, denoted by $\text{td}(X)$, is defined recursively as follows

$$ \text{td}(X) = \begin{cases} 0 & \text{if } X \text{ is the null graph,} \\ \min_{v \in V(X)} \text{td}(X - v) + 1 & \text{if } X \text{ is connected, and} \\ \max_{i \in [k]} \text{td}(C_i) & \text{if } X \text{ consists of components } C_1, \dots, C_k \text{ and } k > 1. \end{cases} $$

The following two theorems are among the main contributions of this paper.

**Theorem 1.** For every positive integer $t$, for every graph $X$ with $\text{td}(X) \leq t$, there exists an integer $c$ such that for every graph $G$, if $G$ is $X$-minor-free, then for every integer $r$ with $r \geq 2$, $wcol_r(G) \leq c \cdot r^{t-1} \log r$.

**Theorem 2.** For every integer $t$ with $t \geq 2$, for every graph $X$ with $\text{td}(X) \leq t$, there exists an integer $c$ such that for every graph $G$, if $G$ is $X$-minor-free, then for every integer $r$ with $r \geq 2$, $wcol_r(G) \leq c \cdot (\text{tw}(G) + 1) \cdot r^{t-2} \log r$.

Weak coloring numbers were introduced by Kierstead and Yang [14] in 2003, though a parameter similar to $wcol_2(G)$ is already present in the work of Chen and Schelp [1] from 1993. This family of parameters gained considerable attention when Zhu [21] proved that it captures important and robust notions of sparsity, namely, bounded expansion and nowhere denseness. Specifically, a class of graphs $\mathcal{C}$ has bounded expansion if and only if there exists a function $g$ such that for every graph $G$ in $\mathcal{C}$ and every positive integer $r$, we have $wcol_r(G) \leq g(r)$. Classes of bounded expansion include in particular, planar graphs, graphs of bounded treewidth, and proper minor-closed graph classes; see the book by Nešetřil and Ossona de Mendez [15] or the recent lecture notes of Pilipczuk, Pilipczuk, and Siebertz [16] for more information on this topic. Many algorithmic problems were solved using the weak coloring numbers characterization of sparse graphs. Dvořák showed a constant-factor approximation for distance versions of domination number and independence number [4], with further applications in fixed-parameter algorithms and kernelization by Eickmeyer, Giannopoulou, Kreutzer, Kwon, Pilipczuk, Rabinovich, and Siebertz [5]. Grohe, Kreutzer, and Siebertz proved that deciding first-order properties is fixed-parameter tractable in nowhere dense graph classes [9]. Reidl and Sullivan presented an algorithm counting the number of occurrences of a fixed induced subgraph in sparse graphs [18]. The time complexities of all these algorithms depend heavily on the asymptotics of $wcol_r$ in respective classes of graphs.

The growth rate of $wcol_r(G)$ when $G$ is in a fixed proper minor-closed class of graphs has been extensively studied. In particular, Grohe, Kreutzer, Rabinovich, Siebertz, and Stavropoulos [8]
proved that if $\mathrm{tw}(G) \le t^1$, then $\mathrm{wcol}_r(G) \le \binom{r+t}{t}$. This is tight as for all nonnegative integers $r, t$ they constructed a graph $G_{r,t}$ with $\mathrm{tw}(G_{r,t}) = t$ and $\mathrm{wcol}_r(G_{r,t}) = \binom{r+t}{t}^2$. In the class of planar graphs, $\mathrm{wcol}_r(G) = \mathcal{O}(r^3)$ as proved by van den Heuvel, Ossona de Mendez, Quiroz, Rabinovich, and Siebertz [11]. On the other hand, for the family of stacked triangulations (i.e. planar graphs of treewidth at most 3), we have $\mathrm{wcol}_r(G) = \Omega(r^2 \log r)$, as shown by Joret and Micek [13]. The exact growth rate of maximum $r$-th weak coloring numbers of planar graphs is unknown. Theorem 2 immediately implies that in the class of planar graphs (or graphs of bounded Euler genus) of bounded treewidth, we have $\mathrm{wcol}_r(G) = \mathcal{O}(r^2 \log r)$, which is tight. Indeed, it follows from Euler's formula that graphs of Euler genus at most $g$ exclude $K_{3,2g+3}$ as a minor and $\mathrm{td}(K_{3,2g+3}) = 4$ for all nonnegative integers $g$.

**Corollary 3.** For all nonnegative integers $g, w$, there exists an integer $c$ such that for every graph $G$ of Euler genus at most $g$ and with $\mathrm{tw}(G) \le w$, and for every integer $r$ with $r \ge 2$,

$$ \mathrm{wcol}_r(G) \le c \cdot r^2 \log r. $$

Since outerplanar graphs are $K_{2,3}$-minor-free and have bounded treewidth, Theorem 2 yields that $\mathrm{wcol}_r(G) = \mathcal{O}(r \log r)$ in the class of outerplanar graphs $G$. This was already proved by Joret and Micek [13], who additionally showed that this bound is tight.

More generally, fix a graph $X$. What is the growth rate with respect to $r$ of the maximum of $\mathrm{wcol}_r(G)$ for all $X$-minor-free graphs $G$? Van den Heuvel et al. [11] showed that $\mathrm{wcol}_r(G) = \mathcal{O}(r^{|V(X)|-1})$. Subsequently, van den Heuvel and Wood [10] proved that $\mathrm{wcol}_r(G) = \mathcal{O}(r^{\mathrm{vc}(X)+1})$. Dujmović, Hickingbotham, Hodor, Joret, La, Micek, Morin, Rambaud, and Wood [2] proved that there exists an exponential function $g$ such that $\mathrm{wcol}_r(G) = \mathcal{O}(r^{g(\mathrm{td}(X))})$. We directly improve this result, namely, Theorem 1 states that $\mathrm{wcol}_r(G) = \mathcal{O}(r^{\mathrm{td}(X)-1} \log r)$ and Theorem 2 states that $\mathrm{wcol}_r(G) = \mathcal{O}(\mathrm{tw}(G) \cdot r^{\mathrm{td}(X)-2} \log r)$. Moreover, since $\mathrm{td}(X) - 1 \le \mathrm{vc}(G)$, we obtain $\mathrm{wcol}_r(G) = \mathcal{O}(r^{\mathrm{vc}(X)} \log r)$ and $\mathrm{wcol}_r(G) = \mathcal{O}(\mathrm{tw}(G) \cdot r^{\mathrm{vc}(X)-1} \log r)$. In these cases, the construction of Grohe et al. [8] witnesses that our bounds are tight up to a factor of $\mathcal{O}(r \log r)$ in the general case and up to $\mathcal{O}(\log r)$ in the case of bounded treewidth. Most of the known bounds on weak coloring numbers of minor-closed graph classes are summarized in Table 1.

All this previous work can be seen as an effort to understand the following graph parameter. For a given graph $X$, let

$$ f(X) = \inf \{ \alpha \in \mathbb{R} \mid \text{there exists } c > 0 \text{ such that for every } X\text{-minor-free graph } G \\ \text{and for every nonnegative integer } r, \mathrm{wcol}_r(G) \le c \cdot r^\alpha \}. $$

The question is whether $f$ is tied to$^3$ some other well-established graph parameters. Recall that for every graph $X$,

$$ \mathrm{tw}(X) \le \mathrm{pw}(X) \le \mathrm{td}(X) - 1 \le \mathrm{vc}(X) \le |V(X)| - 1. $$

<footnote>$^1$For a graph $G$, let $\mathrm{tw}(G)$, $\mathrm{pw}(G)$, and $\mathrm{vc}(G)$ stand for the treewidth, pathwidth, and vertex cover number of $G$ respectively.</footnote>

<footnote>$^2$We recall the construction in Section 2.4.</footnote>

<footnote>$^3$Two graph parameters $p, q$ are said to be *tied* if there are two functions $\alpha, \beta$ such that $p(G) \le \alpha(q(G))$ and $q(G) \le \beta(p(G))$ for every graph $G$.</footnote>
The aforementioned results imply that $tw(X) - 1 \le f(X) \le td(X) - 1$. However, $f$ is not tied to any of these parameters. Indeed, neither pathwidth nor treedepth can lower bound $f$. For every positive integer $k$, let $T_k$ be a complete ternary tree of vertex-height $k$. Recall that there is a constant depending on $k$ bounding pathwidth of $T_k$-minor-free graphs by Robertson-Seymour Excluded Tree Minor Theorem [19]. Also it is easy to show that $wcol_r(G) \le (pw(G)+1)(2r+1)$ for every graph $G$. Thus, $f(T_k) \le 1$ while $pw(T_k) = k$ and $td(T_k) = k+1$. Next, we argue that neither treewidth nor pathwidth can upper-bound $f$. For every positive integer $k$, let $L_k$ be a ladder with $k$ rungs. There is a graph $G_{r,t}$ (constructed in [8]) such that $wcol_r(G_{r,t}) = \Omega(r^t)$, and if $k = \Omega(\log t)$, then $G_{r,t}$ excludes $L_k$ as a minor. Therefore, $f(L_k) = 2^{\Omega(k)}$, and $tw(L_k) \le pw(L_k) \le 2$.

Surprisingly, the key parameter to our problem is 2-treedepth as defined by Huynh, Joret, Micek, Seweryn, and Wollan in [12], where they use it to characterize the structure of graphs excluding a fixed ladder as a minor. Let $X$ be a graph. A cut vertex of $X$ is a vertex $v \in V(X)$ such that $X - v$ has more components than $X$. A block of $X$ is a maximal connected subgraph of $X$ without a cut vertex.<fnref n="4" /> The 2-treedepth of $X$, denoted by $td_2(X)$, is defined recursively as follows

$$td_2(X) = \begin{cases} 0 & \text{if } X \text{ is the null graph,} \\ \min_{v \in V(X)} td_2(X - v) + 1 & \text{if } X \text{ consists of one block, and} \\ \max_{i \in [k]} td_2(B_i) & \text{if } X \text{ consists of blocks } B_1, \dots, B_k \text{ and } k > 1. \end{cases}$$

We show that $f$ is tied by a linear function to $td_2$. The first inequality in the theorem below is witnessed by the construction given in [8].

**Theorem 4.** For every graph $X$ with at least one edge, we have

$$td_2(X) - 2 \le f(X) \le 2td_2(X) - 3.$$

To prove Theorems 1 and 4, we prove that the value of $f$ is tied with the maximum $t$ such that $X$ is a subgraph of $G_{r,t}$ (as in [8]). In other words, we prove that $G_{r,t}$ is the obstruction for the growth of weak coloring numbers. More precisely, we introduce a slightly modified version of 2-treedepth, which we call *rooted 2-treedepth* and denote by $rtd_2(\cdot)$. Later, we show that for all graphs $X$ with at least one edge, $rtd_2(X)$ the minimum $t$ such that there exists $r$ such that $X$ is a subgraph of $G_{r,t-1}$. See Section 4 for the definition of rooted 2-treedepth and Lemma 26 for the equivalence.

Given a graph $X$ with at least one edge, we will show that $td_2(X) \le rtd_2(X) \le 2td_2(X) - 2$ and it will be clear from the definition that $rtd_2(X) \le td(X)$. As a consequence, Theorems 1 and 4 are implied by the following more accurate technical statement. See also Figure 1.

**Theorem 5.** For every positive integer $t$, for every graph $X$ with $rtd_2(X) \le t$, there exists an integer $c$ such that for every graph $G$, if $G$ is $X$-minor-free, then for every integer $r$ with $r \ge 2$,

$$wcol_r(G) \le c \cdot r^{t-1} \log r.$$

<footnote n="4">⁴The blocks can be of three types: maximal 2-connected subgraphs, cut edges together with their endpoints, and isolated vertices. Two blocks have at most one vertex in common, and such a vertex is always a cut vertex.</footnote>
<table><caption>TABLE 1. Lower and upper bounds on $max_{G \in C} wcol_r(G)$ for some minor-closed graphs classes $C$. The variables $g, k, s, t$ are fixed positive integers with $s+3 \le t \le k$, and $X$ is a fixed nonnull graph. The weak coloring numbers of $K_{s,t}$-minor-free graphs were first studied by van den Heuvel and Wood in [10]. In particular they proved the upper bound $\mathcal{O}(r^{s+1})$ and they conjectured $\mathcal{O}(r^s)$. Theorem 1 implies that $K_{s,t}$-minor-free graphs have weak coloring numbers in $\mathcal{O}(r^{s-1} \log r)$. The lower bound $\Omega(r^{s-1} \log r)$ follows from the fact that graphs of simple treewidth $s$ are $K_{s,t}$-minor-free and among them there are graphs with weak coloring numbers in $\Omega(r^{s-1} \log r)$, see [13] for further details.</caption><thead><tr><th>Class <i>C</i></th><th>lower bound</th><th>upper bound</th></tr></thead><tbody><tr><td>planar</td><td>Ω(r<sup>2</sup> log r)</td><td>Ο(r<sup>3</sup>)</td></tr><tr><td>planar and tw &le; k</td><td>Ω(r<sup>2</sup> log r)</td><td>Ο(r<sup>2</sup> log r)</td></tr><tr><td>Euler genus &le; g</td><td>Ω(r<sup>2</sup> log r)</td><td>Ο(r<sup>3</sup>)</td></tr><tr><td>Euler genus &le; g and tw &le; k</td><td>Ω(r<sup>2</sup> log r)</td><td>Ο(r<sup>2</sup> log r)</td></tr><tr><td>outerplanar</td><td>Ω(r log r)</td><td>Ο(r log r)</td></tr><tr><td>K<sub>2,t</sub>-minor-free</td><td>Ω(r log r)</td><td>Ο(r log r)</td></tr><tr><td>tw &le; k</td><td>(r+k)/k</td><td>(r+k)/k</td></tr><tr><td>K<sub>t</sub>-minor-free</td><td>Ω(r<sup>t-2</sup>)</td><td>Ο(r<sup>t-1</sup>)</td></tr><tr><td>K<sub>s,t</sub>-minor-free</td><td>Ω(r<sup>s-1</sup> log r)</td><td>Ο(r<sup>s</sup> log r)</td></tr><tr><td>K<sub>s,t</sub>-minor-free and tw &le; k</td><td>Ω(r<sup>s-1</sup> log r)</td><td>Ο(r<sup>s-1</sup> log r)</td></tr><tr><td>X-minor-free</td><td>Ω(r<sup>rtd<sub>2</sub>(X)-2</sup>)</td><td>Ο(r<sup>rtd<sub>2</sub>(X)-1</sup> log r)</td></tr><tr><td>X-minor-free and tw &le; k</td><td>Ω(r<sup>rtd<sub>2</sub>(X)-2</sup>)</td><td>Ο(r<sup>rtd<sub>2</sub>(X)-2</sup> log r)</td></tr></tbody></table>

Moreover, for all nonnegative integers $r, t$, the graph $G_{r,t}$ of [8] satisfies $rtd_2(G_{r,t}) = t + 1$ and $wcol_r(G_{r,t}) = \Omega(r^t)$. Since rooted 2-treedepth is minor-monotone<fnref n="5" /> (see Lemma 22), for every graph $X$ with at least one edge, $G_{r,rtd_2(X)-2}$ is $X$-minor-free and $wcol_r(G_{r,rtd_2(X)-2}) = \Omega(r^{rtd_2(X)-2})$ for every positive integer $r$. This and Theorem 5 imply that for every graph $X$ with at least one edge,

$$rtd_2(X) - 2 \le f(X) \le rtd_2(X) - 1.$$

Similarly, Theorem 2 is a direct consequence of the following technical statement.

<footnote n="5">⁵A graph parameter $p$ is said to be minor-monotone if $p(H) \le p(G)$ for all graphs $H$ and $G$ such that $H$ is a minor of $G$.</footnote>
**Theorem 6.** For every integer $t$ with $t \ge 2$, for every graph $X$ with $\mathrm{rtd}_2(X) \le t$, there exists an integer $c$ such that for every graph $G$, if $G$ is $X$-minor-free, then for every integer $r$ with $r \ge 2$,

$$ \mathrm{wcol}_r(G) \le c \cdot (\mathrm{tw}(G) + 1) \cdot r^{t-2} \log r. $$

When $X$ is a planar graph, $X$-minor-free graphs have bounded treewidth by the Grid-Minor Theorem [20]. Hence, Theorem 6 implies that for every planar graph $X$ with at least one edge,

$$ f(X) = \mathrm{rtd}_2(X) - 2. $$

<figure><img src="image_2.png" /><figcaption>FIGURE 1. Connections of $f$ to other graph parameters. An arrow from a parameter $p$ to a parameter $q$ indicates that there is a function $\alpha$ such that $p(X) \le \alpha(q(X))$ for every graph $X$. We show that $f$ is tied to $\mathrm{td}_2$ and $\mathrm{rtd}_2$ but not to $\mathrm{tw}$, $\mathrm{pw}$, $\mathrm{td}$, $\mathrm{vc}$, or $|V|$. The results marked in the figure (top-to-bottom) are in [11], [10], [2], and [8] respectively.</figcaption></figure>

We conclude the introduction with our two favorite problems in the area.

**Question 1.** What is the asymptotic of the maximum of $\mathrm{wcol}_r(G)$ when $G$ is planar? As discussed, it is known to be $\Omega(r^2 \log r)$ and $O(r^3)$. In this paper, we show that the lower bound is tight for planar graphs of bounded treewidth.

For a positive integer $p$, a vertex coloring $\phi$ of a graph $G$ is *p-centered* if for every connected subgraph $H$ of $G$, either $\phi$ uses more than $p$ colors in $V(H)$ or there is a color that appears exactly once in $H$. The *p-centered chromatic number* of $G$, denoted by $\chi_p(G)$, is the least number of colors in a *p-centered* coloring of $G$. Centered colorings are tied with weak coloring numbers and therefore they also characterize classes of bounded expansion. However, we seemingly miss the right proof technique to get upper bounds on $\chi_p(G)$ when $G$ excludes a fixed graph as a minor.

**Question 2.** Is there a function $g$ such that for every fixed graph $X$, for every $X$-minor-free graph $G$ and for every positive integer $p$,

$$ \chi_p(G) = O(p^{g(\mathrm{td}(X))})? $$

All we know is that $\chi_p(G) = O(p^{g(|V(X)|)})$ for some function $g$ as proved by Pilipczuk and Siebertz in [17].
## 2. OUTLINE OF THE PROOFS

In this section, we introduce several notions that we use in the proofs of Theorem 5 and Theorem 6 and then we sketch their proofs.

First, we establish basic notation. For a positive integer $k$, we write $[k] = \{1, \dots, k\}$ and $[0] = \emptyset$. The null graph is the graph with no vertices. All graphs considered in this paper are finite, simple, and undirected. Let $G_1, G_2$ be two graphs. We denote by $G_1 \sqcup G_2$ the disjoint union of $G_1$ and $G_2$, and by $G_1 \oplus G_2$ the graph obtained from $G_1 \sqcup G_2$ by adding every edge with one endpoint in $V(G_1)$ and the other in $V(G_2)$. For every positive integer $k$, for every graph $G$, we write $k \cdot G$ for the union of $k$ disjoint copies of $G$.

**2.1. The key parameter.** Let $G$ be a graph and let $k$ be a nonnegative integer. A separation of order $k$ of $G$ is a pair $(A, B)$ of subgraphs of $G$ such that $A \cup B = G$, $E(A \cap B) = \emptyset$, and $|V(A \cap B)| = k$. We define recursively a new graph parameter called rooted 2-treedepth, denoted by rtd$_2$, as follows. For every graph $G$,

(r1) $\text{rtd}_2(G) = 0$ if $G$ is the null graph,

(r2) $\text{rtd}_2(G) = 1$ if $G$ is a one vertex graph, and otherwise

(r3) $\text{rtd}_2(G)$ is the minimum of $\max\{\text{rtd}_2(A), \text{rtd}_2(B - V(A)) + |V(A) \cap V(B)|\}$ over all separations $(A, B)$ of $G$ of order at most one with $V(A) \neq \emptyset$ and $V(B) - V(A) \neq \emptyset$.

Another way to understand rtd$_2$ is through “natural” separations of the graph defined by its block decomposition. When $G$ is not connected, $\text{rtd}_2(G)$ is realized by $\text{rtd}_2(C)$, where $C$ is a component of $G$ for which the value of $\text{rtd}_2$ is the greatest. When $G$ consists of a single block, a separation $(A, B)$ of $G$ with $V(A) \neq \emptyset$ and $V(B) - V(A) \neq \emptyset$ of order at most one is such that $V(A) = \{v\}$. Therefore, $\text{rtd}_2(G) = \text{rtd}_2(B - v) + 1$. When $G$ consists of multiple blocks, the minimum of $\max\{\text{rtd}_2(A), \text{rtd}_2(B - V(A)) + |V(A) \cap V(B)|\}$ is reached for separations where $V(A) \cap V(B)$ consists of exactly one cut-vertex of $G$. The above can be summarized as the following properties. For every graph $G$,

(r4) $\text{rtd}_2(G)$ is the maximum of $\text{rtd}_2(C)$ over all components $C$ of $G$ when $G$ is not connected,

(r5) $\text{rtd}_2(G)$ is the minimum of $\text{rtd}_2(G - v) + 1$ over all vertices $v$ of $G$ when $G$ consists of one block,

(r6) $\text{rtd}_2(G)$ is the minimum of $\max\{\text{rtd}_2(A), \text{rtd}_2(B - V(A)) + 1\}$ over all separations $(A, B)$ of $G$ of order one with $V(A) \cap V(B)$ consisting of a cut-vertex, when $G$ is connected and consists of more than one block.

Moreover, observe that $\text{rtd}_2(G) \le \max\{\text{rtd}_2(A), \text{rtd}_2(B - V(A)) + |V(A) \cap V(B)|\}$ for every separation $(A, B)$ of $G$ of order at most one. In particular, for every $u \in V(G)$, $(G[\{u\}], G)$ is a separation of $G$ of order one, and so,

$$ (r7) \quad \text{rtd}_2(G) \le 1 + \text{rtd}_2(G - u). $$

Finally, vertices of degree 1 can not increase rooted 2-treedepth of a graph.

$$ (r8) \quad \text{rtd}_2(G) \le \max\{2, \text{rtd}_2(G - u)\} \quad \text{for every } u \in V(G) \text{ of degree at most 1.} $$
Rooted 2-treedepth has several interesting properties: it is minor-monotone, see Lemma 22; and
it is also tied to 2-treedepth. More precisely, for every graph $G$, we have $\mathrm{td}_2(G) \le \mathrm{rtd}_2(G) \le$
$\max\{1, 2\mathrm{td}_2(G) - 2\}$ – see Lemma 23, and these inequalities are tight – see Lemma 25.

The parameter rtd₂ originates from a construction by Grohe et al. [8] of graphs $G_{r,t}$ for all nonnegative integers $r$ and $t$ such that

$$ \mathrm{tw}(G_{r,t}) = t \quad \text{and} \quad \mathrm{wcol}_r(G_{r,t}) = \binom{r+t}{t}. $$

We now recall this construction. Let $d$ be a positive integer, let $B$ and $H$ be two graphs and let $u$ be a vertex of $H$. We define $L_d(B, H, u)$ as the graph obtained in the following process. Take a copy of $B$ and $d|V(B)$ copies of $H$. Label the latter $H_{i,x}$ for each $i \in [d]$ and $x \in V(B)$. Next, for each $x \in V(B)$ identify $x$ and $u$ in each $H_{i,x}$ for $i \in [d]$. See Figure 2.

<figure><img src="image_3.png" /><figcaption>FIGURE 2. An construction of $L_2(B, H, u)$, where $B$ is a triangle and $H$ is a path on three vertices with $u$ being one of its endpoints.</figcaption></figure>

For all nonnegative integers $r, t$ the graph $G_{r,t}$ is defined recursively for all nonnegative integers $r$ and $t$ by

$$ \begin{cases} G_{0,t} = G_{r,0} = K_1, \\ G_{r,t} = L_{\binom{r+t}{t}}(G_{r-1,t}, K_1 \oplus G_{r,t-1}, u) & \text{if } r, t > 0, \end{cases} $$

where $u$ is the vertex of $K_1$ in $K_1 \oplus G_{r,t-1}$. Observe that $G_{r,1}$ is a tree for all nonnegative integers $r$.

One can show that for all nonnegative integers $r, t$ and positive integer $d$,

$$ \mathrm{rtd}_2(L_d(G_{r-1,t}, K_1 \oplus G_{r,t-1}, u)) \le \max\{\mathrm{rtd}_2(G_{r-1,t}), 1 + \mathrm{rtd}_2(G_{r,t-1})\}. $$

Therefore, by induction, $\mathrm{rtd}_2(G_{r,t}) = t+1$. In fact, this construction is universal for graphs of rooted 2-treedepth at most $t+1$. Namely, for every graph $G$, $\mathrm{rtd}_2(G) \le t+1$ if and only if $G$ is isomorphic to a subgraph of $G_{r,t}$ for some nonnegative integer $r$. Since rooted 2-treedepth is minor-monotone, we deduce that for every graph $X$, $G_{r,\mathrm{rtd}_2(X)-2}$ is $X$-minor-free. It follows that there are $X$-minor-free graphs with $r$-th weak coloring numbers in $\Omega(r^{\mathrm{rtd}_2(X)-2})$. Hence, Theorem 5 yields that for every nonnegative integer $t$, if a minor-closed class of graphs contains graphs with $r$-th weak coloring in $\omega(r^t \log r)$, then it contains $G_{r,t}$ for every nonnegative integer $r$. As a consequence, in the setting of minor-closed graphs classes, our results imply that the family constructed by Grohe et al. is, up to an $\mathcal{O}(r \log r)$ factor, the unique construction of graphs with large weak coloring numbers. Similarly, in the setting of minor-closed graphs classes of bounded treewidth, the family constructed by Grohe et al. is, up to an $\mathcal{O}(\log r)$ factor, the unique construction of graphs with large weak coloring numbers.
2.2. **Weak coloring numbers of (G, S).** Another key ingredient in our method is a notion of weak coloring numbers focused on a given subset *S* of vertices of a graph *G*. Intuitively, we want to order the vertices of *S* and place them first in the ordering of *V*(*G*) so that, whatever the ordering of the other vertices is, every vertex weakly reaches a small number of vertices in *S*.

Let $G$ be a graph, let $r$ be a nonnegative integer, let $S \subseteq V(G)$, let $\sigma$ be an ordering of $S$, let $u \in V(G)$, and let $v \in S$. We say that $v$ is weakly $r$-reachable from $u$ in $(G, S, \sigma)$ if there is an $u-v$ path $P$ in $G$ of length at most $r$ such that $\min_{\sigma}(V(P) \cap S) = v$. We denote by $\text{WReach}_r[G, S, \sigma, u]$ the set of all the weakly $r$-reachable vertices from $u$ in $(G, S, \sigma)$ and we write $\text{wcol}_r(G, S, \sigma) = \max_{u \in V(G)} |\text{WReach}_r[G, S, \sigma, u]|$. Finally, let $\text{wcol}_r(G, S)$ be the minimum value of $\text{wcol}_r(G, S, \sigma)$ among all $\sigma$ orderings of $S$. For each of the defined objects, we drop $S$ when $S = V(G)$. Namely, $v$ is weakly $r$-reachable from $u$ in $(G, \sigma)$ whenever $v$ is weakly $r$-reachable from $u$ in $(G, V(G), \sigma)$, $\text{WReach}_r[G, \sigma, u] = \text{WReach}_r[G, V(G), \sigma, u]$, $\text{wcol}_r(G, \sigma) = \text{wcol}_r(G, V(G), \sigma)$, and $\text{wcol}_r(G) = \text{wcol}_r(G, V(G))$. This matches the definition given in Section 1. See an illustration in Figure 3. In Section 3, we give many properties of this notion.

<figure><img src="image_4.png" /><figcaption>FIGURE 3. The pink vertices correspond to the set $S$. The vertices in $S$ highlighted blue are in $\text{WReach}_3[G, S, \sigma, u]$.</figcaption></figure>

2.3. **$\mathcal{F}$-rich models.** For a graph $H$, a model of $H$ in a graph $G$ is a family $(B_x \mid x \in V(H))$ of disjoint subsets of $V(G)$ such that

(i) $G[B_x]$ is connected, for every $x \in V(H)$; and

(ii) there is an edge between $B_x$ and $B_y$ in $G$, for every $xy \in E(H)$.

If $G$ has a model of $H$, then we say that $H$ is a *minor* of $G$. Let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$. Such a model of $H$ is said to be *$\mathcal{F}$-rich* if we have the additional following property.

(iii) For every $x \in V(H)$, there exists $F \in \mathcal{F}$ such that $F \subseteq G[B_x]$.

For example, if $H$ has $k$ vertices and no edges, then $G$ has an $\mathcal{F}$-rich model of $H$ if and only if $G$ contains $k$ pairwise disjoint members of $\mathcal{F}$. Another extreme case is when $\mathcal{F}$ contains every one-vertex subgraph of $G$. Then every model of $H$ in $G$ is $\mathcal{F}$-rich.

2.4. **Plan of the proof.** We now present the main ideas behind the proofs of Theorem 5 and Theorem 6. In order to prove the theorems, we strengthen the statement and instead of considering graphs with no models of $X$, we consider graphs with no $\mathcal{F}$-rich models of $X$, given a family $\mathcal{F}$ of nonnull connected subgraphs of $G$. This turns out to be very helpful in keeping induction invariant if we carefully choose $\mathcal{F}$. For some choices of $\mathcal{F}$, excluding an $\mathcal{F}$-rich model of a graph may be a local property. Therefore, we keep a global property that $G$ excludes $K_k$ as a minor, where $k = |V(X)|$. The locality of the property suggests that the bound on
weak coloring numbers should be local in some sense as well. To this end, instead of bounding $wcol_r(G)$, we bound $wcol_r(G, S)$, where $S$ is a hitting set for $\mathcal{F}$, that is $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$. A result in this spirit, that corresponds to excluding every $\mathcal{F}$-rich model of an edgeless graph $X$, is already present in [2]. We restate this result below with adjusted notations.

**Lemma 7.** There exists a function $\delta$ such that for all positive integers $k, d$, for every connected $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if there are no $d$ pairwise vertex-disjoint subgraphs in $\mathcal{F}$, then there exists $S \subseteq V(G)$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) $wcol_r(G, S) \leq \delta(k, d) \cdot r$ for every positive integer $r$.

Pushing this idea further, we show the following technical version of Theorem 5, which can be seen as the induction setup.

**Theorem 8.** Let $k$ and $t$ be positive integers with $t \geq 2$. Let $X$ be a graph with $rtd_2(X) \leq t$. There exists an integer $c(t, X, k)$ such that for every connected $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $X$, then there exists $S \subseteq V(G)$ such that

(A) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(B) $G[S]$ is connected;

(C) $wcol_r(G, S) \leq c(t, X, k) \cdot r^{t-1} \log r$ for every integer $r$ with $r \geq 2$.

To recover Theorem 5 from this last statement, apply it for a family $\mathcal{F}$ containing each one-vertex subgraph of $G$. Then (A) implies that $S = V(G)$, and so, $wcol_r(G) = wcol_r(G, S) \leq c(t, X, k) \cdot r^{t-1} \log r$ by (C). The assumption that $G$ is $K_k$-minor-free is necessary: for every positive integer $n$, if $\mathcal{F}$ is the family of all the subgraphs of $K_n$ with more than $\frac{n}{2}$ vertices, then $K_n$ has no $\mathcal{F}$-rich model of $K_2$, but every hitting set $S$ of $\mathcal{F}$ satisfies $wcol_r(G, \bar{S}) \geq \frac{n}{2}$ for every nonnegative integer $r$, which is not bounded by a function of $r$. Item (B) is a technical condition that supports the induction.

The proof of Theorem 8 is by induction on $t$. Within the inductive step, given the result for all $X$ with $rtd_2(X) = t-1$ we argue that the result holds for graphs of rooted 2-treedepth equal $t$. First, we prove it for graphs of the form $K_1 \oplus X$ where $rtd_2(X) = t-1$. Let $G$ be a $K_1 \oplus X$-minor-free graph. Let $u$ be a vertex of $G$ and let $\mathcal{F}$ be the family of all the connected subgraphs $H$ of $G - \{u\}$ that contain a neighbor of $u$ in $G$. Then observe that any $\mathcal{F}$-rich model $(B_x | x \in V(X))$ of $X$ in $G - \{u\}$ yields a model $(C_x | x \in V(X) \cup \{s\})$ of $K_1 \oplus X$ defined by $C_x = B_x$ for every $x \in V(X)$ and $C_s = \{u\}$ – see Figure 4. Therefore, $G - \{u\}$ has no $\mathcal{F}$-rich model of $X$. Hence, choosing $\mathcal{F}$ carefully, we can deduce that $G$ has no $\mathcal{F}$-rich model of $X$ knowing that $G$ has no model of $K_1 \oplus X$. This technique will allow us to prove Theorem 8 for $K_1 \oplus X$, assuming the result for $X$ (see Claim 1 and Claim 2 in the proof of Theorem 8). When we have the result for graphs of the form $K_1 \oplus X$, we follow the inductive definition of rooted 2-treedepth and conclude the full statement of Theorem 8, see Claim 3.

Here is the summary of the plan of the proof of Theorem 8, with the bounds on $wcol_r(G, S)$ obtained at each step:
<figure><img src="image_5.png" /><figcaption>FIGURE 4. On the left-hand side, we depict an $\mathcal{F}$-rich model of $X$, where $X$ is a cycle on 8 vertices and $\mathcal{F}$ is the family of all nonnull connected subgraphs of $G - \{u\}$ containing a neighbor of $u$ in $G$. On the right-hand side, we show how to construct, given an $\mathcal{F}$-rich model of $Y$, a model of $K_1 \oplus X$.</figcaption></figure>

1. **Pre-base case:** $\mathrm{rtd}_2(X) \le 1$, i.e. $X$ has no edges; Lemma 17. $O(r)$

2. **Base case:** $\mathrm{rtd}_2(X) \le 2$, i.e. $X$ is a forest; Section 5.
   a. $X$ is a star; Lemmas 30 and 31. $O(r \log r)$
   b. $X$ is a forest; Lemma 33. $O(r \log r)$

3. **Induction:** $\mathrm{rtd}_2(X) \le t$, assuming the result for $t-1$; Section 6.
   a. $X = K_1 \oplus Y$ for some $Y$ with $\mathrm{rtd}_2(Y) \le t-1$; Claims 1 and 2. $O(r^{t-1} \log r)$
   b. $X$ is any graph with $\mathrm{rtd}_2(X) \le t$; Claim 3. $O(r^{t-1} \log r)$

The logarithmic factor appears already in the base case. This phenomenon can be explained as follows. Graphs excluding a fixed tree as a minor have bounded pathwidth [19], and it is known that paths have logarithmic weak coloring numbers (see [13] or Figure 10). Combining these ideas, one can show that graphs excluding a fixed tree as a minor have logarithmic weak coloring numbers. Here, we are working in the more general setting of graphs with no $\mathcal{F}$-rich model of a fixed tree, and so we do not have bounded pathwidth. However, using a similar strategy together with Lemma 7, we prove in our base case an $O(r \log r)$ bound for weak coloring numbers of a hitting set of $\mathcal{F}$, in a $K_k$-minor-free graphs with no $\mathcal{F}$-rich model of a fixed tree.

The proof of Theorem 6 is very similar, except that a factor $O(r)$ is saved in the first step. This comes from the fact that for every graph $G$, for every family $\mathcal{F}$ of connected subgraphs of $G$, if there are no $d+1$ disjoint members of $\mathcal{F}$, then there exists a hitting set $S \subseteq V(G)$ of $\mathcal{F}$ of size at most $d \cdot (\mathrm{tw}(G) + 1)$. In particular, $\mathrm{wcol}_r(G, S) \le |S| \le d \cdot (\mathrm{tw}(G) + 1)$ for every nonnegative integer $r$. This fact (see Lemma 35) will replace Lemma 7 in the first step of the proof, which improves by a factor $O(r)$ the bound obtained in the more general setting of $K_k$-minor-free graphs. In the proof of Theorem 5, for technical reasons we keep as an invariant that $G[S]$ is connected. The techniques used in the proof Theorem 6 force us to relax this condition slightly. Now, we assert that for every component $C$ of $G-S$, $N_G(V(C))$ intersects only few components of $G-V(C)$. This makes the proof slightly more technical. However, the main ideas are the same, and substantial parts of the proofs overlap.

2.5. **Organisation of the paper.** In Section 3, we introduce notation and some simple properties that will be used throughout the paper. In Section 4, we prove several properties of the
rooted 2-treedepth, and show its connection with the construction {$G_{r,t}$}$_{r,t\ge0}$ [8]. In Section 5, we prove the base case of Theorem 8 when X is a forest. In Section 6, we prove Theorem 8. Finally, in Section 7, we prove Theorem 6 with the same method.

3. PRELIMINARIES

Let $G$ be a graph and let $A, B, Z \subseteq V(G)$. We say that $Z$ separates $A$ and $B$ in $G$ if no component of $G-Z$ intersects both $A$ and $B$.

A collection $\mathcal{P}$ of subsets of a non-empty set $S$ is a *partition* of $S$ if elements of $\mathcal{P}$ are non-empty, pairwise disjoint, and $\cup \mathcal{P} = S$. A sequence $(P_0, \dots, P_m)$ of subsets of a set $S$ is an *ordered partition* of $S$ if $\{P_i\}_{i \in \{0, \dots, m\}}$ is a partition of $S$. Given a graph $G$ and a partition $\mathcal{P}$ of $V(G)$, the *quotient graph* $G/\mathcal{P}$ is the graph with the vertex set $\mathcal{P}$ and two distinct $P, P' \in \mathcal{P}$ are adjacent in $G/\mathcal{P}$ if there are $u \in P$ and $u' \in P'$ such that $uu'$ is an edge in $G$.

A *layering* of a graph $G$ is an ordered partition $(P_0, \dots, P_l)$ of $V(G)$ such that for every edge $uv$ in $G$ either there is $i \in \{0, \dots, l\}$ with $u, v \in P_i$ or there is $i \in \{0, \dots, l-1\}$ with $u \in P_i$ and $v \in P_{i+1}$. A *tree partition* of a graph $G$ is a pair $(T, \mathcal{P})$, where $T$ is a tree and $\mathcal{P} = (P_x \mid x \in V(T))$ is a partition of $V(G)$ such that for every edge $uv$ in $G$ either there is $x \in V(T)$ with $u, v \in P_x$ or there is an edge $xy$ in $T$ with $u \in P_x$ and $v \in P_y$.

Let $G$ be a graph. For $X, Y \subseteq V(G)$, an $X-Y$ *path* is a path in $G$ that is either a one-vertex path with the vertex in $X \cap Y$ or a path with one endpoint in $X$ and the other endpoint in $Y$ such that no internal vertices are in $X \cup Y$. When $u, v \in V(G)$, instead of $\{u\}-\{v\}$ path we write $u-v$ path for short. The *length* of a path $P$ is the number of edges of $P$. A path $P$ is a *geodesic* in $G$ if it is a shortest path between its endpoints in $G$. The *distance* between two vertices $u$ and $v$ in $G$, denoted by $\text{dist}_G(u, v)$, is the length of a $u-v$ geodesic in $G$ when it exists, and $+\infty$ otherwise. Let $u$ be a vertex of $G$. The *neighborhood* of $u$ in $G$, denoted by $N_G(u)$, is the set $\{v \in V(G) \mid uv \in E(G)\}$. For every set of vertices $X$ of $G$, let $N_G(X) = \cup_{u \in X} N_G(u) - X$. For every positive integer $r$, we denote by $N_G^r[u] = \{v \in V(G) \mid \text{dist}_G(u, v) \le r\}$. We omit $G$ in the subscripts when it is clear from the context. The following lemma is folklore, see e.g. [2, Lemma 23] for a proof.

**Lemma 9.** Let $G$ be a graph and $r$ be a nonnegative integer. For every geodesic $Q$ in $G$ and for every vertex $v \in V(G)$,

$$|N^r[v] \cap V(Q)| \le 2r + 1.$$

An *ordering* $\sigma$ of a finite set $E$ is a sequence $(x_1, \dots, x_{|E|})$ of all the elements of $E$. For all $x, y \in E$, we write $x \leq_{\sigma} y$ when there are $i, j \in [|E|]$ such that $x_i = x, x_j = y$, and $i \leq j$. We also write $\min_{\sigma} E = x_1$ and $\max_{\sigma} E = x_{|E|}$. When $F \subseteq E$, we write $\sigma|_F$ for the *restriction* of $\sigma$ to $F$ that is defined as the ordering of $F$ such that $x \leq_{\sigma|_F} y$ if and only if $x \leq_{\sigma} y$ for all $x, y \in F$. For every nonempty $F \subseteq E$, we define $\min_{\sigma} F = \min_{\sigma|_F} F$ and $\max_{\sigma} F = \max_{\sigma|_F} F$. For all $F, F' \subseteq E$, we write $F <_{\sigma} F'$ whenever for all $x \in F$ and $y \in F'$, we have $x <_{\sigma} y$. If $\sigma'$ is an ordering of $F \subseteq E$, we say that $\sigma$ *extends* $\sigma'$ if $\sigma|_F = \sigma'$.

When $H$ is a subgraph of a graph $G$ and $\mathcal{F}$ is a family of subgraphs of $G$, we denote by $\mathcal{F}|_H$ the family $\{F \in \mathcal{F} \mid F \subseteq H\}$.
Next, we state a bunch of simple observations concerning the notion of weak coloring numbers in the version presented above.

**Observation 10.** Let $G$ be a graph and let $S \subseteq V(G)$. Let $G'$ consist of all the components of $G$ that contain a vertex from $S$. For every nonnegative integer $r$, we have

$$wcol_r(G, S) = wcol_r(G', S).$$

**Observation 11.** Let $G$ be a graph, $S \subseteq V(G)$, and $C$ be the family of components of $G$. For every nonnegative integer $r$, we have

$$wcol_r(G, S) = \max_{C \in \mathcal{C}} wcol_r(C, S \cap V(C)).$$

**Observation 12.** Let $G$ be a graph and let $S, S' \subseteq V(G)$. For every nonnegative integer $r$, we have

$$wcol_r(G, S \cup S') \le wcol_r(G, S) + wcol_r(G - S, S' - S).$$

Observations 10 and 11 are clear from the definition and to see Observation 12, it suffices to order all the vertices of $S$ before all the vertices of $S'$.

Geodesics are a useful tool when bounding weak coloring numbers. For instance, Lemma 9 implies the following.

**Observation 13.** Let $G$ be a graph, $S \subseteq V(G)$, $\ell$ be a positive integer, and $Q_1, \dots, Q_\ell$ be geodesics in $G$. For every nonnegative integer $r$, we have

$$wcol_r(G, S \cup V(Q_1) \cup \dots \cup V(Q_\ell)) \le wcol_r(G, S) + \ell(2r + 1).$$

This inequality is witnessed by an ordering of $S \cup V(Q_1) \cup \dots \cup V(Q_\ell)$ obtained from the ordering $\sigma$ of $S$ witnessing $wcol_r(G, S)$ by putting vertices from $V(Q_1) \cup \dots \cup V(Q_\ell) - S$ arbitrarily.

Note that $wcol_r(G, S)$ is not monotone with respect to $S$. For example, let $G$ be a star with the root $v$. We have $V(G) - \{v\} \subseteq V(G)$, however, $wcol_1(G, V(G) - \{v\}) = |V(G)|$ and $wcol_1(G, V(G)) = 2$. On the other hand, our version of weak coloring numbers is monotone in the following sense.

**Observation 14.** Let $G$ be a graph, $S \subseteq V(G)$, and $U \subseteq V(G)$. For every nonnegative integer $r$, we have

$$wcol_r(G - U, S - U) \le wcol_r(G, S).$$

The ideas of Observations 13 and 14 can be combined to obtain another property.

**Observation 15.** Let $G$ be a graph, $S \subseteq V(G)$, $U \subseteq V(G)$, $\ell$ be a positive integer, and $Q_1, \dots, Q_\ell$ be geodesics in $G$. For every nonnegative integer $r$, we have

$$wcol_r(G - U, (S \cup V(Q_1) \cup \dots \cup V(Q_\ell)) - U) \le wcol_r(G - U, S - U) + \ell(2r + 1).$$

Finally, we can decide to place a fixed subset $A$ of vertices first in the ordering and then consider the geodesic paths in the remaining graph $G - A$. This turns out to be an important trick.
**Observation 16.** Let $G$ be a graph, $A \subseteq V(G)$, $\ell$ be a positive integer, and $Q_1, \dots, Q_\ell$ be geodesics in $G-A$. For every nonnegative integer $r$, we have

$$ wcol_r(G, A \cup V(Q_1) \cup \dots \cup V(Q_\ell)) \le |A| + \ell(2r + 1). $$

To see that the observation holds, we just take an arbitrary ordering of $A \cup V(Q_1) \cup \dots \cup V(Q_\ell)$ with vertices of $A$ preceding vertices of $V(Q_1) \cup \dots \cup V(Q_\ell)$.

Now, we present one of the key basic tools in the proof of Theorem 5.

**Lemma 17 (Lemma 7 restated).** There exists a function $\delta$ such that for all positive integers $k, d$, for every connected $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, either there are $d$ pairwise vertex-disjoint subgraphs in $\mathcal{F}$, or there exists $S \subseteq V(G)$ such that

(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) $wcol_r(G, S) \le \delta(k, d) \cdot r$ for every positive integer $r$.

Lemma 17 is a consequence of the following statement from [2], which relies on the Graph Minor Structure Theorem by Robertson and Seymour.

**Lemma 18 ([2, Lemma 21]).** There exists a function $\gamma$ such that for all positive integers $k, d$, for every $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$ either

(1) there are $d$ pairwise vertex-disjoint subgraphs in $\mathcal{F}$, or

(2) there exists $A \subseteq V(G)$ such that $|A| \le (d-1)\gamma(k)$, and a subgraph $X$ of $G$, where $X$ is the union of at most $(d-1)^2\gamma(k)$ geodesics in $G-A$, and for every $F \in \mathcal{F}$ we have $V(F) \cap (V(X) \cup A) \ne \emptyset$.

*Proof of Lemma 17.* Let $\delta(k, d) = 12(d-1)^2\gamma(k)$ where $\gamma$ is the function from Lemma 18. Let $G$ be a $K_k$-minor-free graph and let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$. Suppose that there are no $d$ pairwise disjoint members of $\mathcal{F}$, and hence, Lemma 18.(2) holds, yielding $A \subseteq V(G)$ and a subgraph $X$ of $G$ such that $|A| \le (d-1)\gamma(k)$ and $X$ is the union of at most $(d-1)^2\gamma(k)$ geodesics in $G-A$. Note that $G[A \cup V(X)]$ has at most $|A| + (d-1)^2\gamma(k)$ components. Let $Q_1, \dots, Q_\ell$ be a family of at most $(d-1)\gamma(k) + (d-1)^2\gamma(k) - 1$ geodesics in $G$ such that the set $S = A \cup V(X) \cup \bigcup_{i \in [\ell]} V(Q_i)$ induces a connected subgraph in $G$. In particular, $\ell \le 2(d-1)^2\gamma(k)$. By Observations 13 and 16, for every positive integer $r$,

$$ \begin{aligned} wcol_r(G, S) &\le wcol_r(G, A \cup V(X)) + \ell(2r + 1) \\ &\le |A| + (d-1)^2\gamma(k)(2r + 1) + \ell(2r + 1) \\ &\le (d-1)\gamma(k) + (d-1)^2\gamma(k)(2r + 1) + 2(d-1)^2\gamma(k)(2r + 1) \\ &\le 4(d-1)^2\gamma(k)(2r + 1) \le \delta(k, d)r. \end{aligned} \quad \square $$

It is easy to derive an upper bound on weak coloring numbers of trees. It suffices to root a given tree and order the vertices in an elimination order. Namely, an *elimination ordering* of a tree $T$ rooted in $s \in V(T)$ is an ordering $(x_1, \dots, x_{|V(T)|})$ of $V(T)$ such that $x_1 = s$ and for every $i \in \{2, \dots, |V(T)|\}$, $N(x_i) \cap \{x_j \mid j \in [i-1]\} = \{y\}$ where $y$ is the parent of $x$. Note that in such an ordering a vertex weakly reaches only its ancestors. See Figure 5.
<figure><img src="image_6.png" /><figcaption>FIGURE 5. An example of an eliminating ordering of a complete binary tree of height 3.</figcaption></figure>

**Observation 19.** Let $T$ be a tree. For every positive integer $r$, we have

$$wcol_r(T) \le r + 1.$$

More precisely, for every elimination ordering $\sigma$ of $T$, for every $u \in V(T)$, and for every positive integer $r$ we have

$$WReach_r[T, \sigma, u] \subseteq A_{r,x}$$

where $A_{r,x}$ is the set of ancestors of $x$ in distance at most $r$. Note that $|A_{r,x}| \le r + 1$.

Note that this idea can be generalized to elimination orderings of tree decompositions – see [8].

## 4. ROOTED 2-TREEDEPTH

First, we recall the definition of rooted 2-treedepth. For every graph $G$,

(r1) $rtd_2(G) = 0$ if $G$ is the null graph,

(r2) $rtd_2(G) = 1$ if $G$ is a one vertex graph, and otherwise

(r3) $rtd_2(G)$ is the minimum of $\max\{rtd_2(A), rtd_2(B - V(A)) + |V(A) \cap V(B)|\}$ over all separations $(A, B)$ of $G$ of order at most one with $V(A) \neq \emptyset$ and $V(B) - V(A) \neq \emptyset$.

As mentioned in Section 2.1, the following properties are direct consequences of the definition.

(r4) $rtd_2(G)$ is the maximum of $rtd_2(C)$ over all components $C$ of $G$ when $G$ is not connected,

(r5) $rtd_2(G)$ is the minimum of $rtd_2(G - v) + 1$ over all vertices $v$ of $G$ when $G$ consists of one block,

(r6) $rtd_2(G)$ is the minimum of $\max\{rtd_2(A), rtd_2(B - V(A)) + 1\}$ over all separations $(A, B)$ of $G$ of order one with $V(A) \cap V(B)$ consisting of a cut-vertex, when $G$ is connected and consists of more than one block.

(r7) $rtd_2(G) \le 1 + rtd_2(G - u)$.

(r8) $rtd_2(G) \le \max\{2, rtd_2(G - u)\}$ for every $u \in V(G)$ of degree at most 1.

As an illustration of the definition of rooted 2-treedepth, we characterize graphs having the values of $rtd_2$ in $\{1, 2\}$. First, note the following straightforward observation.
**Observation 20.** For every graph $G$, we have $\mathrm{rtd}_2(G) \le 1$ if and only if $G$ has no edges.

Next, we show that for every tree $T$, we have $\mathrm{rtd}_2(T) \le 2$. We proceed by induction on the number of vertices of $T$. For the base case, $\mathrm{rtd}_2(K_1) = 1 \le 2$. In general, if $x$ is a leaf of $T$ whose parent is $y$, then the separation $(T - x, T[\{x, y\}])$ witnesses $\mathrm{rtd}_2(T) \le \max\{\mathrm{rtd}_2(T - x), \mathrm{rtd}_2(K_1) + 1\} \le 2$.

We are about to show that $\mathrm{rtd}_2$ is minor-monotone. Note that this yields a characterization of graphs with $\mathrm{rtd}_2$ at most two. Namely, $\mathrm{rtd}_2(G) \le 2$ if and only if $G$ is a forest. Indeed, observe that $\mathrm{rtd}_2(K_3) = 3$.

**Observation 21.** For every graph $G$, we have $\mathrm{rtd}_2(G) \le 2$ if and only if $G$ is a forest.

**Lemma 22.** For all graphs $G, H$, if $H$ is a minor of $G$, then

$$ \mathrm{rtd}_2(H) \le \mathrm{rtd}_2(G). $$

*Proof.* We proceed by induction on $|V(G)|$. When $|V(G)| \le 1$, then the assertion holds. Hence, let $G$ be a graph on at least two vertices. There is a separation $(A, B)$ of $G$ of order at most one such that $\mathrm{rtd}_2(G) = \max\{\mathrm{rtd}_2(A), \mathrm{rtd}_2(B - V(A)) + |V(A) \cap V(B)|\}, V(B) - V(A) \ne \emptyset$, and $V(A) \ne \emptyset$. In particular, $\mathrm{rtd}_2(A) \le \mathrm{rtd}_2(G)$ and $\mathrm{rtd}_2(B - V(A)) + |V(A) \cap V(B)| \le \mathrm{rtd}_2(G)$.

We claim that $H$ has a separation $(A', B')$ such that $A'$ is a minor of $A$, $B' - V(A')$ is a minor of $B - V(A)$, and $|V(A') \cap V(B')| \le |V(A) \cap V(B)|$. Indeed, let $(C_x | x \in V(H))$ be a model of $H$ in $G$, and let

$$ A' = H[\{x \in V(H) | C_x \cap V(A) \ne \emptyset\}] $$

$$ B' = H[\{x \in V(H) | C_x \cap V(B) \ne \emptyset\}]. $$

Note that $(A', B')$ is a separation of $H$. Moreover, since $|V(A) \cap V(B)| \le 1$, $A'$ is a minor of $A$ and $B' - V(A')$ is a minor of $B - V(A)$. Moreover, by construction $|V(A') \cap V(B')| \le |V(A) \cap V(B)|$. Observe that since $|V(A') \cap V(B')| \le 1$, $(C_x \cap V(A) | x \in V(A'))$ is a model of $A'$ in $A$, and $(C_x \cap (V(B) - V(A)) | x \in V(B') - V(A'))$ is a model of $B' - V(A')$ in $B$.

Since $V(B) - V(A) \ne \emptyset$, and $V(A) \ne \emptyset$, we have $|V(A)| < |V(G)$ and $|V(B - V(A))| < |V(G)|$. Therefore, by induction hypothesis, since $A'$ is a minor of $A$ and $B' - V(A')$ is a minor of $B - V(A)$, $\mathrm{rtd}_2(A') \le \mathrm{rtd}_2(A)$ and $\mathrm{rtd}_2(B' - V(A')) \le \mathrm{rtd}_2(B - V(A))$. We deduce that

$$ \mathrm{rtd}_2(H) \le \max\{\mathrm{rtd}_2(A'), \mathrm{rtd}_2(B' - V(A')) + |V(A') \cap V(B')|\} $$

$$ \le \max\{\mathrm{rtd}_2(A), \mathrm{rtd}_2(B - V(A)) + |V(A) \cap V(B)|\} $$

$$ = \mathrm{rtd}_2(G). \quad \square $$

It is evident from the definitions that the parameters $\mathrm{td}_2$ and $\mathrm{rtd}_2$ are closely related. Indeed, for instance, $\mathrm{td}_2$ is minor-monotone too – one can see this by following the above proof with a slight modification (we do not give an explicit proof since we never use this fact). In the next part of this section, we discuss relations between $\mathrm{rtd}_2$ and $\mathrm{td}_2$. Namely, we show that the two parameters are linearly tied.

**Lemma 23.** For every graph $G$ with at least one edge,

$$ \mathrm{td}_2(G) \le \mathrm{rtd}_2(G) \le 2 \mathrm{td}_2(G) - 2. $$
Proof. First, we prove that $\mathrm{td}_2(G) \le r\mathrm{td}_2(G)$ for every graph $G$. We proceed by induction on $|V(G)|$. When $G$ is a null graph, we have $\mathrm{td}_2(G) = r\mathrm{td}_2(G) = 0$ and when $G$ is a one-vertex graph, we have $\mathrm{td}_2(G) = r\mathrm{td}_2(G) = 1$. Thus, we assume that $|V(G)| \ge 2$. If $G$ consists of one block, then by (r5) and induction hypothesis,

$$ \mathrm{td}_2(G) = \min_{v \in V(G)} \mathrm{td}_2(G - v) + 1 \le \min_{v \in V(G)} r\mathrm{td}_2(G - v) + 1 = r\mathrm{td}_2(G). $$

If $G$ consists of blocks $B_1, \dots, B_k$ for $k > 1$, then by induction hypothesis,

$$ \mathrm{td}_2(G) = \max_{i \in [k]} \mathrm{td}_2(B_i) \le \max_{i \in [k]} r\mathrm{td}_2(B_i) \le r\mathrm{td}_2(G). $$

Now, we prove the other inequality for every graph $G$ with at least one edge. We again proceed by induction on $|V(G)|$. If $\mathrm{td}_2(G) = 2$, then $G$ is a forest with at least one edge, and so as mentioned earlier $r\mathrm{td}_2(G) = \mathrm{td}_2(G) = 2$. Now assume that $\mathrm{td}_2(G) \ge 3$, and so in particular $|V(G)| \ge 3$, and that the result holds for smaller graphs. In particular, for every nonnull graph $H$ with $|V(H)| < |V(G)|$, either $H$ has no edge and so $r\mathrm{td}_2(H) = \mathrm{td}_2(H) = 1$, or $r\mathrm{td}_2(H) \le 2\mathrm{td}_2(H) - 2$. In both cases, $r\mathrm{td}_2(H) \le \max\{1, 2\mathrm{td}_2(H) - 2\}$. There is a separation $(A, B)$ of $G$ of order at most one such that $r\mathrm{td}_2(G) = \max\{r\mathrm{td}_2(A), r\mathrm{td}_2(B - V(A)) + |V(A) \cap V(B)|\}, V(B) - V(A) \ne \emptyset$, and $V(A) \ne \emptyset$. If $|V(A) \cap V(B)| = 0$, then $B - V(A) = B$ and so

$$ \begin{aligned} r\mathrm{td}_2(G) &= \max\{r\mathrm{td}_2(A), r\mathrm{td}_2(B)\} \\ &\le \max\{\max\{1, 2\mathrm{td}_2(A) - 2\}, \max\{1, 2\mathrm{td}_2(B) - 2\}\} \\ &= \max\{1, 2\max\{\mathrm{td}_2(A), \mathrm{td}_2(B)\} - 2\} \\ &= 2\mathrm{td}_2(G) - 2. \end{aligned} $$

Therefore, we assume that $|V(A) \cap V(B)| = 1$ and $V(A) \cap V(B) = \{u\}$. There exists $v \in V(B)$ such that $\mathrm{td}_2(B - v) = \mathrm{td}_2(B) - 1$. Then, by (r7),

$$ \begin{aligned} r\mathrm{td}_2(B - u) &\le r\mathrm{td}_2(B - u - v) + 1 \le r\mathrm{td}_2(B - v) + 1 \\ &\le \max\{1, 2\mathrm{td}_2(B - v) - 2\} + 1 \\ &= \max\{2, 2\mathrm{td}_2(B - v) - 1\} \\ &\le \max\{2, 2\mathrm{td}_2(B) - 3\}. \end{aligned} $$

Finally, since $\mathrm{td}_2(G) \ge 3$,

$$ \begin{aligned} r\mathrm{td}_2(G) &\le \max\{r\mathrm{td}_2(A), r\mathrm{td}_2(B - u) + 1\} \\ &\le \max\{\max\{1, 2\mathrm{td}_2(A) - 2\}, \max\{2, 2\mathrm{td}_2(B) - 3\} + 1\} \\ &= \max\{3, 2\mathrm{td}_2(A) - 2, 2\mathrm{td}_2(B) - 3 + 1\} \\ &\le \max\{3, 2\mathrm{td}_2(G) - 2\} \\ &= 2\mathrm{td}_2(G) - 2. \end{aligned} $$

□

The bounds in Lemma 23 are tight. Indeed, for every positive integer $n$, we have $\mathrm{td}_2(K_n) = r\mathrm{td}_2(K_n) = n$, which witnesses that the first inequality is tight. For the second one, see Lemma 25, which we precede with a simple observation. Note that this observation is also true for $\mathrm{td}_2$, namely, $\mathrm{td}_2(K_1 \oplus G) = 1 + \mathrm{td}_2(G)$ – again, the proof is very similar and we omit it.

**Observation 24.** For every graph $G$,

$$ r\mathrm{td}_2(K_1 \oplus G) = 1 + r\mathrm{td}_2(G). $$
**Proof.** Let $G$ be a graph and let $s$ the vertex of $K_1$ in $K_1 \oplus G$. By definition, $\mathrm{rtd}_2(K_1 \oplus G) \le 1 + \mathrm{rtd}_2(G)$. For the other inequality, we proceed by induction on $\mathrm{rtd}_2(G)$. The assertion is clear when $G$ is the null graph, thus, assume that $G$ is not the null graph. If $G$ is not connected, then $\mathrm{rtd}_2(G) = \mathrm{rtd}_2(C)$ for some component $C$ of $G$, and since $\mathrm{rtd}_2(K_1 \oplus G) \ge \mathrm{rtd}_2(K_1 \oplus C)$, it suffices to show $\mathrm{rtd}_2(K_1 \oplus C) \ge 1 + \mathrm{rtd}_2(C)$. Therefore, we assume that $G$ is connected. Since $K_1 \oplus G$ is also connected, there is a separation $(A, B)$ of $K_1 \oplus G$ of order one such that $\mathrm{rtd}_2(G) = \max\{\mathrm{rtd}_2(A), \mathrm{rtd}_2(B - V(A)) + 1\}, V(B) - V(A) \ne \emptyset$, and $V(A) \ne \emptyset$. Since $s$ is adjacent to all other vertices in $K_1 \oplus G$, the only possibility is that $V(A) = \{s\}$ and $V(B) = V(K_1 \oplus G)$. It follows that $B - V(A)$ contains a subgraph isomorphic to $G$, and thus, $\mathrm{rtd}_2(K_1 \oplus G) \ge 1 + \mathrm{rtd}_2(B - V(A)) \ge 1 + \mathrm{rtd}_2(G)$. $\square$

**Lemma 25.** For every integer $k$ with $k \ge 2$, there is a graph $G$ with $\mathrm{td}_2(G) \le k$ and $\mathrm{rtd}_2(G) \ge 2k - 2$.

**Proof.** We define inductively graphs $H_{k,\ell}$ with two distinguished vertices $u_{k,\ell}$ and $v_{k,\ell}$ for every integers $k, \ell$ with $k, \ell \ge 2$. For $k = 2$, $H_{k,\ell}$ is a path on $\ell$ vertices and $u_{k,\ell}, v_{k,\ell}$ are its endpoints. For $k > 3$, $H_{k,\ell}$ is obtained from two disjoint copies $H_1, H_2$ of $K_1 \oplus H_{k-1,\ell}$ by identifying the copy of $v_{k-1,\ell}$ in $H_1$ with the copy of $u_{k-1,\ell}$ in $H_2$. The vertices $u_{k,\ell}, v_{k,\ell}$ are then respectively the copy of $u_{k-1,\ell}$ in $H_1$ and the copy of $v_{k-1,\ell}$ in $H_2$. See Figure 6.

By induction on $k$, we show that $\mathrm{td}_2(H_{k,\ell}) \le k$ and $\mathrm{rtd}_2(H_{k,\ell}) \ge 2k - 2$ for all integers $k, \ell$ with $\ell \ge k \ge 2$. When $k = 2$, $H_{2,\ell}$ is a path on at least two vertices and so $\mathrm{td}_2(H_{2,\ell}) = \mathrm{rtd}_2(H_{2,\ell}) = 2$. Now suppose that $k > 2$. First, observe that $H_{k,\ell}$ has exactly two blocks $H_1, H_2$, both isomorphic to $K_1 \oplus H_{k-1,\ell}$. Hence, $\mathrm{td}_2(H_{k,\ell}) \le \mathrm{td}_2(K_1 \oplus H_{k-1,\ell}) \le 1 + \mathrm{td}_2(H_{k-1,\ell}) \le k$ by induction hypothesis. Let $v$ be the unique cut-vertex of $H_{k,\ell}$. Since $H_{k,\ell}$ is connected and consists of more than one block, by (r6), there is a separation $(A, B)$ of $H_{k,\ell}$ such that $V(A) \cap V(B) = \{v\}$ and $\mathrm{rtd}_2(H_{k,\ell}) = \max\{\mathrm{rtd}_2(A), \mathrm{rtd}_2(B - v) + 1\}$. It follows that the graph $B - v$ contains $K_1 \oplus H_{k-1,\ell-1}$ as a subgraph, and so, applying Observation 24,

$$ \mathrm{rtd}_2(H_{k,\ell-1}) \ge \mathrm{rtd}_2(B - v) + 1 \ge \mathrm{rtd}_2(K_1 \oplus H_{k-1,\ell-1}) + 1 \ge \mathrm{rtd}_2(H_{k-1,\ell-1}) + 2 \ge 2k - 2. $$

This concludes the proof of the lemma. $\square$

<figure><img src="image_7.png" /></figure>

<figure><img src="image_8.png" /><figcaption>FIGURE 6. The proof of Lemma 25 implies that $\mathrm{td}_2(H_{4,4}) \le 4$ and $\mathrm{rtd}_2(H_{4,4}) \ge 6$.</figcaption></figure>

In Section 1, we mentioned several times the construction given in [8]. Let us now finally introduce it properly, and later show the equivalent description of rooted 2-treedepth using this construction.
Let $d$ be a positive integer, let $B, H$ be two graphs, and let $u$ be a vertex of $H$. Recall that $L_d(B, H, u)$ is the graph obtained in the following process. Take a copy of $B$ and $d|V(B)|$ copies of $H$. Label the latter $H_{i,x}$ for each $i \in [d]$ and $x \in V(B)$. Next, for each $x \in V(B)$ identify $x$ and $u$ in each $H_{i,x}$ for $i \in [d]$. See Figure 2.

Moreover, for all nonnegative integers $r, t$ the graph $G_{r,t}$ is defined recursively by

$$ \begin{cases} G_{0,t} = G_{r,0} = K_1 \\ G_{r,t} = L_{(r+t)}(G_{r-1,t}, K_1 \oplus G_{r,t-1}, u) \text{ if } r, t > 0 \end{cases} $$

where $u$ is the vertex of $K_1$ in $K_1 \oplus G_{r,t-1}$.

**Lemma 26.** For every graph $G$ with at least one edge, $\text{rtd}_2(G)$ is equal to the least $t$ such that there exists a nonnegative integer $r$ with $G \subseteq G_{r,t-1}$.

*Proof.* First, we show that for every $G$ with at least one edge and every integer $t \ge 0$ such that there exists $r \ge 0$ with $G \subseteq G_{r,t-1}$, we have $\text{rtd}_2(G) \le t$. Since $G$ has an edge, we have $t \ge 2$. By Lemma 22, it is enough to show that $\text{rtd}_2(G_{r,t-1}) \le t$ for all integers $r, t$ with $r \ge 0$ and $t \ge 2$. We proceed by induction on $t+r$. If $t=2$ or $r=0$, then $G_{r,t-1}$ is a tree and the result follows. Now suppose $t \ge 3, r \ge 1$. By the definition of $G_{r,t-1}$, there is a sequence $H_0, \dots, H_m$ of graphs such that $H_0 = G_{r-1,t-1}$, $H_m = G_{r,t-1}$, and for every $i \in [m]$, $H_i$ contains a block $B_i$ containing a unique cut vertex $r_i$ of $H_i$ in $B_i$, which is such that $B_i - r_i$ is isomorphic to $G_{r,t-2}$ and $H_{i-1} = H_i - V(B_i - r_i)$.

We claim that $\text{rtd}_2(H_i) \le t$ for every $i \in \{0, \dots, m\}$. We proceed by induction on $i$. The main induction hypothesis gives $\text{rtd}_2(H_0) = \text{rtd}_2(G_{r-1,t-1}) \le t$. Now let $i \in [m]$. The graph $H_i$ has a block $B_i$ containing a unique cut vertex $r_i$ of $H_i$ such that $B_i - r_i$ is isomorphic to $G_{r,t-2}$ and $H_{i-1} = H_i - V(B_i - r_i)$. Then $(H_{i-1}, B_i)$ is a separation of $H_i$ of order at most one, and hence by induction hypothesis $\text{rtd}_2(H_i) \le \max\{\text{rtd}_2(H_{i-1}), \text{rtd}_2(G_{r,t-2}) + 1\} \le t$. For $i = m$, this proves that $\text{rtd}_2(G_{r,t-1}) \le t$ as asserted.

Next, we prove the opposite implication, i.e., if $\text{rtd}_2(G) \le t$ then there exists $r \ge 0$ such that $G \subseteq G_{r,t-1}$. We proceed by induction on $(t, |V(G)|)$ in the lexicographic order. Since $G$ has an edge, we must have $|V(G)| \ge 2$ and $t \ge 2$. Suppose that $t=2$, and so, $\text{rtd}_2(G) \le 2$, which implies by Observation 21 that $G$ is a forest. There is a vertex $x$ of $G$ of degree at most one. Since $\text{rtd}_2(G-x) \le \text{rtd}_2(G) \le t$, by induction hypothesis, there exists a nonnegative integer $r$ such that $G-x \subseteq G_{r,1}$, and so $G \subseteq G_{r+1,1}$.

Now, suppose that $t \ge 3$. There is a separation $(A, B)$ of $G$ of order at most one such that $\text{rtd}_2(A) \le \text{rtd}_2(G)$, $\text{rtd}_2(B - V(A)) \le \text{rtd}_2(G) - |V(A) \cap V(B)|$, $V(B) - V(A) \ne \emptyset$ and $V(A) \ne \emptyset$. We take such a separation $(A, B)$ with $|V(A) \cap V(B)| = 1$ if possible. Assume that it is impossible, and so, $|V(A) \cap V(B)| = 0$. Then we claim that every component of $G$ has only one vertex. Indeed, by (r4) there is a component $C$ of $G$ such that $\text{rtd}_2(G) = \text{rtd}_2(C)$. If $C$ has more than one vertex, there is a separation $(A', B')$ of $C$ of order at most one such that $\text{rtd}_2(A') \le \text{rtd}_2(C)$, $\text{rtd}_2(B' - V(A')) \le \text{rtd}_2(C) - |V(A') \cap V(B')|$, $V(B') - V(A') \ne \emptyset$ and $V(A') \ne \emptyset$. Note that $|V(A') \cap V(B')| = 1$ as $C$ is connected. However, $((G - V(C)) \cup A', B')$ contradicts the impossibility assumption. This proves that every component of $G$ has one vertex, and so, $G$ has no edges, which is a contradiction.
such that $G \subseteq G_{r,t}$. Hence, it is enough to show that there exists a graph $H$ with $rtd_2(H) \le t$ and $G_{r,t} \subseteq T_{h,d}(H)$ for some positive integers $h, d$. Let $\mathcal{B}$ be the family of all the blocks of $G_{r,t}$. Recall that $G_{r,t} = L_{(r+t)}(G_{r-1,t}, K_1 \oplus G_{r,t-1}, u)$ if $r, t > 0$. Thus, each $B \in \mathcal{B}$ is either isomorphic to $K_1 \oplus G_{r,t-1}$, or is a block of $G_{r-1,t}$. Thus, for each $B \in \mathcal{B}$ there is a nonnegative integer $r'$ with $r' < r$ such that every $B$ is isomorphic to $K_1 \oplus G_{r',t-1}$. This implies that for each $B \in \mathcal{B}$ we have $B \subseteq K_1 \oplus G_{r,t-1}$.

We denote by $s_B$ the vertex of $B$ corresponding to $K_1$. By the definition of $G_{r,t}$, one can inductively construct a rooted tree $T$ with $V(T) = \mathcal{B}$ such that for every $B \in \mathcal{B}$ which is not the root, the vertex $s_B$ belongs of $V(B')$ if $B'$ is the parent of $B$ in $T$. Moreover, $B - s_B$ is isomorphic to $G_{r',t-1}$ for some integer $r'$ with $r' \le r$. Let $S$ be the root of $T$. Let $h$ be the vertex-height of $T$, and let $d$ be the maximum number of children of a vertex in $T$. We claim that $H = G_{r,t-1}$ satisfies the required conditions. The first assertion is clear by Lemma 26, thus, it suffices to prove that $G_{r,t} \subseteq T_{h,d}(G_{r,t-1})$. To this end, we show by induction the following property. For every subtree $T'$ of $T$ rooted in $S$ of vertex-height $h'$, we have $\bigcup_{B \in V(T')} V(B) \subseteq T_{h',d}(G_{r,t-1})$.

When $h' = 1$, $|V(T')| = 1$ and so $\bigcup_{B \in V(T')} V(B) \subseteq K_1 \oplus G_{r,t-1} = T_{1,d}(G_{r,t-1})$. Now suppose that $h' > 1$. Let $L$ be the set of all vertices of $T'$ at distance $h' - 1$ from $S$. By induction hypothesis and because $T' - L$ has vertex-height $h' - 1$, we have $\bigcup_{B \in V(T' - L)} V(B) \subseteq T_{h'-1,d}(G_{r,t-1})$. Then, $\bigcup_{B \in V(T')} V(B)$ is obtained from $\bigcup_{B \in V(T' - L)} V(B)$ by gluing on every vertex at most $d$ blocks isomorphic to a subgraph of $K_1 \oplus G_{r,t-1}$. Hence $\bigcup_{B \in V(T')} V(B) \subseteq T_{h',d}(G_{r,t-1})$. Applying the above to $T' = T$ ends the proof. $\square$

Having a model of $T_{h,d}(X)$ in some graph $G$, sometimes it will be handy to insist that a given vertex $u \in V(G)$ is in the branch set of the root of $T_{h,d}(X)$. To this end, we introduce another auxiliary construction and we prove Lemma 29 below.

For every graph $X$ and for all positive integers $d, h$, let $T'_{h,d}(X)$ be the result of taking two disjoint copies of $T_{h,d}(X)$ and identifying their roots – we call this new vertex the root of $T'_{h,d}(X)$.

**Lemma 29.** Let $X$ be a graph and let $h, d$ be positive integers. Let $G$ be a connected graph and let $u \in V(G)$. If $(A_x \mid x \in V(T'_{h,d}(X)))$ is a model of $T'_{h,d}(X)$ in $G$, then there exists a model $(B_x \mid x \in V(T_{h,d}(X)))$ of $T_{h,d}(X)$ in $G$ such that

(a) $u \in B_s$ where $s$ is the root of $T_{h,d}(X)$ and

(b) for every $x \in V(T_{h,d}(X))$, there exists $y \in V(T'_{h,d}(X))$ such that $A_y \subseteq B_x$.

*Proof.* Observe that $T'_{h,d}(X)$ has a separation $(H_1, H_2)$ such that $V(H_1) \cap V(H_2) = \{s'\}$ where $s'$ is the root of $T'_{h,d}(X)$, and $H_i$ is isomorphic to $T_{h,d}(X)$ for each $i \in \{1, 2\}$.

Let $A$ be the union of all branch sets $A_x$ for $x \in V(T'_{h,d}(X))$. Fix a path $P$ in $G$ from $u$ to any vertex of $A$ with no internal vertices in $A$. Suppose that the endpoint of $P$ in $A$ is contained in $A_x$ for some $x_0 \in V(T'_{h,d}(X))$. Let $\{i, j\} = \{1, 2\}$ be such that $x_0 \in V(H_i)$. Let $B_s = V(P) \cup \bigcup_{x \in V(H_i)} A_x$ and $B_y = A_y$ for every $y \in V(H_j) - \{s\}$. Then $(B_y \mid y \in V(H_j))$ is a model of $T_{h,d}(X)$ in $G$ satisfying the conclusion of the lemma. $\square$
5. THE BASE CASE: GRAPHS WITH NO *F*-RICH MODEL OF A GIVEN TREE

The proof of Theorem 5 is by induction. The technical statement of the induction is stated in Theorem 8. In this section, we provide the base case for the induction, that is, the case where $X$ is a forest. It turns out that methods used in the so-called theory of product structure of graphs are useful in the study of weak coloring numbers. For instance, the main result of [2] is actually a product structure result and the weak coloring numbers bound follows from a slight adjustment of the argument. In the material of this section, we are strongly inspired by another product structure paper by Dujmović, Hickingbotham, Joret, Micek, Morin, and Wood [3].

For all positive integers $h$ and $d$, we denote by $F_{h,d}$ the (rooted) complete $d$-ary tree of vertex-height $h$. In particular, $F_{2,d}$ is the star with $d$ leaves. Note that for every tree $X$, there exist positive integers $h, d$ such that $X \subseteq F_{h,d}$.

We start with the case where $X$ is a star. Let $\delta$ be the function given by Lemma 17.

**Lemma 30.** Let $k, d$ be positive integers. Let $G$ be a connected $K_k$-minor-free graph, and let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$ such that $G$ has no $\mathcal{F}$-rich model of $F_{2,d}$. For every $U \subseteq V(G)$ such that $G[U]$ is connected, there is a set $S \subseteq V(G)$, a layering $(P_0, \dots, P_\ell)$ of $S$ in $G$ with $P_0 = U$, and sets $R_1, \dots, R_\ell \subseteq S$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) for every component $C$ of $G-S$, $N_G(V(C)) \subseteq P_i \cup P_j$ for some $i, j \in \{0, \dots, \ell\}$ and either $i = j$ or $j = i + 1$;

(d) $P_i \subseteq R_i \subseteq \bigcup_{j \in \{0, \dots, i\}} P_j$ for every $i \in [\ell]$;

(e) $\mathrm{wcol}_r(G, R_i) \le (\delta(k, d+1)+3) \cdot r$ for every $i \in [\ell]$ and for every positive integer $r$.

The statement of the lemma is visualized on Figure 8.

<figure><img src="image_9.png" /><figcaption>FIGURE 8. We illustrate the statement of Lemma 30. The green is a given set $U$, which should become $P_0$. It is contained in a blue layering of $S$. The yellow components should not contain members of $\mathcal{F}$. Moreover, each such component can have neighbors only in two consecutive layers. The set $R_3$ has to satisfy $P_3 \subseteq R_3 \subseteq P_0 \cup P_1 \cup P_2 \cup P_3$ and we want $\mathrm{wcol}_r(G, R_3)$ to be low. We do not depict all the sets $R_i$ for readability.</figcaption></figure>
*Proof.* In the proof we define many objects, they are depicted in Figure 9. We proceed by induction on $|V(G)| - |U|$. Let $U \subseteq V(G)$ be such that $G[U]$ is connected. If $\mathcal{F}|_{G-U} = \emptyset$, then it suffices to take $S = U$, $\ell = 0$ and $P_0 = U$. In particular, this is the case for $U = V(G)$. Therefore, assume $|U| < |V(G)|$ and $\mathcal{F}|_{G-U} \neq \emptyset$. Let $\mathcal{F}_0$ be the family of all the nonnull connected subgraphs $A$ of $G-U$ such that $A$ contains a member of $\mathcal{F}$ and $V(A) \cap N_G(U) \neq \emptyset$. We argue that $\mathcal{F}_0 \neq \emptyset$. Since $\mathcal{F}|_{G-U} \neq \emptyset$, there is a component $C$ of $G-U$ containing a member of $\mathcal{F}$. Since $G$ is connected, $V(C) \cap N_G(U) \neq \emptyset$, and in particular, $C \in \mathcal{F}_0$.

Observe that any collection of $d+1$ pairwise disjoint $A_1, \dots, A_{d+1} \in \mathcal{F}_0$ yields an $\mathcal{F}$-rich model of $F_{2,d}$ in $G$. Indeed, it suffices to take $U \cup A_{d+1}$ as the branch set corresponding to the root of $F_{2,d}$ and $A_1, \dots, A_d$ as the branch sets of the remaining $d$ vertices of $F_{2,d}$. Therefore, there is at most $d$ pairwise disjoint members of $\mathcal{F}_0$, and thus, by Lemma 17 applied to $G$ and $\mathcal{F}_0$, there exists a set $S_0 \subseteq V(G)$ such that

17.(a) $V(F) \cap S_0 \neq \emptyset$ for every $F \in \mathcal{F}_0$;

17.(b) $G[S_0]$ is connected;

17.(c) $\mathrm{wcol}_r(G, S_0) \leq \delta(k, d+1) \cdot r$ for every positive integer $r$.

Since $\mathcal{F}_0 \neq \emptyset$, we have $S_0 - U \neq \emptyset$. Let $Q$ be a $U-S_0$ geodesic in $G$ (possibly just one vertex path), and let $S_1 = (S_0 \cup V(Q)) - U$. Note that by 17.(b), $G[U \cup S_1]$ is connected.

Let $C_0$ be the family of all the components $C$ of $G - U - S_1$ such that $N_G(U) \cap V(C) = \emptyset$. Let $U' = V(G) - \bigcup_{C \in \mathcal{C}_0} V(C)$. Observe that $|U'| > |U|$ since $S_0 - U \neq \emptyset$ and $U'$ contains $U \cup S_1$. Moreover, $G[U']$ is connected since $G$ is connected and $G[U \cup S_1]$ is connected. Let $\mathcal{F}' = \{F \in \mathcal{F} \mid V(F) \cap U' = \emptyset\}$. By induction hypothesis applied to $G$, $\mathcal{F}'$, and $U'$, there is a set $S' \subseteq V(G)$, a layering $(P_0', \dots, P_{\ell'}')$ of $G[S']$ with $P_0' = U'$, and sets $R_0', \dots, R_{\ell'}' \subseteq S'$ such that

(a') $V(F) \cap S' \neq \emptyset$ for every $F \in \mathcal{F}'$;

(b') $G[S']$ is connected;

(c') for every component $C$ of $G - S'$, $N_G(V(C)) \subseteq P_i \cup P_j$ for some $i, j \in \{0, \dots, \ell'\}$ and either $i = j$ or $j = i + 1$;

(d') $P_i' \subseteq R_i' \subseteq \bigcup_{j \in \{0, \dots, i\}} P_j'$ for every $i \in \{0, \dots, \ell'\}$;

(e') $\mathrm{wcol}_r(G, R_i') \leq (\delta(k, d+1) + 3) \cdot r$ for every $i \in [\ell]$ and for every positive integer $r$.

Let $S = U \cup S_1 \cup (S' - U')$, $P_0 = U$, $P_1 = S_1$ and $P_i = P_{i-1}'$ for every $i \in \{2, \dots, \ell' + 1\}$ – we set $\ell = \ell' + 1$. Let $R_1 = S_0 \cup V(Q)$ and $R_i = R_{i-1}'$ for every $i \in \{2, \dots, \ell\}$. We claim that $(P_0, \dots, P_\ell)$ is a layering of $S$ in $G$ and (a)-(e) hold, which will complete the proof of the lemma.

Let $i, j \in \{0, \dots, \ell\}$ with $i < j$ and assume that there is an edge a vertex in $P_i$ and a vertex in $P_j$ in $G$. If $i \ge 1$, then $P_i \subseteq P_{i-1}'$ and $P_j = P_{j-1}'$, which implies $|i - j| \le 1$ since $(P_0', \dots, P_{\ell'}')$ is a layering of $G[S']$. Otherwise, $i = 0$ and since $N_G(V(G - U')) \subseteq S_1 = P_1$, we have $j = 1$, which implies that $(P_0, \dots, P_\ell)$ is a layering of $S$ in $G$.

Let $F \in \mathcal{F}$. If $V(F) \cap (U \cup S_1) \neq \emptyset$, then $V(F) \cap S \neq \emptyset$. Otherwise, $F \subseteq G - U$ and $V(F) \cap S_0 = \emptyset$, and therefore by 17.(a), $F \notin \mathcal{F}_0$, so in particular, $V(F) \cap N_G(U) = \emptyset$. In this case, $F \in \mathcal{F}'$, and by (a'), $V(F) \cap S' \neq \emptyset$. This proves (a).

Item (b) holds since $G[U \cup S_1]$ is connected and $G[S']$ is connected by (b').
Let $C$ be a component of $G-S$. Either $C$ is a component of $G-U-S_1$ with $C \notin C_0$ or $V(C) \cap U' = \emptyset$. In the former case, $N_G(V(C)) \subseteq U \cup S_1 = P_0 \cup P_1$, thus, assume the latter case. In particular, $C$ is a component of $G-S'$. By (c'), $N_G(V(C))$ is included in at most two consecutive parts of $(P'_0, \dots, P'_\ell)$. If $N_G(V(C)) \subseteq P'_\ell$, and so $N_G(V(C)) \subseteq P_{\ell+1}$, or there exists $i \in \{0, \dots, \ell-1\}$ such that $N_G(V(C)) \subseteq P'_i \cup P'_{i+1}$. If $i=0$, then $N_G(V(C)) \subseteq U' \cup P'_1$, and since $N_G(V(G-U')) \subseteq S_1$, we have $N_G(V(C)) \subseteq S_1 \cup P'_1 = P_1 \cup P_2$. If $i > 0$, then $N_G(V(C)) \subseteq P'_i \cup P'_{i+1} = P_{i-1} \cup P_i$. Hence, (c) holds.

Item (d) holds by construction and (d').

Finally, let $i \in [\ell]$ and let $r$ be a positive integer. If $i=1$, then we set $R_1 = S_0 \cup V(Q)$. We have $R_1 \subseteq P_0 \cup P_1 = U \cup S_1$ and $P_1 = S_1 \subseteq R_1$. Moreover,

$$ \mathrm{wcol}_r(G, S_0 \cup V(Q))) \le \delta(k, d+1) + (2r+1) \le (\delta(k, d+1) + 3) \cdot r $$

by 17.(c) and Observation 13. If $i > 1$, then by (e'), there exists $R'_{i-1} \subseteq \bigcup_{a \in \{0, \dots, i-1\}} P'_a$ with $P'_{i-1} \subseteq R'_{i-1}$ and $\mathrm{wcol}_r(G, R'_{i-1}) \le (\delta(k, d+1) + 3) \cdot r$. We set $R_i = R'_{i-1}$. This proves that (e) holds and ends the proof of the lemma. $\square$

<figure><img src="image_10.png" /><figcaption>FIGURE 9. An illustration of the considered objects in Lemma 30. Note that $S_0$ may intersect $U$.</figcaption></figure>

Now we are ready to prove the theorem for graphs with no $\mathcal{F}$-rich model of a fixed star. This part of the argument follows ideas from the proof by [13] that $\mathrm{wcol}_r(P) \le 1 + \lfloor \log r \rfloor$ for all paths $P$ – we explain the idea of this proof in Figure 10.

**Lemma 31.** Let $k, d$ be positive integers. For every connected $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $F_{2,d}$, then there is a set $S \subseteq V(G)$ such that

(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) $\mathrm{wcol}_r(G, S) \le 5(\delta(k, d+1) + 3) \cdot r \log r$ for every integer $r$ with $r \ge 2$.

*Proof.* Let $G$ be a connected $K_k$-minor-free graph, let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$, and suppose that $G$ has no $\mathcal{F}$-rich model of $F_{2,d}$. Let $r$ be an integer with $r \ge 2$. Let $U$ be an arbitrary singleton of a vertex in $G$. Lemma 30 applied to $G$, $\mathcal{F}$, and $U$ gives $S \subseteq V(G)$, a layering $(P_0, \dots, P_\ell)$ of $G[S]$ with $P_0 = U$, and sets $R_1, \dots, R_\ell \subseteq S$ such that
<figure><img src="image_11.png" /><figcaption>FIGURE 10. Consider the path $P = p_0 \dots p_{22}$. Let $r = 7$. Then, $s = 3 = \lceil \log(r+1) \rceil$. We claim that $\mathrm{wcol}_r(P) \le 1+s$. We mark every eighth vertex with 3 (this corresponds to the set $I_3$ in the proof of Lemma 31). Then, we mark each fourth unmarked vertex with 2 (the set $I_2 - I_3$), every second unmarked vertex with 1 (the set $I_1 - I_2$), and finally all remaining vertices with 0 (the set $I_0 - I_1$). Next, we construct an ordering on the vertices $p_0, \dots, p_{22}$. First, preserving the original ordering in the path, we put the vertices marked with 3, then similarly the ones marked with 2, with 1, and with 0. The lower part of the figure depicts this ordering in a slightly convoluted way that we will explain. It suffices to argue that for every $u \in V(P)$, we have $|\mathrm{WReach}_r[P, \sigma, u]| \le 4$. We build an auxiliary tree (depicted in green in the figure), where for every $i \in \{3, 2, 1\}$, we connect every vertex marked with $i$ with the closest (in the path) vertices marked with $i-1$. It is not hard to see that $\mathrm{WReach}_r[P, \sigma, u]$ consists only of the ancestors of $u$ in the auxiliary tree.</figcaption></figure>

30.(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

30.(b) $G[S]$ is connected;

30.(c) for every component $C$ of $G-S$, $N_G(V(C)) \subseteq P_i \cup P_j$ for some $i, j \in \{0, \dots, \ell\}$ and either $i=j$ or $j=i+1$;

30.(d) $P_i \subseteq R_i \subseteq \bigcup_{j \in \{0, \dots, i\}} P_j$ for every $i \in [\ell]$;

30.(e) $\mathrm{wcol}_r(G, R_i) \le (\delta(k, d+1)+3) \cdot r$ for every $i \in [\ell]$ and for every positive integer $r$.

Moreover, since $(P_0, \dots, P_\ell)$ is a layering of $S$ in $G$ and by 30.(c) we obtain

(⋆) for each $i \in \{0, \dots, \ell\}$, $P_i$ separates $\bigcup_{a \in \{0, \dots, i\}} P_a$ and $\bigcup_{a \in \{i, \dots, \ell\}} P_a$ in $G$.
Note that (a) holds by 30.(a) and (b) holds by 30.(b). In order to conclude the proof, it suffices to show (c).

Let $s = \lceil \log(r+1) \rceil$. For every $i \in \{0, \dots, s\}$, let $I_i = \{j \in \{0, \dots, \ell\} \mid j = 0 \bmod 2^i\}$. See Figure 10 again. We construct recursively families $\{R'_j\}_{j \in \{0, \dots, \ell\}}$ and $\{S_i\}_{i \in \{0, \dots, s\}}$ of subsets of $V(G)$ and a family $\{\sigma_j\}_{j \in \{0, \dots, \ell\}}$ such that $\sigma_j$ is an ordering of $R'_j$. For every $j \in I_s$, let

$$R'_j = R_j - \bigcup_{a \in \{0, \dots, j-2^s\}} P_a$$

and let $S_s = \bigcup_{j \in I_s} R'_j$. If $j < 2^s$, then $R'_j = R_j$, and so by 30.(e), $wcol_r(G, R'_j) \le (\delta(k, d+1) + 3) \cdot r$. Now assume that $j \ge 2^s$. By (★), $P_{j-2^s}$ separates $\bigcup_{a \in \{0, \dots, j-2^s\}} P_a$ and $\bigcup_{a \in \{j-2^s, \dots, \ell\}} P_a$ in $G$. In particular, $P_{j-2^s}$ separates $\bigcup_{a \in \{0, \dots, j-2^s\}} P_a$ and $R'_j$ in $G$. Since $P_{j-2^s} \subseteq R'_{j-2^s}$ by 30.(d), by (★) and Observation 10, we have

$$ \begin{aligned} wcol_r(G - \bigcup_{a \in \{0, \dots, j-2^s\} \cap I_s} R'_a, R'_j) &= wcol_r(G - P_{j-2^s}, R'_j) \\ &= wcol_r(G - \bigcup_{a \in \{0, \dots, j-2^s\}} P_a, R'_j). \end{aligned} $$

Finally,

$$ \begin{aligned} wcol_r(G - \bigcup_{a \in \{0, \dots, j-2^s\}} P_a, R'_j) &\le wcol_r(G, R_j) \quad \text{by Observation 14} \\ &\le (\delta(k, d+1) + 3) \cdot r \quad \text{by 30.(e).} \end{aligned} $$

For every $j \in I_s$, let $\sigma_j$ be an ordering of $R'_j$ such that

$$ wcol_r(G - \bigcup_{a \in \{0, \dots, j-2^s\} \cap I_s} R'_a, R'_j, \sigma_j) \le (\delta(k, d+1) + 3) \cdot r. $$

Next, let $i \in \{0, \dots, s-1\}$ and assume that $S_{i+1}$ is defined. Now for every $j \in I_i - I_{i+1}$, let

$$R'_j = (R_j - \bigcup_{a \in \{0, \dots, j-2^i\}} P_a) - S_{i+1},$$

and let $S_i = \bigcup_{j \in I_i} R'_j$. Let $j \in I_i - I_{i+1}$. We have $j - 2^i \in I_{i+1}$ and therefore $P_{j-2^i} \subseteq S_{i+1}$. By (★), $P_{j-2^i}$ separates $\bigcup_{a \in \{0, \dots, j-2^i\}} P_a$ and $\bigcup_{a \in \{j-2^i, \dots, \ell\}} P_a$ in $G$. It follows that

$$ wcol_r(G - S_{i+1}, R'_j) = wcol_r(G - P_{j-2^i}, R'_j) = wcol_r(G - \bigcup_{a \in \{0, \dots, j-2^i\}} P_a, R'_j). $$

Furthermore,

$$ \begin{aligned} wcol_r(G - \bigcup_{a \in \{0, \dots, j-2^i\}} P_a, R'_j) &\le wcol_r(G, R_j) \quad \text{by Observation 14} \\ &\le (\delta(k, d+1) + 3) \cdot r \quad \text{by 30.(e).} \end{aligned} $$

Let $\sigma_j$ be an ordering of $R'_j$ such that

$$ wcol_r(G - S_{i+1}, R'_j, \sigma_j) \le (\delta(k, d+1) + 3) \cdot r. $$

This concludes the construction of the families.

Let $S = S_0$. The sets $\{R'_j\}_{j \in \{0, \dots, \ell\}}$ are pairwise disjoint, and they partition $S$. Let $\sigma$ be an ordering of $S$ such that

(i) $\sigma$ extends $\sigma_j$, for every $j \in \{0, \dots, \ell\}$;

(ii) for every $j, j' \in I_s$ with $j < j'$, for all $u \in R'_j$ and $v \in R'_{j'}$, $u <_\sigma v$; and

(iii) for every $i \in \{0, \dots, s-1\}$, for all $u \in S_{i+1}$ and $v \in S_i - S_{i+1}$, $u <_\sigma v$.
Note the similarity of this ordering to the one described in Figure 10. For convenience, let $P_j = R'_j = \emptyset$ for every integer $j$ with $j > \ell$.

Let $u \in V(G)$. We will show that $|\text{WReach}_r[G, S, \sigma, u]| \le 5(\delta(k, d+1) + 3) \cdot r \log r$. Let $j_u \in \{0, \dots, \ell\}$ be such that if $u \in S$, then $u \in P_{j_u}$, and otherwise, $N_G(V(C)) \subseteq P_{j_u} \cup P_{j_u+1}$, where $C$ is the component of $u$ in $G-S$ (such $j_u$ exists by 30.(c)).

We claim that

$$|\text{WReach}_r[G, S, \sigma, u] \cap S_s| \le 2(\delta(k, d+1) + 3) \cdot r.$$

Let $\alpha = \max\{a \in I_s \mid a \le j_u\}$. This is well-defined since $0 \in I_s$. Let $\beta = \alpha + 2^s$. Thus if $\beta \le \ell$ then $\beta \in I_s$. Next, we argue that

$$\text{WReach}_r[G, S, \sigma, u] \cap S_s \subseteq R'_\alpha \cup R'_\beta.$$

Suppose to the contrary that there is a vertex $v \in \text{WReach}_r[G, S, \sigma, u] \cap S_s$ with $v \notin R'_\alpha \cup R'_\beta$ and $v \in R'_\gamma$ for some $\gamma \in I_s - \{\alpha, \beta\}$. Then either $\gamma < \alpha$ or $\gamma > \beta$. First, assume $\gamma < \alpha$. Since $R'_\gamma \subseteq \bigcup_{a \in \{0, \dots, \gamma\}} P_a$, by (⋆), every $u-v$ path in $G$ intersects $P_a$ for each $a \in \{\gamma, \dots, j_u\}$. Thus, we have $\text{dist}_G(u, v) \ge j_u - \gamma \ge \alpha - \gamma \ge 2^s > r$, which contradicts the fact that $v \in \text{WReach}_r[G, S, \sigma, u]$. Finally, assume that $\gamma > \beta$. If $\beta > \ell$, then the assertion is clear, thus assume $\beta \le \ell$. Since $R'_\gamma \subseteq \bigcup_{a \in \{\gamma-2^{s+1}, \dots, \gamma\}} P_a$, by (⋆), every $u-v$ path in $G$ intersects $P_\beta$. However, for every $w \in P_\beta$, we have $w <_\sigma v$, thus, $v \notin \text{WReach}_r[G, S, \sigma, u]$, which is a contradiction. We obtain that $\text{WReach}_r[G, S, \sigma, u] \cap S_s \subseteq R'_\alpha \cup R'_\beta$.

For every $\delta \in I_s$, by definition of $\sigma$, we have

$$\text{WReach}_r[G, S, \sigma, u] \cap R'_\delta \subseteq \text{WReach}_r[G - \bigcup_{a \in \{0, \dots, j_u - 2^s\} \cap I_s} R'_a, R'_\delta, \sigma_\delta, u]$$

and therefore,

$$|\text{WReach}_r[G, S, \sigma, u] \cap R'_\delta| \le (\delta(k, d+1) + 3) \cdot r.$$

In particular,

$$|\text{WReach}_r[G, S, \sigma, u] \cap S_s| \le |\text{WReach}_r[G, S, \sigma, u] \cap (R'_\alpha \cup R'_\beta)| \\ \le 2(\delta(k, d+1) + 3) \cdot r.$$

Next, let $i \in \{0, \dots, s-1\}$. We claim that

$$|\text{WReach}_r[G, S, \sigma, u] \cap (S_i - S_{i+1})| \le (\delta(k, d+1) + 3) \cdot r.$$

Since each vertex of $S_{i+1}$ precedes each vertex of $S_i$ in $\sigma$, we have

$$\text{WReach}_r[G, S, \sigma, u] \cap (S_i - S_{i+1}) \subseteq \text{WReach}_r[G - S_{i+1}, S - S_{i+1}, \sigma|_{S-S_{i+1}}, u] \cap (S_i - S_{i+1}).$$

Let $\alpha = \max\{a \in I_{i+1} \mid a \le j_u\}$ and $\beta = \alpha + 2^{i+1}$. Let $C$ be the component of $u$ in $G - S_{i+1}$. Since $P_\alpha, P_\beta \subseteq S_{i+1}$, by (⋆), $V(C) \cap S \subseteq \bigcup_{a \in \{\alpha+1, \dots, \beta-1\}} P_a$. We deduce that

$$\text{WReach}_r[G - S_{i+1}, S - S_{i+1}, \sigma|_{S-S_{i+1}}, u] \cap (S_i - S_{i+1}) \subseteq \bigcup_{a \in \{\alpha+1, \dots, \beta-1\}} P_a.$$

Since the only multiple of $2^i$ in $\{\alpha+1, \dots, \beta-1\}$ is $\gamma = \alpha + 2^i$, we in fact have

$$\text{WReach}_r[G - S_{i+1}, S - S_{i+1}, \sigma|_{S-S_{i+1}}, u] \cap (S_i - S_{i+1}) \subseteq R'_\gamma.$$
If $\gamma > \ell$, then $R'_{\gamma} = \emptyset$ and if $\gamma \le \ell$, then

$$ \begin{aligned} |\text{WReach}_r[G - S_{i+1}, S - S_{i+1}, \sigma|_{S-S_{i+1}}, u] \cap (S_i - S_{i+1})| &\le \text{wcol}_r(G - S_{i+1}, R'_{\gamma}, \sigma_{\gamma}) \\ &\le (\delta(k, d+1) + 3) \cdot r. \end{aligned} $$

This concludes the claim that $|\text{WReach}_r[G, S, \sigma, u] \cap (S_i - S_{i+1})| \le (\delta(k, d+1) + 3) \cdot r$.

Since $S = S_0$, it follows that setting $S_{s+1} = \emptyset$, we have

$$ \begin{aligned} |\text{WReach}_r[G, S, \sigma, u]| &\le \sum_{i \in \{0, \dots, s\}} |\text{WReach}_r[G, S, \sigma, u] \cap (S_i - S_{i+1})| \\ &\le (s+2) \cdot (\delta(k, d+1) + 3) \cdot r \\ &\le 5(\delta(k, d+1) + 3) \cdot r \log r. \end{aligned} \quad \square $$

To generalize Lemma 31 to graphs with no $\mathcal{F}$-rich model of $F_{h,d}$ for $h > 2$, we need the following straightforward property.

**Lemma 32.** Let $h, d$ be positive integers. Let $G$ be a connected graph. If there is a model $(B_x | x \in V(F_{h,d+1}))$ of $F_{h,d+1}$ in $G$, then for every $u \in V(G)$, there is a model $(B'_x | x \in V(F_{h,d}))$ of $F_{h,d}$ in $G$ such that

(a) $u \in B'_s$, where $s$ is the root of $F_{h,d}$, and

(b) for every $x \in V(F_{h,d})$, $B_y \subseteq B'_x$ for some $y \in V(F_{h,d+1})$.

*Proof.* Suppose that there is a model $(B_x | x \in V(F_{h,d+1}))$ of $F_{h,d+1}$ in $G$. Since $G$ is connected, we can assume that $\bigcup_{x \in V(F_{h,d+1})} B_x = V(G)$. Let $s_0$ be the root of $F_{h,d+1}$. There is a subtree $T'$ of $F_{h,d+1}$ rooted in a child of $s_0$ such that $u \in \bigcup_{x \in V(T') \cup \{s_0\}} B_x$. Define $B'_s = \bigcup_{x \in V(T') \cup \{s_0\}} B_x$ and $B'_x = B_x$ for every $x \in V(F_{h,d+1}) - (\{s_0\} \cup V(T'))$. The collection $(B'_x | x \in V(F_{h,d}))$ is a model of $F_{h,d}$ in $G$ satisfying (a) and (b). $\square$

**Lemma 33.** Let $k, h, d$ be positive integers with $h \ge 2$. There is an integer $c_0(h, d, k)$ such that for every connected $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $F_{h,d}$, then there is a set $S \subseteq V(G)$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) $\text{wcol}_r(G, S) \le c_0(h, d, k) \cdot r \log r$ for every integer $r$ with $r \ge 2$.

*Proof.* We proceed by induction on $h$. For $h = 2$, the result is given by Lemma 31 setting $c_0(1, d, k) = 5(\delta(k, d+1) + 3)$. Next, assume $h > 2$ and that $c_0(h-1, d, k)$ witnesses the assertion for $h-1$. Let $c_0(h, d, k) = 5(\delta(k, d+1) + 3) + 3 + c_0(h-1, d+1, k)$.

Let $G$ be a connected $K_k$-minor-free graph and let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$. Suppose that $G$ has no $\mathcal{F}$-rich model of $F_{h,d}$. Let $r$ be an integer with $r \ge 2$. Let $\mathcal{F}'$ be the family of all the connected subgraphs $H$ of $G$ such that $H$ contains an $\mathcal{F}|_H$-rich model of $F_{h-1,d+1}$. We claim that there is no $\mathcal{F}'$-rich model of $F_{2,d}$ in $G$. Suppose to the contrary that $(B_x | x \in V(F_{2,d}))$ is such a model. Let $s$ be the root of $F_{2,d}$ and let $s'$ be the root of $F_{h-1,d}$. For every $x \in V(F_{2,d}) - \{s\}$, by Lemma 32, there is an $\mathcal{F}$-rich model $(C_y | y \in V(F_{h-1,d}))$ of
$F_{h-1,d}$ in $G[B_x]$ such that $C_{s'}$ contains a vertex of $N_G(B_s) \cap B_x$. The union of these models together with $B_s$ yields an $\mathcal{F}$-rich model of $F_{h,d}$ in $G$, which is a contradiction. See Figure 11.

<figure><img src="image_12.png" /><figcaption>FIGURE 11. We provide an example of the construction of an $\mathcal{F}$-rich model of $F_{h,d}$ in $G$ assuming that there is an $\mathcal{F}'$-rich model of $F_{2,d}$ in $G$ in the case where $h=3$ and $d=2$. In green, we depict an $\mathcal{F}'$-rich model of $F_{2,d} = F_{2,2}$ in the graph. Each branch set contains an $\mathcal{F}$-rich model of $F_{h-1,d+1} = F_{2,3}$. We depict these models in yellow and the red stars are the elements of $\mathcal{F}$. The obtained model of $F_{h,d} = F_{3,2}$ we depict in blue. Note that this model is $\mathcal{F}$-rich.</figcaption></figure>

Since $G$ has no $\mathcal{F}'$-rich model of $F_{2,d}$, by Lemma 31, there is a set $S_0 \subseteq V(G)$ such that

31.(a) for every $F \in \mathcal{F}', V(F) \cap S_0 \neq \emptyset$;

31.(b) $G[S_0]$ is connected;

31.(c) $\mathrm{wcol}_r(G, S_0) \le 5(\delta(k, d+1) + 3) \cdot r \log r$.

Let $C$ be a component of $G - S_0$. By 31.(a), $C \notin \mathcal{F}'$, and so, $C$ has no $\mathcal{F}|_C$-rich model of $F_{h-1,d+1}$. Therefore, by induction hypothesis, there is a set $S_C \subseteq V(C)$ such that

(a') $V(F) \cap S_C \neq \emptyset$ for every $F \in \mathcal{F}|_C$;

(b') $C[S_C]$ is connected;

(c') $\mathrm{wcol}_r(C, S_C) \le c_0(h-1, d+1, k) \cdot r \log r$.

Let $Q_C$ be an $S_C-N_G(S_0)$ geodesic in $G$. In particular, $Q_C$ is a geodesic in $C$. Let $C$ be the family of components of $G - S_0$ and let

$$S = S_0 \cup \bigcup_{C \in C} (S_C \cup V(Q_C)).$$

See Figure 12 for an illustration. We claim that (a)-(c) hold.

Let $F \in \mathcal{F}$. If $V(F) \cap S_0 = \emptyset$, then $V(F) \subseteq V(C)$ for some component $C$ of $G - S_0$. In particular, $F \in \mathcal{F}|_C$, and thus, by (a'), $V(F) \cap S_C \neq \emptyset$, which proves (a). The graph $G[S]$ is connected by construction, (b') and 31.(b), which yields (b). The following sequence of
<figure><img src="image_13.png" /><figcaption>FIGURE 12. An illustration of the construction of the set $S$ in the proof of Lemma 33.</figcaption></figure>

inequalities concludes the proof of (c) and the lemma:

$$
\begin{align*}
wcol_r(G, S) &\le wcol_r(G, S_0) + wcol_r \left( G - S_0, \bigcup_{C \in \mathcal{C}} (S_C \cup V(Q_C)) \right) &\text{by Observation 12} \\
&\le wcol_r(G, S_0) + \max_{C \in \mathcal{C}} wcol_r(C, S_C \cup V(Q_C)) &\text{by Observation 11} \\
&\le wcol_r(G, S_0) + \max_{C \in \mathcal{C}} wcol_r(C, S_C) + (2r + 1) &\text{by Observation 13} \\
&\le 5(\delta(k, d+1) + 3) \cdot r \log r + c_0(h-1, d+1, k) \cdot r \log r + 3r &\text{by 31.(c) and (c')} \\
&\le (5(\delta(k, d+1) + 3) + c_0(h-1, d+1, k) + 3) \cdot r \log r \\
&= c_0(h, d, k) \cdot r \log r. \quad \square
\end{align*}
$$

6. PROOF OF THE MAIN THEOREM

In this section, we prove Theorem 5. As already mentioned, the proof is by induction, and in
Section 5 we covered the base case. The induction statement is encapsulated in Theorem 8.
Note that in order to obtain Theorem 5 as a corollary of Theorem 8 one has to apply it to each
connected component of G with $k = |V(X)|$ and with the family of all one-vertex subgraphs
of G as $\mathcal{F}$. Note that in such a case $S$ must be equal to $V(G)$.

**Theorem 34** (Theorem 8 restated). Let $k$ and $t$ be positive integers with $t \ge 2$. Let $X$ be a graph with $rtd_2(X) \le t$. There exists an integer $c(t, X, k)$ such that for every connected $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $X$, then there exists $S \subseteq V(G)$ such that

(A) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(B) $G[S]$ is connected;

(C) $wcol_r(G, S) \le c(t, X, k) \cdot r^{t-1} \log r$ for every integer $r$ with $r \ge 2$.

*Proof.* We proceed by induction on $t$. When $t=2$, by Observation 21, $X$ is a forest. Let $h, d$ be positive integers such that $X \subseteq F_{h,d}$, and let $c_0(h, d, k)$ be the constant given by Lemma 33. The assertion with $c(2, X, k) = c_0(h, d, k)$ follows by applying Lemma 33. Next, let $t \ge 3$, and assume that the result holds for $t-1$. We refer to this property as the *main induction hypothesis*.
Claim 1. Let $Y$ be a graph with $\mathrm{rtd}_2(Y) \le t-1$. There is an integer $c_1(t, Y, k)$ such that for every connected $K_k$-minor-free graph $G$, for every $u \in V(G)$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $K_1 \oplus Y$, then there exist $S \subseteq V(G)$, a tree $T$ rooted in $s \in V(T)$, and a tree partition $(T, (P_x \mid x \in V(T)))$ of $G[S]$ with $P_s = \{u\}$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) for every component $C$ of $G-S$, $N_G(V(C)) \subseteq P_x \cup P_y$ for some $x, y \in V(T)$ with either $x=y$ or $xy$ is an edge in $T$;

(d) for every $x \in V(T)$ let $T_x$ be the subtree of $T$ rooted in $x$, then

$$ \mathrm{wcol}_r \left( G \left[ \bigcup_{y \in V(T_x)} P_y \right], P_x \right) \le c_1(t, X, k) \cdot r^{t-2} \log r $$

for every integer $r$ with $r \ge 2$.

The statement of the claim is visualized in Figure 13.

<figure><img src="image_14.png" /><figcaption>FIGURE 13. An illustration of the statement of Claim 1.</figcaption></figure>

*Proof of the claim.* Let $X' = K_1 \sqcup Y$ and let $c_1(t, Y, k) = c(t-1, X', k) + 3$. We proceed by induction on $|V(G)|$. If $|V(G)| = 1$, then since $c_1(t, Y, k) \ge 1$, the result holds. Next, suppose that $|V(G)| > 1$.

First, assume that $G - \{u\}$ is not connected. Let $\mathcal{C}$ be the family of all the components of $G - \{u\}$. Consider a component $C \in \mathcal{C}$. By induction hypothesis applied to $G_C = G[V(C) \cup \{u\}]$, $u$, and $\mathcal{F}|_{G_C}$, there exist $S_C \subseteq V(G_C)$, a tree $T_C$ rooted in $s_C \in V(T_C)$, and a tree partition $(T_C, (P_{C,x} \mid x \in V(T_C)))$ of $S_C$ in $G_C$ with $P_{C,s_C} = \{u\}$ such that

(a') $V(F) \cap S_C \neq \emptyset$ for every $F \in \mathcal{F}|_{G[V(C) \cup \{u\}]}$;

(b') $G[S_C]$ is connected;

(c') for every component $C'$ of $G_C - S_C$, $N_{G_C}(V(C')) \subseteq P_{C,x} \cup P_{C,y}$ for some $x, y \in V(T_C)$ and either $x = y$ or $xy$ is an edge in $T_C$;
(d') for every $x \in V(T_C)$ let $T_{C,x}$ be the subtree of $T_C$ rooted in $x$, then

$$ \mathrm{wcol}_r \left( G_C \left[ \bigcup_{y \in V(T_{C,x})} P_{C,y} \right], P_{C,x} \right) \le c_1(t, X, k) \cdot r^{t-2} \log r $$

for every integer $r$ with $r \ge 2$.

Then let $S = \bigcup_{C \in \mathcal{C}} S_C$, let $T$ be the tree obtained from the disjoint union of all the $T_C$ for $C \in \mathcal{C}$ by identifying all the vertices in $\{s_C | C \in \mathcal{C}\}$ into a single vertex $s$. Finally, let $P_s = \{u\}$ and $P_x = P_{C,x}$ for every $C \in \mathcal{C}$ and $x \in V(T_C) - \{s_C\}$. Then we claim that (a)-(d) hold. Indeed, for every $F \in \mathcal{F}$, $F$ is connected so either $F$ is a subgraph of $G - \{u\}$ or $F$ contains $u$. In both cases, we see that $V(F) \cap S \ne \emptyset$, so (a) holds. Item (b) holds as $u \in S_C$ and $G[S_C]$ is connected for all $C \in \mathcal{C}$. Item (c) holds as every component of $G - S$ is a component of $G_C - S_C$ for some $C \in \mathcal{C}$. Finally, for all $x \in V(T)$ with $x \ne s$ item (d) follows directly from (d') and the construction of $T$, while when $x = s$, $\mathrm{wcol}_r(G[\bigcup_{y \in V(T)} P_y], P_s) = 1$ for every integer $r$ with $r \ge 2$. From now on we assume that $G - \{u\}$ is connected.

Let $\mathcal{F}'$ be the family of all the nonnull connected subgraphs $H$ of $G - \{u\}$ such that $u \in N_G(V(H))$ and $F \subseteq H$ for some $F \in \mathcal{F}$. We argue that there is no $\mathcal{F}'$-rich model of $X'$ in $G - \{u\}$. Indeed, such a model would contain an $\mathcal{F}$-rich model of $K_1 \sqcup Y$ in $G - \{u\}$ such that every branch set is adjacent to $u$. By adding $u$ to the branch set corresponding to $K_1$ in $K_1 \sqcup Y$, we obtain an $\mathcal{F}$-rich model of $K_1 \oplus Y$ in $G$, which is a contradiction. This proves that there is no $\mathcal{F}'$-rich model of $X'$ in $G - \{u\}$.

Since $\mathrm{rtd}_2(X') \le \max\{\mathrm{rtd}_2(Y), 1\} \le t - 1$, by the main induction hypothesis applied to $X', G - \{u\}$, and $\mathcal{F}'$, there exists a set $S_0 \subseteq V(G - \{u\})$ such that

(A') $V(F) \cap S_0 \ne \emptyset$ for every $F \in \mathcal{F}'$;

(B') $(G - \{u\})[S_0]$ is connected;

(C') $\mathrm{wcol}_r(G - \{u\}, S_0) \le c(t - 1, X', k) \cdot r^{t-2} \log r$ for every integer $r$ with $r \ge 2$.

By possibly adding an arbitrary vertex of $V(G - \{u\})$ to $S_0$, we can assume $S_0 \ne \emptyset$. Let $Q$ be a $u-S_0$ geodesic in $G$ and let $S_1 = (S_0 \cup V(Q)) - \{u\}$. Note that $G[\{u\} \cup S_1]$ is connected by (B').

Let $C_1$ be the family of all the components $C$ of $G - (\{u\} \cup S_1)$ such that $N_G(u) \cap V(C) = \emptyset$. Consider $C \in C_1$. Since $G$ is connected and $u \notin N_G(V(C))$, there is an edge between $V(C)$ and $S_1$ in $G$. Let $G_C$ be obtained from $G[V(C) \cup S_1]$ by contracting $S_1$ into a single vertex $u_C$. Note that $|V(G_C)| < |V(G)|$ since $u \notin V(G_C)$. Since $G_C$ is a minor of $G$, $G_C$ has no $\mathcal{F}|_C$-rich model of $K_1 \oplus Y$. By induction hypothesis applied to $G_C$, $u_C$, and $\mathcal{F}|_C$, there exist $S_C \subseteq V(G_C)$, a tree $T_C$ rooted in $S_C \in V(T_C)$, and a tree partition $(T_C, (P_{C,x} | x \in V(T_C)))$ of $S_C$ in $G_C$ with $P_{C,s_C} = \{u_C\}$ such that

(a'') $V(F) \cap S_C \ne \emptyset$ for every $F \in \mathcal{F}|_C$;

(b'') $G_C[S_C]$ is connected;

(c'') for every component $C'$ of $G_C - S_C$, $N_{G_C}(V(C')) \subseteq P_{C,x} \cup P_{C,y}$ for some $x, y \in V(T_C)$ and either $x = y$ or $xy$ is an edge in $T_C$;
(d”) for every $x \in V(T_C)$ let $T_{C,x}$ be the subtree of $T_C$ rooted in $x$, then

$$ \mathrm{wcol}_r \left( G_C \left[ \bigcup_{y \in V(T_{C,x})} P_{C,y} \right], P_{C,x} \right) \le c_1(t, X, k) \cdot r^{t-2} \log r $$

for every integer $r$ with $r \ge 2$.

Let

$$ S = \{u\} \cup S_1 \cup \bigcup_{C \in \mathcal{C}_1} (S_C - \{u_C\}). $$

Let $T$ be obtained from the disjoint union of $\{T_C \mid C \in \mathcal{C}_1\}$ by identifying the vertices $\{s_C \mid C \in \mathcal{C}_1\}$ into a new vertex $s'$ and by adding a new vertex $s$ adjacent to $s'$ in $T$. Let $P_s = \{u\}$, $P_{s'} = S_1$, and for each $C \in \mathcal{C}_1$, $x \in V(T_C - \{s_C\})$, let $P_x = P_{C,x}$. See Figure 14 for the illustration of this construction.

In order to conclude, we argue that $(T, (P_x \mid x \in V(T)))$ is a tree partition of $G[S]$ and (a)-(d) hold.

<figure><img src="image_15.png" /><figcaption>FIGURE 14. An illustration of the construction of $S$ and its tree partition in the proof of Claim 1. Note that in the sketched case $\mathcal{C}_1 = \{C_1, C_2\}$.</figcaption></figure>

Since for every $C \in \mathcal{C}_1$, $u \notin N_G(V(C))$, every edge in $G[S]$ containing $u$ has another endpoint in $S_1 = P_{s'}$. Consider an edge $vw$ in $G[S]$ such that $v \in S_1$ and $w \in S_C$ for some $C \in \mathcal{C}_1$. Since $(T_C, (P_{C,x} \mid x \in V(T_C)))$ is a tree partition of $G_C[S_C]$ with $P_{C,s_C} = \{u_C\}$ and $u_C$ is the result of the contraction of $S_1$, we conclude that $w \in P_x$ for some $x \in V(T_C)$ such that $s'x$ is an edge in $T$. Finally, for every edge $vw$ of $G[S]$ with $v, w \notin \{u\} \cup S_1$, $vw$ is an edge of $G[S_C - \{u_C\}]$ for some component $C \in \mathcal{C}_1$, and so $v \in P_{C,x}$ and $w \in P_{C,y}$ for adjacent or identical vertices $v, w$ of $T_C$. Then $v \in P_x$ and $w \in P_y$. It follows that $(T, (P_x \mid x \in V(T)))$ is a tree partition of $G[S]$.

Let $F \in \mathcal{F}$. If $V(F) \cap (\{u\} \cup S_1) \ne \emptyset$, then $V(F) \cap S \ne \emptyset$. Otherwise, $F \subseteq G - \{u\}$ and $V(F) \cap S_0 = \emptyset$, and therefore by (A'), $F \notin \mathcal{F}'$, so in particular, $u \notin N_G(V(F))$. In this case, there is a component $C \in \mathcal{C}_1$ such that $F \in \mathcal{F}|_C$, thus, $V(F) \cap S_C \ne \emptyset$ by (a''). This proves (a).

Item (b) holds since $G[\{u\} \cup S_1]$ is connected and for every $C \in \mathcal{C}_1$, $G_C[S_C]$ is connected by (b") and $u_C \in S_C$.
For every component $C'$ of $G-S$, either $N_G(V(C')) \subseteq \{u\} \cup S_1 = P_s \cup P_{s'}$, or $C' \subseteq C$ for some $C \in \mathcal{C}_1$. In the latter case, $C'$ is a component of $G_C - S_C$, and $u \notin N_G(V(C))$. By (c'), there is $x, y \in V(T_C)$ such that $N_{G_C}(V(C')) \subseteq P_{C,x} \cup P_{C,y}$, and thus, $N_G(V(C')) \subseteq P_x \cup P_y$. This proves (c).

Finally, we argue (d). Let $r$ be an integer with $r \ge 2$ and let $x \in V(T)$. For $x = s$, $|P_s| = 1$, thus the assertion is clear. For $x = s'$, we have $T_{s'} = V(G) - \{u\}$. By (C'), $\mathrm{wcol}_r(G - \{u\}, S_0) \le c(t-1, X', k) \cdot r^{t-2} \log r$. Since $Q$ is a geodesic in $G$, by Observation 15, $\mathrm{wcol}_r(G - \{u\}, S_1) \le c(t-1, X', k) \cdot r^{t-2} \log r + (2r+1) \le c_1(t, Y, k) \cdot r^{t-2} \log r$.

For $x \in V(T_C - \{s_C\})$ for some $C \in \mathcal{C}_1$, we have $T_x = T_{C,x}$, thus, the asserted inequality follows from (d''). This ends the proof of the claim. $\diamond$

Claim 1 yields the following less technical statement.

Claim 2. Let $Y$ be a graph with $\mathrm{rtd}_2(Y) \le t-1$. There is an integer $c_2(t, Y, k)$ such that for every connected $K_k$-minor-free graph $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $K_1 \oplus Y$, then there exists $S \subseteq V(G)$ such that

(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) $\mathrm{wcol}_r(G, S) \le c_2(t, Y, k) \cdot r^{t-1} \log r$ for every integer $r$ with $r \ge 2$.

*Proof of the claim.* Let $c_2(t, Y, k) = 2 \cdot c_1(t, Y, k)$ and let $r$ be an integer with $r \ge 2$. We apply Claim 1 with an arbitrary vertex $u \in V(G)$ to obtain $S \subseteq V(G)$, a tree $T$ rooted in $s \in V(T)$, and a tree partition $(T, (P_x | x \in V(T)))$ of $S$ in $G$ with $P_s = \{u\}$ such that

1.(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

1.(b) $G[S]$ is connected;

1.(c) for every component $C$ of $G-S$, $N_G(V(C)) \subseteq P_x \cup P_y$ for some $x, y \in V(T)$ and either $x = y$ or $xy$ is an edge in $T$;

1.(d) for every $x \in V(T)$ let $T_x$ be the subtree of $T$ rooted in $x$, then

$$ \mathrm{wcol}_r \left( G \left[ \bigcup_{y \in V(T_x)} P_y \right], P_x \right) \le c_1(t, X, k) \cdot r^{t-2} \log r $$

for every integer $r$ with $r \ge 2$.

Items (a) and (b) hold by 1.(a) and 1.(b) respectively. It suffices to prove (c).

For each $x \in V(T)$, let $\sigma_x$ be an ordering of $P_x$ witnessing 1.(d) and let $\sigma' = (x_1, \dots, x_{|V(T)|})$ be an elimination ordering of $T$. Finally, let $\sigma$ be the concatenation of $\sigma_{x_1}, \dots, \sigma_{x_{|V(T)|}}$ in this order.

Let $u \in V(G)$. To conclude the claim, we argue that

$$ |\mathrm{WReach}_r[G, S, \sigma, u]| \le c_2(t, Y, k) \cdot r^{t-1} \log r. $$

Let $x_u \in V(T)$ be such that if $u \in S$, then $u \in P_{x_u}$, and otherwise, $x_u$ is the vertex of $T$ furthest to $s$ such that $P_{x_u}$ intersects $N_G(V(C))$, where $C$ is the component of $u$ in $G-S$.
Let $A$ be the set of all the ancestors of $x_u$ in $T$ in distance at most $r$ from $x_u$. In particular, $|A| \le r + 1$. By Observation 19 and 1.(c),

$$WReach_r[G, S, \sigma, u] \subseteq \bigcup_{y \in A} P_y.$$

Let $y \in A$. Since $\sigma$ extends $\sigma_y$ and $x \in T_y$, by 1.(d), we have

$$| WReach_r[G, S, \sigma, u] \cap P_y | \le wcol_r \left( G \left[ \bigcup_{z \in V(T_y)} P_z \right], P_y \right) \le c_1(t, X, k) \cdot r^{t-2} \log r.$$

Summarizing,

$$\begin{aligned} | WReach_r[G, S, \sigma, u] | &= \sum_{y \in A} | WReach_r[G, S, \sigma, u] \cap P_y | \\ &\le (r+1) \cdot c_1(t, X, k) \cdot r^{t-2} \log r \\ &\le 2r \cdot c_1(t, X, k) \cdot r^{t-2} \log r = c_2(t, Y, k) \cdot r^{t-1} \log r. \end{aligned}$$

This concludes the proof of (c), and the claim follows. $\diamond$

We now move on to the final step of the proof.

*Claim 3.* Let $Y$ be a graph with $rtd_2(Y) \le t-1$ and let $h, d$ be positive integers. There exists an integer $c_3(Y, h, d, k)$ such that for every connected $K_k$-minor-free graph $G$ and for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $T'_{h,d}(Y)$, then there exists $S \subseteq V(G)$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) $G[S]$ is connected;

(c) $wcol_r(G, S) \le c_3(Y, h, d, k) \cdot r^{t-1} \log r$ for every integer $r$ with $r \ge 2$.

*Proof of the claim.* We proceed by induction on $h$. When $h = 1$, $T'_{h,d}(Y) = K_1 \oplus (Y \sqcup Y)$ and the result follows from the previous claim applied to $Y \sqcup Y$ (note that $rtd_2(Y \sqcup Y) = rtd_2(Y) \le t-1$) by setting $c_3(Y, 1, d, k) = c_2(t, Y \sqcup Y, k)$.

Now assume that $h > 1$ and that the result holds for $h-1$. Fix a copy of $Y \sqcup Y$. For each $y \in V(Y \sqcup Y)$ add $d$ vertices with $y$ as a unique neighbor. Furthermore, add $2d$ isolated vertices. We call the obtained graph $Z$ – see Figure 15. To keep things in order, we write $V(Z) = V_Y \cup V_Z$, where $V_Y$ are the vertices of $Y \sqcup Y$ in $Z$ and $V_Z$ are all the added vertices. Let

$$c_3(Y, h, d, k) = c_2(t, Z, k) + c_3(Z, h-1, d, k) + 3.$$

By (r8) and (r4), $rtd_2(Z) \le \max\{2, rtd_2(Y)\} \le t-1$ since $t \ge 3$.

Let $\mathcal{F}'$ be the family of all the connected subgraphs $H$ of $G$ such that $H$ has an $\mathcal{F}|_{H}$-rich model of $T'_{h-1,d}(Y)$. We claim that there is no $\mathcal{F}'$-rich model of $K_1 \oplus Z$ in $G$. Suppose to the contrary that such a model $(A_y | y \in V(K_1 \oplus Z))$ exists. Let $s$ be the vertex of $K_1$ in $K_1 \oplus Z$. In particular, $V(K_1 \oplus Z) = \{s\} \cup V_Y \cup V_Z$. For every vertex $z \in V_Z$, we define its parent in $K_1 \oplus Z$ in the following way. Note that $z$ has at most one neighbor in $Z$. If $z$ has a neighbor in $Z$, then the neighbor is its parent and if $z$ is isolated in $Z$, then $s$ is its parent. Let $z \in V_Z$ with the parent $p_z$ and let $u_z \in A_z$ be such that there is an edge between $u_z$ and a vertex in
<figure><img src="image_16.png" /><figcaption>FIGURE 15. An illustration of the graph $K_1 \oplus Z$.</figcaption></figure>

$A_{p_z}$. Since the model is $\mathcal{F}'$-rich, $G[A_z]$ contains an $\mathcal{F}|_{G[A_z]}$-rich model of $T'_{h-1,d}(Y)$. Let $H_z$ be a copy of $T_{h-1,d}(Y)$ with a root $s_z$. By Lemma 29 applied to $Y$, $G[A_z]$, and $u$, there is an $\mathcal{F}|_{G[A_z]}$-rich model ($B_{z,x} | x \in V(H_z)$) of $H_z$ in $G[A_z]$ such that $u_z \in B_{z,s_z}$. In particular, there is an edge between $B_{z,s_z}$ and $A_{p_z}$ in $G$. Finally, we construct an $\mathcal{F}$-rich model of $T'_{h,d}(Y)$ in $G$. Observe that the graph obtained from $(K_1 \oplus Z)[\{s\} \cup V_Y]$ (this graph is isomorphic to $K_1 \oplus (Y \sqcup Y)$) and the disjoint union of $H_z$ for each $z \in V_Z$ by identifying $s_z \in V(H_z)$ with $p_z \in \{s\} \cup V_Y$ for each $z \in V_Z$ is isomorphic to $T'_{h,d}(Y)$. For each $p \in \{s\} \cup V_Y$, let $P_y$ be the set of all $z \in V_Z$ such that $p$ is the parent of $z$. Let

(i) $D_p = A_p \cup \bigcup_{z \in P_p} B_{z,s_z}$ for every $p \in \{s\} \cup V_Y$ and

(ii) $D_x = B_{z,x}$ for every $z \in V_Z$ and $x \in V(H_z - \{s_z\})$.

It follows that $(D_x | x \in \{s\} \cup V_Y \cup \bigcup_{z \in V_Z} V(H_z - \{s_z\}))$ is an $\mathcal{F}$-rich model of $T'_{h,d}(Y)$ in $G$. This is a contradiction, hence, $G$ has no $\mathcal{F}'$-rich model of $K_1 \oplus Z$.

<figure><img src="image_17.png" /><figcaption>FIGURE 16. We illustrate how the $\mathcal{F}'$-rich model of $T'_{h,d}(Y)$ in $G$ is constructed. We depict only one vertex $p \in \{s\} \cup V_Y$ and two vertices $z_1, z_2 \in V_Z$ such that $p$ is the parent of both $z_1$ and $z_2$. The yellow model is a model of $T'_{h-1,d}(Y)$ after applying Lemma 29.</figcaption></figure>
By Claim 2, applied to $Z$, $G$, and $\mathcal{F}'$ there exists $S_0 \subseteq V(G)$ such that

2.(a) $V(F) \cap S_0 \neq \emptyset$ for every $F \in \mathcal{F}'$;

2.(b) $G[S_0]$ is connected;

2.(c) $\mathrm{wcol}_r(G, S_0) \le c_2(t, 1, Z, k) \cdot r^{t-1} \log r$ for every integer $r$ with $r \ge 2$.

Let $C$ be a component of $G - S_0$. Since $V(F) \cap S_0 \neq \emptyset$ for every $F \in \mathcal{F}'$, $C$ has no $\mathcal{F}|_C$-rich model of $T'_{h-1,d}(Y)$. Therefore, by induction hypothesis, there exists $S_C \subseteq V(C)$ such that

(a') $V(F) \cap S_C \neq \emptyset$ for every $F \in \mathcal{F}|_C$;

(b') $C[S_C]$ is connected;

(c') $\mathrm{wcol}_r(C, S_C) \le c_3(Y, h-1, d, k) \cdot r^{t-1} \log r$ for every integer $r$ with $r \ge 2$.

Let $Q_C$ be an $S_C$-$N_G(S_0)$ geodesic in $G$. In particular, $Q_C$ is a geodesic in $C$. Let $\mathcal{C}$ be the family of all the components of $G - S_0$ and let

$$S = S_0 \cup \bigcup_{C \in \mathcal{C}} (S_C \cup V(Q_C)).$$

We claim that (a)-(c) hold. Let $F \in \mathcal{F}$. If $V(F) \cap S_0 = \emptyset$, then $V(F) \subseteq V(C)$ for some component $C$ of $G - S_0$. In particular, $F \in \mathcal{F}|_C$, and thus, by (a'), $V(F) \cap S_C \neq \emptyset$, which proves (a). The graph $G[S]$ is connected by construction, 2.(b) and (b'), which yields (b). The following sequence of inequalities concludes the proof of (c) and the claim:

$$\mathrm{wcol}_r(G, S) \le \mathrm{wcol}_r(G, S_0) + \mathrm{wcol}_r \left( G - S_0, \bigcup_{C \in \mathcal{C}} (S_C \cup V(Q_C)) \right) \quad \text{by Observation 12}$$

$$\le \mathrm{wcol}_r(G, S_0) + \max_{C \in \mathcal{C}} \mathrm{wcol}_r(C, S_C \cup V(Q_C)) \quad \text{by Observation 11}$$

$$\le \mathrm{wcol}_r(G, S_0) + \max_{C \in \mathcal{C}} \mathrm{wcol}_r(C, S_C) + (2r+1) \quad \text{by Observation 13}$$

$$\le c_2(t, Z, k) \cdot r^{t-1} \log r + c_3(Y, h-1, d, k) \cdot r^{t-1} \log r + 3r \quad \text{by 2.(c) and (c')}$$

$$\le (c_2(t, Z, k) + c_3(Y, h-1, d, k) + 3) \cdot r^{t-1} \log r$$

$$= c_3(Y, h, d, k) \cdot r^{t-1} \log r.$$

◇

Finally, by Lemma 28, for every graph $X$ with $\mathrm{rtd}_2(X) \le t$, there exists a graph $Y$ with $\mathrm{rtd}_2(Y) \le t-1$ and positive integers $h, d$ such that $X \subseteq T_{h,d}(Y) \subseteq T'_{h,d}(Y)$. By Claim 3, the theorem follows with $c(t, X, k) = c_3(Y, h, d, k)$. □

## 7. A TIGHTER BOUND FOR GRAPHS OF BOUNDED TREEWIDTH

In this section, we prove Theorem 6.

### 7.1. Preliminaries.
We start by recalling the notion of tree decomposition and one of its basic properties. Then, we introduce a refined version of tree decomposition – natural tree decomposition. Let $G$ be a graph. A tree decomposition of a graph $G$ is a pair $\mathcal{D} = (T, \{W_x \mid x \in V(T)\})$ where $T$ is a tree and $W_x \subseteq V(G)$ for every $x \in V(T)$ satisfying the following conditions:
(i) for every $u \in V(G)$, $T[\{x \in V(T) \mid u \in W_x\}]$ is a connected nonnull subtree of $T$, and

(ii) for every edge $uv \in E(G)$, there exists $x \in V(T)$ such that $u, v \in W_x$.

The sets $W_x$ are called *bags* of $\mathcal{D}$. The *width* of $\mathcal{D}$ is $\max_{x \in V(T)} |W_x| - 1$, and the *treewidth* of $G$, denoted by $\text{tw}(G)$, is the minimum width of a tree decomposition of $G$.<fnref n="6" />

**Lemma 35** ([20, Statement (8.7)]). For every graph $G$, for every tree decomposition $\mathcal{D}$ of $G$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, for every positive integer $d$, either

(1) there are $d$ pairwise vertex-disjoint subgraphs in $\mathcal{F}$ or

(2) there is a set $S$ that is the union of at most $d-1$ bags of $\mathcal{D}$ such that $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$.

A tree decomposition $(T, (W_x \mid x \in V(T)))$ of a graph $G$ is *natural* if for every edge $e$ in $T$, for each component $T_0$ of $T-e$, the graph $G[\bigcup_{z \in V(T_0)} W_z]$ is connected. The following statement appeared first in [6], see also [7].

**Lemma 36** ([6, Theorem 1]). Let $G$ be a connected graph and let $(T, (W_x \mid x \in V(T)))$ be a tree decomposition of $G$. There exists a natural tree decomposition $(T', (W'_x \mid x \in V(T')))$ of $G$ such that for every $x' \in V(T')$ there is $x \in V(T)$ with $W'_{x'} \subseteq W_x$.

The following lemma is folklore. See e.g. [2, Lemma 8] for a proof.

**Lemma 37.** Let $m$ be a positive integer. Let $G$ be a graph and let $\mathcal{D}$ be a tree decomposition of $G$. If $Y$ is the union of $m$ bags of $\mathcal{D}$, then there is a set $X$ that is the union of at most $2m-1$ bags of $\mathcal{D}$ such that $Y \subseteq X$ and for every component $C$ of $G-X$, $N_G(V(C)) \cap X$ is a subset of the union of at most two bags of $\mathcal{D}$. Moreover, if $\mathcal{D}$ is natural, then $N_G(V(C))$ intersects at most two components of $G-V(C)$.

We will need the following technical statement. For a given set $S$, we say that a collection $S_1, \dots, S_k \subseteq S$ is a *covering* of $S$ if $S_1 \cup \dots \cup S_k = S$.

**Lemma 38.** Let $k$ be a positive integer and let $X$ be a graph. There exists a graph $X'$ such that $\text{rtd}_2(X') \le \text{rtd}_2(X)$ and for every sets $S_1, \dots, S_k$ of vertices of $X'$ whose union is $V(X')$, there exists $i \in [k]$ such that $X'$ contains an $\{H \subseteq X' \mid H \text{ connected and } S_i \cap V(H) \ne \emptyset\}$-rich model of $X$.

Lemma 38 follows directly from Lemma 39 and Lemma 28.

**Lemma 39.** Let $h, d, k$ be positive integers and let $X$ be a graph. There exists a positive integer $d'$ and a graph $X'$ with $\text{rtd}_2(X') \le \text{rtd}_2(X)$ such that for each covering $S_1, \dots, S_k$ of $V(T_{h,d'}(X'))$, there exists $i \in [k]$ such that $T_{h,d'}(X')$ contains an $\{H \subseteq T_{h,d'}(X') \mid H \text{ connected and } S_i \cap V(H) \ne \emptyset\}$-rich model of $T_{h,d'}(X)$ whose branch set corresponding to the root of $T_{h,d'}(X)$ contains the root of $T_{h,d'}(X')$.

*Proof.* We proceed by induction on $(\text{rtd}_2(X), h)$ in the lexicographic order. If $\text{rtd}_2(X) = 0$, then $X$ is the null graph, $T_{h,d'}(X) = K_1$, and the result holds.

<footnote n="6">⁶A *path decomposition* of $G$ is a tree decomposition $(T, (W_x \mid x \in V(T)))$ of $G$ where $T$ is a path. The *pathwidth* of $G$, denoted by $\text{pw}(G)$, is the minimum width of a path decomposition of $G$.</footnote>
Assume that $\mathrm{rtd}_2(X) > 0$ and that the result holds for every graph with rooted 2-treedepth less than $\mathrm{rtd}_2(X)$. By Lemma 28, there is a graph $Z$ such that $\mathrm{rtd}_2(Z) \le \mathrm{rtd}_2(X) - 1$ and $X \subseteq T_{h_1,d_1}(Z)$ for some positive integers $h_1$ and $d_1$.

By induction hypothesis applied to $h_1$, $d_1$, and $Z$, there exists a positive integer $d'_1$ and a graph $Y$ with $\mathrm{rtd}_2(Y) \le \mathrm{rtd}_2(Z)$ such that for each covering $S_1, \dots, S_k$ of $V(T_{h_1,d'_1}(Y))$, there exists $i \in [k]$ such that $T_{h_1,d'_1}(Y)$ contains an $\{H \subseteq T_{h_1,d'_1}(Y) \mid H \text{ connected and } S_i \cap V(H) \ne \emptyset\}$-rich model of $T_{h_1,d_1}(Z)$ (in particular of $X$) whose branch set corresponding to the root of $T_{h_1,d_1}(Z)$ contains the root of $T_{h_1,d'_1}(Y)$.

In the case of $h = 1$. Let $X' = (k+1) \cdot T_{h_1,d'_1}(Y)$ and $d' = 1$. In particular, $T_{1,d}(X') = K_1 \oplus ((k+1) \cdot T_{h_1,d'_1}(Y))$. By (r4) and Observation 27

$$ \mathrm{rtd}_2(X') = \mathrm{rtd}_2(T_{h_1,d'_1}(Y)) = 1 + \mathrm{rtd}_2(Y) \le 1 + \mathrm{rtd}_2(Z) \le \mathrm{rtd}_2(X). $$

Note that $T_{1,1}(X') = K_1 \oplus X' = K_1 \oplus ((k+1) \cdot T_{h_1,d'_1}(Y))$. Denote by $u$ the vertex of $K_1$ in $T_{1,1}(X')$ and by $H_1, \dots, H_{k+1}$ the copies of $T_{h_1,d'_1}(Y)$ in $T_{1,1}(X')$. Next, let $S_1, \dots, S_k$ be a covering of $T_{1,1}(X')$. For every $j \in [k+1]$, there exists $i_j \in [k]$ such that $H_j$ contains an $\{H \subseteq H_j \mid H \text{ connected and } S_{i_j} \cap V(H) \ne \emptyset\}$-rich model $(B_{j,x} \mid x \in V(X))$ of $X$. By the pigeonhole principle, there exist distinct $j_1, j_2 \in [k+1]$ such that $i_{j_1} = i_{j_2}$. Adding a branch set $\{u\} \cup \bigcup_{x \in V(X)} B_{j_2,x}$ to the model $(B_{j,x} \mid x \in V(X))$ gives a model of $T_{1,d}(X) = K_1 \oplus X$ in $T_{1,1}(X')$. The new branch set contains the root of $T_{1,1}(X')$ and corresponds to the root of $T_{1,d}(X)$. Finally, the obtained model is an $\{H \subseteq T_{1,1}(X') \mid H \text{ connected and } S_{i_1} \cap V(H) \ne \emptyset\}$-rich model.

Next, suppose that $h > 1$ and that the result holds for $h-1$. By induction hypothesis applied to $h-1$, $d$, and $X$, there exists a positive integer $d'_0$ and a graph $X'_0$ with $\mathrm{rtd}_2(X'_0) \le \mathrm{rtd}_2(X)$ such that for each covering $S_1, \dots, S_k$ of $V(T_{h-1,d'(X'_0)})$, there exists $i \in [k]$ such that $T_{h-1,d'_0}(X'_0)$ contains an $\{H \subseteq T_{h-1,d'_0}(X'_0) \mid H \text{ connected and } S_i \cap V(H) \ne \emptyset\}$-rich model of $T_{h-1,d}(X)$ whose branch set corresponding to the root of $T_{h-1,d}(X)$ contains the root of $T_{h-1,d'(X'_0)}$. Let $d' = d'_0 + (dk+1)$ and $X' = X'_0 \sqcup ((k+1) \cdot T_{h_1,d'_1}(Y))$. We claim that $X'$, $d'$ satisfy the conclusion of the lemma. By (r4) and Observation 27, $\mathrm{rtd}_2(X') \le \mathrm{rtd}_2(X)$.

Let $S_1, \dots, S_k$ be a covering of $V(T_{h,d'}(X'))$. Recall that $T_{h,d'}(X') = L_{d'}(K_1 \oplus X', T_{h-1,d'}(X'), s')$ where $s'$ is the root of $T_{h-1,d'}(X')$. For every $x \in V(K_1 \oplus X')$, let $H_{1,x}, \dots, H_{d',x}$ be the copies of $T_{h-1,d'}(X')$ such that $T_{h,d'}(X')$ is obtained from their disjoint union with $K_1 \oplus X'$ by identifying $x$ with the copies of $s'$ in each of $H_{1,x}, \dots, H_{d',x}$. Note that now $x$ is the root of $H_{j,x}$ for every $j \in [d']$ and $x \in V(K_1 \oplus X')$. Since $d' \ge d'_0$ and $X'_0 \subseteq X'$, for every $x \in V(K_1 \oplus X')$ and for every $j \in [d']$, there exists $i_{j,x} \in [k]$ such that $H_{j,x}$ contains an $\{H \subseteq T_{h-1,d'}(X') \mid H \text{ connected and } S_{i_{j,x}} \cap V(H) \ne \emptyset\}$-rich model $M_{j,x}$ of $T_{h-1,d}(X)$ whose branch set of the root of $T_{h-1,d}(X)$ contains $x$. Since $d' \ge dk+1$, for every $x \in V(K_1 \oplus X')$, by pigeonhole principle, there exists $i_x \in [k]$ and pairwise distinct $j_{1,x}, \dots, j_{d+1,x} \in [d']$ such that $i_{j_{\ell,x}} = i_x$ for every $\ell \in [d+1]$.

Let $H_1, \dots, H_{k+1}$ be the copies of $T_{h_1,d'_1}(Y)$ in $X'$. For every $j \in [k+1]$ and for every $\ell \in [k]$, let $S_{j,\ell} = \{x \in V(H_i) \mid i_x = \ell\}$. For every $j \in [k+1]$, $S_{j,1}, \dots, S_{j,k}$ is a covering of $V(H_j)$, therefore, there exists $\ell_j \in [k]$ such that $H_j$ contains an $\{H \subseteq H_i \mid H \text{ connected and } S_{j,\ell_j} \cap V(H) \ne \emptyset\}$-rich model $M_j$ of $X$. By pigeonhole principle, there exists distinct $j_1, j_2 \in [k+1]$ and $i \in [k]$ such that $\ell_{j_1} = \ell_{j_2} = i$ for some $i \in [k]$. Let $u$
be the vertex of $K_1$ in $k_1 \oplus X'$. Adding a branch set $\{u\} \cup \bigcup \mathcal{M}_2$ to the model $\mathcal{M}_1$ gives a model of an $\{H \subseteq K_1 \oplus X' \mid H \text{ connected and there is } x \in V(H) \text{ with } i_x = i\}$-rich model $(A_y \mid y \in V(K_1 \oplus X))$ of $K_1 \oplus X$ in $K_1 \oplus X'$. For every $y \in V(K_1 \oplus X)$, let $x_y \in A_y$ be such that $i_{x_y} = i$ and let $B_y = A_y \cup \bigcup \mathcal{M}_{j_{d+1}, x_y}$. Finally, consider the model obtained from $(B_y \mid y \in V(K_1 \oplus X))$ by adding all the models $\mathcal{M}_{j_{1,x_y}, x_y}, \dots, \mathcal{M}_{j_{d,x_y}, x_y}$ for every $y \in V(K_1 \oplus X)$. We obtain an $\{H \subseteq T_{h,d'}(X') \mid H \text{ connected and } S_i \cap V(H) \neq \emptyset\}$-rich model of $T_{h,d}(X)$ whose branch set of the root of $T_{h,d}(X)$ contains the root of $T_{h,d'}(X')$. $\square$

**7.2. The base case.** Recall that for all positive integers $h$ and $d$, we denote by $F_{h,d}$ the (rooted) complete $d$-ary tree of vertex-height $h$.

This first lemma is a modification of a proof in [3].

**Lemma 40.** Let $d$ be a positive integer. Let $G$ be a connected graph, let $\mathcal{D} = (T, (W_x \mid x \in V(T)))$ be a tree decomposition of $G$, and let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$ such that $G$ has no $\mathcal{F}$-rich model of $F_{2,d}$. For every $u \in V(G)$, there is a set $S \subseteq V(G)$ and a layering $(P_0, \dots, P_\ell)$ of $G[S]$ with $P_0 = \{u\}$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) for every component $C$ of $G-S$, $N_G(V(C)) \subseteq P_i \cup P_j$ for some $i, j \in \{0, \dots, \ell\}$ and either $i = j$ or $j = i + 1$;

(c) for every $i \in [\ell]$, $P_i$ is contained in the union of at most $d$ bags of $\mathcal{D}$.

*Proof.* We illustrate some parts of the proof in Figure 17. We proceed by induction on $|V(G)|$. If $\mathcal{F}|_{G-\{u\}}$ is empty, then it suffices to take $\ell = 0$ and $P_0 = \{u\}$. In particular, this is the case for $|V(G)| = 1$. Therefore, assume $|V(G)| > 1$ and $\mathcal{F}|_{G-\{u\}} \neq \emptyset$. Let $\mathcal{F}_0$ be the family of all the nonnull connected subgraphs $A$ of $G - \{u\}$ such that $A$ contains some member of $\mathcal{F}$ and $V(A) \cap N_G(u) \neq \emptyset$. Since $\mathcal{F}|_{G-\{u\}} \neq \emptyset$ and $G$ is connected, $\mathcal{F}_0$ is nonempty.

Observe that any collection of $d+1$ pairwise disjoint $A_1, \dots, A_{d+1} \in \mathcal{F}_0$ yields an $\mathcal{F}$-rich model of $F_{2,d}$ in $G$. Indeed, it suffices to take $\{u\} \cup A_{d+1}$ as the branch set corresponding to the root of $F_{2,d}$ and $A_1, \dots, A_d$ as the branch sets of the remaining $d$ vertices of $F_{2,d}$. Therefore, there is at most $d$ pairwise disjoint members of $\mathcal{F}_0$, and thus, by Lemma 35 applied to $G - \{u\}$ and $\mathcal{F}_0$, there exists a set $Z \subseteq V(G - \{u\})$ included in the union of at most $d$ bags of $\mathcal{D}$ such that $Z \cap V(F) \neq \emptyset$ for every $F \in \mathcal{F}_0$. Suppose that $Z$ is inclusion-wise minimal for this property. Note that since $\mathcal{F}_0 \neq \emptyset$, $Z$ is nonempty.

Let $\mathcal{C}_0$ be the family of all the components $C$ of $G - (\{u\} \cup Z)$ such that $N_G(u) \cap V(C) = \emptyset$. Let $W = \bigcup_{C \in \mathcal{C}_0} V(C)$. Let $z \in Z$. By the minimality of $Z$, there exists $A_z \in \mathcal{F}_0$ with $V(A_z) \cap (Z - z) = \emptyset$. We have $A_z - \{z\} \notin \mathcal{F}_0$, thus, $z \in V(A_z)$. Since $A_z \in \mathcal{F}_0$, $V(A_z) \cap N_G(u) \neq \emptyset$, and so, there is a $u-z$ path $Q_z$ in $G[\{u\} \cup A_z] \subseteq G - (Z - z)$. For every component $C \in \mathcal{C}_0$, we have $V(C) \cap V(Q_z) = \emptyset$, hence, $W \cap V(Q_z) = \emptyset$.

Let $Q = \bigcup_{z \in Z} V(Q_z)$ and let $G'$ be the graph obtained from $G[W \cup Q]$ by contracting $Q$ into a single vertex $u'$. Note that $G'$ is a minor of $G$, and $V(G') = \{u'\} \cup W$. Moreover, since $Z \neq \emptyset$, we have $|V(G')| < |V(G)|$.
<figure><img src="image_18.png" /><figcaption>FIGURE 17. An illustration of the proof of Lemma 40.</figcaption></figure>

For every $x \in V(T)$, let

$$W'_{x} = \begin{cases} W_{x} & \text{if } W_{x} \subseteq W \\ (W_{x} \cap W) \cup \{u'\} & \text{otherwise.} \end{cases}$$

It follows that $\mathcal{D}' = (T, (W'_x | x \in V(T)))$ is a tree decomposition of $G'$. By induction hypothesis applied on $G', \mathcal{D}', u', \mathcal{F}|_{G[W]}$, there is a set $S' \subseteq V(G')$ and a layering $(P'_0, \dots, P'_{\ell'})$ of $G'[S']$ with $P'_0 = \{u'\}$ such that

(a') $V(F) \cap S' \neq \emptyset$ for every $F \in \mathcal{F}|_{G[W]}$;

(b') for every component $C$ of $G[W] - S'$, $N_G(V(C)) \subseteq P'_i \cup P'_j$ for some $i, j \in \{0, \dots, \ell'\}$ with either $i = j$ or $j = i + 1$;

(c') for every $i \in [\ell']$, $P'_i$ is contained in the union of at most $d$ bags of $\mathcal{D}'$.

Let $S = \{u\} \cup Z \cup (S' - \{u'\})$, $P_0 = \{u\}$, $P_1 = Z$, and $P_i = P_{i-1}'$ for every $i \in \{2, \dots, \ell' + 1\}$ – we set $\ell = \ell' + 1$. We claim that $(P_0, \dots, P_\ell)$ is a layering of $G[S]$ satisfying (a)-(c), which will complete the proof of the lemma.

Let $i, j \in \{0, \dots, \ell\}$ with $i < j$ and assume that there is an edge a vertex in $P_i$ and a vertex in $P_j$ in $G$. If $i \ge 2$, then $P_i \subseteq P_{i-1}'$ and $P_j = P_{j-1}'$, which implies $|i - j| \le 1$ since $(P'_0, \dots, P'_{\ell'})$ is a layering of $G'[S']$. Otherwise, $i \in \{0, 1\}$. If $i = 0$, then $j = 1$ since $u$ has no neighbors in $W$. If $i = 1$, then $j = 2$ since $N_{G'}(u') \subseteq P'_1$. It follows that $(P_0, \dots, P_\ell)$ is a layering of $G[S]$.

Let $F \in \mathcal{F}$. If $V(F) \cap (\{u\} \cup Z) \neq \emptyset$, then $V(F) \cap S \neq \emptyset$. Otherwise, $F \subseteq C$ for some component of $G - (\{u\} \cup Z)$, and in particular, $C \notin \mathcal{F}'$. In this case, $N_G(u) \cap V(C)$, hence, $C \in \mathcal{C}_0$, thus, $F \in \mathcal{F}|_{G[W]}$, and finally, $V(F) \cap S' \neq \emptyset$ by (a'). This proves (a).

For every component $C$ of $G - S$, either $C \cap W = \emptyset$ and so $N(V(C)) \subseteq \{u\} \cup Z = P_0 \cup P_1$, or $V(C) \subseteq W$, and so $C$ is a component of $G' - S'$. It follows that there exists $i, j \in \{0, \dots, \ell'\}$ with $|i - j| \le 1$ such that $N_{G'}(V(C)) \subseteq P'_i \cup P'_j$ and so $N_G(V(C)) \subseteq P_{i+1} \cup P_{j+1}$. This proves (b).

Finally, $P_0$ is contained in one bag of $\mathcal{D}$, $P_1$ is contained in at most $d$ bags of $\mathcal{D}$ by the definition of $Z$, and for every $i \in \{2, \dots, \ell\}$, $P_i$ is contained in at most $d$ bags of $\mathcal{D}$ by (c'). Therefore, (c) holds, which concludes the proof of the lemma. $\square$
Recall that in the base case of the proof of Theorem 5 (see Section 5), we applied the ideas required to prove that positive integer $r$ and for every path $P$, $wcol_r(P) \le 1 + \lfloor \log r \rfloor$. We illustrated these ideas in Figure 10. In this section, it suffices to use this result as a black box. We state it here for reference.

**Lemma 41 ([13]).** For every positive integer $r$ and for every path $P$, $wcol_r(P) \le 1 + \lfloor \log r \rfloor$.

**Lemma 42.** Let $k, d$ be positive integers. For every graph $G$, for every tree decomposition $\mathcal{D}$ of $G$ of width at most $k-1$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $F_{2,d}$, then there is a set $S \subseteq V(G)$ such that

(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

(b) for every component $C$ of $G-S$, $N_G(V(C))$ is contained in the union of at most $d$ bags of $\mathcal{D}$;

(c) $wcol_r(G, S) \le 6dk \cdot \log r$ for every integer $r$ with $r \ge 2$.

*Proof.* Let $G$ be a graph, let $\mathcal{D}$ be a tree decomposition of $G$ of width at most $k-1$, let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$, and suppose that $G$ has no $\mathcal{F}$-rich model of $F_{2,d}$. Let $r$ be an integer with $r \ge 2$. By considering the components of $G$ independently, we can assume that $G$ is connected. Let $u$ be an arbitrary vertex in $G$. Lemma 40 applied to $G$, $\mathcal{D}$, $\mathcal{F}$, and $u$ gives $S \subseteq V(G)$, a layering $(P_0, \dots, P_\ell)$ of $G[S]$ with $P_0 = \{u\}$ such that

40.(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

40.(b) for every component $C$ of $G-S$, $N_G(V(C)) \subseteq P_i \cup P_j$ for some $i, j \in \{0, \dots, \ell\}$ and either $i = j$ or $j = i + 1$;

40.(c) for every $i \in [\ell]$, $P_i$ is contained in the union of at most $d$ bags of $\mathcal{D}$.

Note that (a) holds by 40.(a) and (b) holds by 40.(b). In order to conclude the proof, it suffices to show (c).

For convenience, let $P_{\ell+1} = \emptyset$. Consider the path $Q$ with $V(Q) = \{0, \dots, \ell+1\}$ where two numbers are connected by an edge whenever they are consecutive. Let $\sigma' = i_0 \dots i_\ell$ be an ordering of $\{0, \dots, \ell+1\}$ given by Lemma 41, that is, $wcol_r(Q, \sigma') \le 1 + \lfloor \log r \rfloor \le 3 \log r$. For each $i \in \{0, \dots, \ell+1\}$, let $\sigma_i$ be an arbitrary ordering of $P_i$. Let $\sigma$ be the concatenation of $\sigma_{i_0} \dots \sigma_{i_{\ell+1}}$ in this order.

Let $u \in V(G)$. To conclude the claim, we argue that

$$|\text{WReach}_r[G, S, \sigma, u]| \le 6dk \cdot \log r.$$

Let $i_u \in V(T)$ be such that if $u \in S$, then $u \in P_{i_u}$, and otherwise, $i_u \in \{0, \dots, \ell\}$ is the least value such that $P_{i_u}$ intersects $N_G(C)$, where $C$ is the component of $u$ in $G-S$. Let $A = \text{WReach}_r[Q, \sigma', i_u] \cup \text{WReach}_r[Q, \sigma', i_u+1]$. In particular, $|A| \le 2 \cdot wcol_r(Q, \sigma') \le 2 \cdot 3 \log r$ By 40.(b),

$$\text{WReach}[G, S, \sigma, u] \subseteq \bigcup_{j \in A} P_j.$$

By 40.(c), for every $j \in \{0, \dots, \ell+1\}$, $P_j$ is contained in the union of at most $d$ bags of $\mathcal{D}$ and since the width of $\mathcal{D}$ is at most $k-1$, we have $|P_j| \le dk$. It follows that

$$|\text{WReach}[G, S, \sigma, u]| \le |A| \cdot dk \le 6dk \log r.$$

□
**Lemma 43.** Let $k, h, d$ be positive integers with $h \ge 2$. There is an integer $\bar{c}_0(h, d)$ such that for every graph $G$, for every tree decomposition $\mathcal{D}$ of $G$ of width at most $k-1$ for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $F_{h,d}$, then there is a set $S \subseteq V(G)$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$,

(b) for every component $C$ of $G-S$, $N_G(V(C))$ is contained in the union of at most $d(h-1) + \binom{h-1}{2}$ bags of $\mathcal{D}$;

(c) $\mathrm{wcol}_r(\bar{G}, S) \le \bar{c}_0(h, d)k \cdot \log r$ for every integer $r$ with $r \ge 2$.

*Proof.* We proceed by induction on $h$. For $h=2$, the result holds by Lemma 42 setting $\bar{c}_0(h, d) = 6dk$, since $d(2-1) + \binom{2-1}{2} = d$. Next, assume $h \ge 3$ and that $\bar{c}(h, d)$ witnesses the assertion for $h-1$. Let $\bar{c}_0(h, d) = 6d + \bar{c}_0(h-1, d+1)$.

Let $G$ be a graph and let $\mathcal{D}$ be a tree decomposition of $G$ of width at most $k-1$. Let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$. Let $r$ be an integer with $r \ge 2$. Let $\mathcal{F}'$ be the family of all the connected subgraphs $H$ of $G$ such that $H$ contains an $\mathcal{F}|_{H}$-rich model of $F_{h-1,d+1}$. We claim that there is no $\mathcal{F}'$-rich model of $F_{2,d}$ in $G$. Suppose to the contrary that $(B_x | x \in V(F_{2,d}))$ is such a model. Let $s$ be the root of $F_{2,d}$ and let $s'$ be the root of $F_{h-1,d}$. For every $x \in V(F_{2,d}) - \{s\}$, by Lemma 32, there is an $\mathcal{F}$-rich model $(C_y | y \in V(F_{h-1,d}))$ of $F_{h-1,d}$ in $G[B_x]$ such that $C_{s'}$ contains a vertex of $N_G(B_s) \cap B_x$. The union of these models together with $B_s$ yields an $\mathcal{F}$-rich model of $F_{h,d}$ in $G$, which is a contradiction. Note that this is exactly the same argument as in Lemma 33, see Figure 11.

Since $G$ has no $\mathcal{F}'$-rich model of $F_{2,d}$, by Lemma 42, there is a set $S_0 \subseteq V(G)$ such that

42.(a) for every $F \in \mathcal{F}'$, $V(F) \cap S_0 \neq \emptyset$;

42.(b) for every component $C$ of $G-S_0$, $N_G(V(C))$ is contained in the union of at most $d$ bags of $\mathcal{D}$;

42.(c) $\mathrm{wcol}_r(G, S_0) \le 6dk \cdot \log r$.

Let $C$ be a component of $G-S_0$. Let $\mathcal{D}_C$ be $\mathcal{D}$ restricted to $C$. By 42.(a), $C \notin \mathcal{F}'$, and so, $C$ has no $\mathcal{F}|_C$-rich model of $F_{h-1,d+1}$. Therefore, by induction hypothesis, there is a set $S_C \subseteq V(C)$ such that

(a') $V(F) \cap S_C \neq \emptyset$ for every $F \in \mathcal{F}|_C$;

(b') for every component $C'$ of $C - S_C$, $N_C(V(C'))$ is contained in the union of at most $(d+1)(h-2) + \binom{h-2}{2} = d(h-1) + \binom{h-1}{2} - d$ bags of $\mathcal{D}_C$;

(c') $\mathrm{wcol}_r(C, S_C) \le \bar{c}_0(h-1, d+1)k \cdot \log r$.

Let $C$ be the family of components of $G-S_0$ and let

$$S = S_0 \cup \bigcup_{C \in C} S_C.$$

We claim that (a)-(c) hold. Let $F \in \mathcal{F}$. If $V(F) \cap S_0 = \emptyset$, then $V(F) \subseteq V(C)$ for some component $C$ of $G-S_0$. In particular, $F \in \mathcal{F}|_C$, and thus, by (a'), $V(F) \cap S_C \neq \emptyset$, which proves (a). For every component $C'$ of $G-S$, there exists a component $C$ of $G-S_0$ such that $C' \subseteq C$ and by 42.(b) and (b'), $N_G(C')$ is contained in at most $d + (d(h-1) + \binom{h-1}{2} - d) = d(h-1) + \binom{h-1}{2}$ bags of $\mathcal{D}$, which implies (b).
The following sequence of inequalities concludes the proof of (c) and the lemma:

$$
\begin{align*}
wcol_r(G, S) &\le wcol_r(G, S_0) + wcol_r\left(G - S_0, \bigcup_{C \in \mathcal{C}} S_C\right) &\text{by Observation 12} \\
&\le wcol_r(G, S_0) + \max_{C \in \mathcal{C}} wcol_r(C, S_C) &\text{by Observation 11} \\
&\le 6dk \cdot \log r + \bar{c}_0(h-1, d+1)k \cdot \log r &\text{by 42.(c) and (c')} \\
&= \bar{c}_0(h, d)k \cdot \log r. &\square
\end{align*}
$$

We now show that using Lemma 37, the constant $d(h-1) + \binom{h-1}{2}$ in (b) in Lemma 43 can be
reduced to two.

**Lemma 44.** Let $k, h, d$ be positive integers with $h \ge 2$. For every graph $G$ with $\mathrm{tw}(G) < k$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $F_{h,d}$, then there is a set $S \subseteq V(G)$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) for every component $C$ of $G-S$, $N_G(V(C))$ intersects at most two components of $G-V(C)$;

(c) $wcol_r(G, S) \le (\bar{c}_0(h, d) + 2dh^2) k \cdot \log r$ for every integer $r$ with $r \ge 2$, where $\bar{c}_0(h, d)$ is the constant from Lemma 43.

*Proof.* Let $G$ be a graph and let $\mathcal{D}$ be a tree decomposition of $G$ of width at most $k-1$. By Lemma 36, we can assume that $\mathcal{D}$ is a natural tree decomposition of $G$. By Lemma 42 applies to $G$, $\mathcal{D}$, and $\mathcal{F}$, there is a set $S_0 \subseteq V(G)$ such that

42.(a) $V(F) \cap S_0 \neq \emptyset$ for every $F \in \mathcal{F}$,

42.(b) for every component $C$ of $G - S_0$, $N_G(V(C))$ is contained in the union of at most $d(h-1) + \binom{h-1}{2}$ bags of $\mathcal{D}$;

42.(c) $wcol_r(G, S_0) \le \bar{c}_0(h, d)k \cdot \log r$ for every integer $r$ with $r \ge 2$.

Let $C$ be a component of $G - S_0$. By 42.(b) and Lemma 37, there exists a family $\mathcal{B}_C$ of at most $2\left(d(h-1) + \binom{h-1}{2}\right) - 1 \le 2dh^2$ bags of $\mathcal{D}$ such that $N_G(V(C)) \subseteq \bigcup \mathcal{B}_C$ and for every component $C'$ of $G - \bigcup \mathcal{B}_C$, $N_G(V(C'))$ intersects at most two components of $G - V(C')$. Let $S_C = V(C) \cap \bigcup \mathcal{B}_C$. Then, for every component $C'$ of $G - (S_0 \cup S_C)$ intersecting $V(C)$, $C$ is a component of $G - \bigcup \mathcal{B}_C$, and so $N_G(V(C'))$ intersects at most two component of $G - V(C')$.

Let $C$ be the family of all the components of $G - S_0$ and let

$$
S = S_0 \cup \bigcup_{C \in \mathcal{C}} S_C.
$$
Item (b) follows from the previous considerations and (a) follows directly from 42.(a). Now, it suffices to justify (c). To this end, let $r$ be an integer with $r \ge 2$. Then,

$$ wcol_r(G, S) \le wcol_r(G, S_0) + wcol_r \left( G - S_0, \bigcup_{C \in \mathcal{C}} S_C \right) \quad \text{by Observation 12} $$

$$ \le wcol_r(G, S_0) + \max_{C \in \mathcal{C}} wcol_r(C, S_C) \quad \text{by Observation 11} $$

$$ \le wcol_r(G, S_0) + \max_{C \in \mathcal{C}} |S_C| $$

$$ \le \bar{c}_0(h, d)k \cdot \log r + 2dh^2k \quad \text{by 42.(c)} $$

$$ \le (\bar{c}_0(h, d) + 2dh^2) k \cdot \log r. \quad \square $$

<figure><img src="image_19.png" /></figure>

### 7.3. Induction.
We can now prove Theorem 6 in the following stronger version, which is very similar to Theorem 8, with a slightly relaxed condition (B). Note that the following proof and the one of Theorem 8 largely overlap, but since there is no non-artificial way to merge them, we elect to give full proofs of both theorems.

**Theorem 45.** Let $t$ be positive integers with $t \ge 2$. Let $X$ be a graph with $rtd_2(X) \le t$. There exist an integer $\bar{c}(t, X)$ such that for every integer $k$, for every graph $G$ with $\mathrm{tw}(G) < k$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $X$, then there exists $S \subseteq V(G)$ such that

(A) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

(B) for every component $C$ of $G-S$, $N_G(V(C))$ intersects at most two components of $G-V(C)$;

(C) $wcol_r(G, S) \le \bar{c}(t, X)k \cdot r^{t-2} \log r$ for every integer $r$ with $r \ge 2$.

*Proof.* We proceed by induction on $t$. When $t=2$, by Observation 21, $X$ is a forest. Let $h, d$ be positive integers such that $X \subseteq F_{h,d}$, and let $\bar{c}_0(h, d)$ be the constant given by Lemma 44. The assertion with $\bar{c}(t, X) = \bar{c}_0(h, d) + 2dh^2$ follows by applying Lemma 44. Next, let $t \ge 3$, and assume that the result holds for $t-1$. We refer to this property as the main induction hypothesis.

**Claim 4.** Let $Y$ be a graph with $rtd_2(Y) \le t-1$. There is an integer $\bar{c}_1(t, Y)$ such that for every positive integer $k$, for every connected graph $G$ with $\mathrm{tw}(G) < k$, for every nonempty set $U$ of vertices of $G$ with $|U| \le 2$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $K_1 \oplus Y$, then there exist $S \subseteq V(G)$, a tree $T$ rooted in $s \in V(T)$, and a tree partition $(T, (P_x | x \in V(T)))$ of $G[S]$ with $P_s = U$ such that

(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

(b) for every component $C$ of $G-S$, $N_G(V(C))$ intersects at most four components of $G-V(C)$;

(c) for every component $C$ of $G-S$, $N_G(V(C)) \subseteq P_x \cup P_y$ for some $x, y \in V(T)$ with either $x = y$ or $xy$ is an edge in $T$;

(d) for every $x \in V(T)$ let $T_x$ be the subtree of $T$ rooted in $x$, then

$$ wcol_r \left( G \left[ \bigcup_{y \in V(T_x)} P_y \right], P_x \right) \le \bar{c}_1(t, Y)k \cdot r^{t-3} \log r $$
for every integer $r$ with $r \ge 2$.

**Proof of the claim.** Let $X' = K_1 \sqcup Y$. By Lemma 38 applied to $k=2$ and $X'$, there exists a graph $X''$ with $\mathrm{rtd}_2(X'') = \mathrm{rtd}_2(X') = t$ such that for every covering $S_1, S_2$ of $V(X'')$ there exists $i \in \{1, 2\}$ such that $X''$ contains an $\{H \subseteq X'' \mid H \text{ connected and } S_i \cap V(H) \neq \emptyset\}$-rich model of $X'$. Let $\bar{c}_1(t, Y) = 2 + \bar{c}(t - 1, X'')$.

We proceed by induction on $|V(G)|$. If $\mathcal{F}|_{G-U} = \emptyset$, then since $\bar{c}_1(t, Y) \ge |U|$, the result holds. Now suppose that $\mathcal{F}|_{G-U} \ne \emptyset$ and in particular, $|V(G) - U| > 1$.

Assume that $G - U$ is not connected. Let $\mathcal{C}$ be the family of all the components of $G - U$. Consider a component $C \in \mathcal{C}$. By induction hypothesis applied to $G_C = G[V(C) \cup U]$, $U$, and $\mathcal{F}|_{G_C}$, there exist $S_C \subseteq V(G_C)$, a tree $T_C$ rooted in $s_C \in V(T_C)$, and a tree partition $(T_C, (P_{C,x} \mid x \in V(T_C)))$ of $S_C$ in $G_C$ with $P_{C,s_C} = U$ such that

(a') $V(F) \cap S_C \neq \emptyset$ for every $F \in \mathcal{F}|_{G[V(C) \cup U]}$;

(b') for every component $C'$ of $G_C - S_C$, $N_G(V(C'))$ intersects at most four components of $G_C - V(C')$;

(c') for every component $C'$ of $G_C - S_C$, $N_{G_C}(V(C')) \subseteq P_{C,x} \cup P_{C,y}$ for some $x, y \in V(T_C)$ and either $x = y$ or $xy$ is an edge in $T_C$;

(d') for every $x \in V(T_C)$ let $T_{C,x}$ be the subtree of $T_C$ rooted in $x$, then

$$ \mathrm{wcol}_r \left( G_C \left[ \bigcup_{y \in V(T_C, x)} P_{C,y} \right], P_{C,x} \right) \le \bar{c}_1(t, Y)k \cdot r^{t-3} \log r $$

for every integer $r$ with $r \ge 2$.

Then let $S = \bigcup_{C \in \mathcal{C}} S_C$, let $T$ be the tree obtained from the disjoint union of all the $T_C$ for $C \in \mathcal{C}$ by identifying all the vertices in $\{s_C \mid C \in \mathcal{C}\}$ into a single vertex $s$. Finally, let $P_s = U$ and $P_x = P_{C,x}$ for every $C \in \mathcal{C}$ and $x \in V(T_C) - \{s_C\}$. Then we claim that (a)-(d) hold. Indeed, for every $F \in \mathcal{F}$, $F$ is connected so either $F$ is a subgraph of $G - U$ or $F$ intersects $U$. In both cases, we see that $V(F) \cap S \neq \emptyset$, so (a) holds. Item (b) holds by (b') as $U \subseteq S_C$ for all $C \in \mathcal{C}$. Item (c) holds as every component of $G - S$ is a component of $G_C - S_C$ for some $C \in \mathcal{C}$. Finally, for all $x \in V(T)$ with $x \neq s$ item (d) follows directly from (d') and the construction of $T$, while when $x = s$, $\mathrm{wcol}_r(G[\bigcup_{y \in V(T)} P_y], P_s) = |U| \le 2$ for every integer $r$ with $r \ge 2$. From now on we assume that $G - U$ is connected.

Let $\mathcal{F}'$ be the family of all the nonnull connected subgraphs $H$ of $G - U$ such that $U \cap N_G(V(H)) \neq \emptyset$ and $F \subseteq H$ for some $F \in \mathcal{F}$. We argue that there is no $\mathcal{F}'$-rich model of $X''$ in $G - U$. Suppose to the contrary that there is an $\mathcal{F}'$-rich model $(B_x \mid x \in V(X''))$ of $X''$ in $G - U$. For each $u \in U$, let $S_u = \{x \in V(X'') \mid u \in N_G(B_x)\}$. Since the model is $\mathcal{F}'$-rich, $\{S_u\}_{u \in U}$ is a covering of $V(X'')$. Therefore, there exists $u \in U$ such that $X''$ contains an $\{H \subseteq X'' \mid H \text{ connected and } S_u \cap V(H) \neq \emptyset\}$-rich model $\mathcal{M}$ of $X'$. Moreover, by definition, each branch set of $\mathcal{M}$ contains a member of $\mathcal{F}$, and furthermore, $\mathcal{M}$ is a model of $X'$ in $G$. Recall that $X' = K_1 \sqcup Y$. If $v$ is the vertex of $K_1$ is $X'$, then the model obtained from $\mathcal{M}$ by replacing the branch set $C_v$ corresponding to $v$ by $C_v \cup \{u\}$ yields an $\mathcal{F}$-rich model of $K_1 \oplus Y$ in $G$, which is a contradiction. This proves that there is no $\mathcal{F}'$-rich model of $X'$ in $G - \{u\}$.
Since $\mathrm{rtd}_2(X'') = \mathrm{rtd}_2(X') \le \max\{\mathrm{rtd}_2(Y), 1\} \le t-1$, by the main induction hypothesis applied to $X'', G-U$, and $\mathcal{F}'$ there exists a set $S_0 \subseteq V(G-U)$ such that

(A') $V(F) \cap S_0 \ne \emptyset$ for every $F \in \mathcal{F}'$;

(B') for every component $C$ of $(G-U)-S_0$, $N_{G-U}(V(C))$ intersects at most two components of $(G-U)-V(C)$;

(C') $\mathrm{wcol}_r(G-U, S) \le \bar{c}(t-1, X'')k \cdot r^{t-3} \log r$ for every integer $r$ with $r \ge 2$.

Note that $S_0 \ne \emptyset$ since $\mathcal{F}' \ne \emptyset$.

Let $C_1$ be the family of all the components $C$ of $(G-U)-S_0$ such that $N_G(U) \cap V(C) = \emptyset$. Consider $C \in C_1$. Let $G_C$ be the graph obtained from $G[V(C) \cup N_G(V(C))]$ by contracting each component $C'$ of $(G-U)-V(C)$ into a single vertex. Let $U_C$ be the set of all the vertices resulting from these contractions. Note that $U_C$ is not empty since $G$ is connected, and $|U_C| \le 2$ by (B'). Since $N_G(U) \cap V(C) = \emptyset$, $|V(G_C)| < |V(G)|$. Since $G_C$ is a minor of $G$, $G_C$ has no $\mathcal{F}|_{C}$-rich model of $K_1 \oplus Y$. By induction hypothesis applied to $G_C$, $u_C$, and $\mathcal{F}|_C$, there exist $S_C \subseteq V(G_C)$, a tree $T_C$ rooted in $s_C \in V(T_C)$, and a tree partition $(T_C, (P_{C,x} | x \in V(T_C)))$ of $S_C$ in $G_C$ with $P_{C,s_C} = U$ such that

(a'') $V(F) \cap S_C \ne \emptyset$ for every $F \in \mathcal{F}|_C$;

(b'') for every component $C'$ of $G_C - S_C$, $N_G(V(C'))$ intersects at most four components of $G_C - V(C')$;

(c'') for every component $C'$ of $G_C - S_C$, $N_{G_C}(V(C')) \subseteq P_{C,x} \cup P_{C,y}$ for some $x, y \in V(T_C)$ and either $x = y$ or $xy$ is an edge in $T_C$;

(d'') for every $x \in V(T_C)$ let $T_{C,x}$ be the subtree of $T_C$ rooted in $x$, then

$$ \mathrm{wcol}_r \left( G_C \left[ \bigcup_{y \in V(T_{C,x})} P_{C,y} \right], P_{C,x} \right) \le \bar{c}_1(t, Y)k \cdot r^{t-3} \log r $$

for every integer $r$ with $r \ge 2$.

Let

$$ S = U \cup S_0 \cup \bigcup_{C \in C_1} (S_C - U_C). $$

Let $T$ be obtained from the disjoint union of $\{T_C | C \in C_1\}$ by identifying the vertices $\{s_C | C \in C_1\}$ into a new vertex $s'$ and by adding a new vertex $s$ adjacent to $s'$ in $T$. Let $P_s = U$, $P_{s'} = S_0$, and for each $C \in C_1$, $x \in V(T_C - \{s_C\})$, let $P_x = P_{C,x}$.

In order to conclude, we argue that $(T, (P_x | x \in V(T)))$ is a tree partition of $G[S]$ and (a)-(d) hold.

Since for every $C \in C_1$, $U \cap N_G(V(C)) = \emptyset$, every edge in $G[S]$ containing a vertex in $U$ has another endpoint in $U \cup S_0 = P_s \cup P_{s'}$. Consider an edge $vw$ in $G[S]$ such that $v \in S_0$ and $w \in S_C$ for some $C \in C_1$. Since $(T_C, (P_{C,x} | x \in V(T_C)))$ is a tree partition of $G_C[S_C]$ with $P_{C,s_C} = U_C$ and $S_0 \subseteq V((G-U)-V(C))$, we conclude that $w \in P_x$ for some $x \in V(T_C)$ such that $s'x$ is an edge in $T$. Finally, for every edge $vw$ of $G[S]$ with $v, w \notin U \cup S_0$, $vw$ is an edge of $G[S_C - U_C]$ for some component $C \in C_1$, and so $v \in P_{C,x}$ and $w \in P_{C,y}$ for adjacent or identical vertices $x, y$ of $T_C$. Then $v \in P_x$ and $w \in P_y$. It follows that $(T, (P_x | x \in V(T)))$ is a tree partition of $G[S]$.
Let $F \in \mathcal{F}$. If $V(F) \cap (U \cup S_0) \neq \emptyset$, then $V(F) \cap S \neq \emptyset$. Otherwise, $F \subseteq G - U$ and $V(F) \cap S_0 = \emptyset$, and therefore by (A'), $F \notin \mathcal{F}'$, so in particular, $U \cap N_G(V(F)) = \emptyset$. In this case, there is a component $C \in \mathcal{C}_1$ such that $F \in \mathcal{F}|_C$, thus, $V(F) \cap S_C \neq \emptyset$ by (a''). This proves (a).

Consider a component $C'$ of $G - S$. If $C' \subseteq C$ for some $C \in \mathcal{C}_1$, then by (b''), it follows that $N_{G_C}(V(C'))$ intersects at most four components of $G_C - V(C')$, and so $N_G(V(C'))$ intersects at most four components of $G - V(C')$. Otherwise, $C'$ is a component of $(G - U) - S_0$ such that $N_G(U) \cap V(C') \neq \emptyset$. By (B'), $N_{G-U}(V(C'))$ intersects at most two components of $(G - U) - V(C')$, and therefore, $N_G(V(C'))$ intersects at most four components of $G - V(C')$. This proves (b).

For every component $C'$ of $G - S$, either $N_G(V(C')) \subseteq U \cup S_0 = P_s \cup P_{s'}$, or $C' \subseteq C$ for some $C \in \mathcal{C}_1$. In the latter case, $C'$ is a component of $G_C - S_C$, and $N_G(U) \cap V(C) = \emptyset$. By (c''), there is $x, y \in V(T_C)$ such that $N_{G_C}(V(C')) \subseteq P_{C,x} \cup P_{C,y}$, and thus, $N_G(V(C')) \subseteq P_x \cup P_y$. This proves (c).

Finally, we argue (d). Let $r$ be an integer with $r \ge 2$ and let $x \in V(T)$. For $x = s$, $|P_s| = |U| \le 2$, thus the assertion is clear. For $x = s'$, we have $T_{s'} = V(G) - U$. By (C'),

$$ \mathrm{wcol}_r(G - U, S_0) \le \bar{c}(t - 1, X'')k \cdot r^{t-3} \log r \le \bar{c}_1(t, Y)k \cdot r^{t-3} \log r. $$

For $x \in V(T_C - \{s_C\})$ for some $C \in \mathcal{C}_1$, we have $T_x = T_{C,x}$, thus, the asserted inequality follows from (d''). This ends the proof of the claim. $\diamond$

Claim 4 yields the following less technical statement.

Claim 5. Let $Y$ be a graph with $rtd_2(Y) \le t - 1$. There are integers $\bar{c}_2(t, Y)$ such that for every positive integer $k$, for every graph $G$ with $\mathrm{tw}(G) < k$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $K_1 \oplus Y$, then there exist $S \subseteq V(G)$ such that

(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

(b) for every component $C$ of $G-S$, $N_G(V(C))$ intersects at most four components of $G-V(C)$;

(c) $\mathrm{wcol}_r(G, S) \le \bar{c}_2(t, Y)k \cdot r^{t-2} \log r$ for every integer $r$ with $r \ge 2$.

Proof of the claim. Let $\bar{c}_2(t, Y) = 2 \cdot \bar{c}_1(t, Y)$ and let $r$ be an integer with $r \ge 2$. We apply Claim 4 with an arbitrary singleton $U$ in $G$ to obtain $S \subseteq V(G)$, a tree $T$ rooted in $s \in V(T)$, and a tree partition $(T, (P_x | x \in V(T)))$ of $S$ in $G$ with $P_s = \{u\}$ such that

4.(a) $V(F) \cap S \neq \emptyset$ for every $F \in \mathcal{F}$;

4.(b) for every component $C$ of $G - S$, $N_G(V(C))$ intersects at most four components of $G - V(C)$;

4.(c) for every component $C$ of $G - S$, $N_G(V(C)) \subseteq P_x \cup P_y$ for some $x, y \in V(T)$ with either $x = y$ or $xy$ is an edge in $T$;

4.(d) for every $x \in V(T)$ let $T_x$ be the subtree of $T$ rooted in $x$, then

$$ \mathrm{wcol}_r \left( G \left[ \bigcup_{y \in V(T_x)} P_y \right], P_x \right) \le \bar{c}_1(t, Y)k \cdot r^{t-3} \log r $$

for every integer $r$ with $r \ge 2$.
Items (a) and (b) hold by 4.(a) and 4.(b) respectively. It suffices to prove (c).

For each $x \in V(T)$, let $\sigma_x$ be an ordering of $P_x$ witnessing 4.(d) and let $\sigma' = (x_1, \dots, x_{|V(T)|})$ be an elimination ordering of $T$. Finally, let $\sigma$ be the concatenation of $\sigma_{x_1}, \dots, \sigma_{x_{|V(T)|}}$ in this order.

Let $u \in V(G)$. To conclude the claim, we argue that

$$|\text{WReach}_r[G, S, \sigma, u]| \le \bar{c}_2(t, Y)k \cdot r^{t-1} \log r.$$

Let $x_u \in V(T)$ be such that if $u \in S$, then $u \in P_{x_u}$, and otherwise, $x_u$ is the vertex of $T$ furthest to $s$ such that $P_{x_u}$ intersects $N_G(V(C))$, where $C$ is the component of $u$ in $G-S$. Let $A$ be the set of all the ancestors of $x_u$ in $T$ in distance at most $r$ from $x_u$. In particular, $|A| \le r+1$. By Observation 19 and 4.(c),

$$\text{WReach}_r[G, S, \sigma, u] \subseteq \bigcup_{y \in A} P_y.$$

Let $y \in A$. Since $\sigma$ extends $\sigma_y$ and $x \in T_y$, by 4.(d), we have

$$|\text{WReach}_r[G, S, \sigma, u] \cap P_y| \le \text{wcol}_r \left( G \left[ \bigcup_{z \in V(T_y)} P_z \right], P_y \right) \le \bar{c}_1(t, X)k \cdot r^{t-2} \log r.$$

Summarizing,

$$\begin{align*}
|\text{WReach}_r[G, S, \sigma, u]| &= \sum_{y \in A} |\text{WReach}_r[G, S, \sigma, u] \cap P_y| \\
&\le (r+1) \cdot \bar{c}_1(t, X)k \cdot r^{t-2} \log r \\
&\le 2r \cdot \bar{c}_1(t, X)k \cdot r^{t-2} \log r = \bar{c}_2(t, Y)k \cdot r^{t-1} \log r.
\end{align*}$$

This concludes the proof of (c), and the claim follows. $\diamond$

**Claim 6.** Let $Y$ be a graph with $\text{rtd}_2(Y) \le t-1$ and let $h, d$ be positive integers. There exists an integer $\bar{c}_3(Y, h, d)$ such that for every positive integer $k$, for every graph $G$ with $\text{tw}(G) < k$, for every family $\mathcal{F}$ of nonnull connected subgraphs of $G$, if $G$ has no $\mathcal{F}$-rich model of $T'_{h,d}(Y)$, then there exists $S \subseteq V(G)$ such that

(a) $V(F) \cap S \ne \emptyset$ for every $F \in \mathcal{F}$;

(b) for every component $C$ of $G-S$, $N_G(V(C))$ intersects at most $4h$ components of $G-V(C)$;

(c) $\text{wcol}_r(G, S) \le \bar{c}_3(Y, h, d)k \cdot r^{t-2} \log r$ for every integer $r$ with $r \ge 2$.

*Proof of the claim.* We proceed by induction on $h$. When $h=1$, $T'_{h,d}(Y) = K_1 \oplus (Y \sqcup Y)$ and the result follows from the previous claim applied to $Y \sqcup Y$ (note that $\text{rtd}_2(Y \sqcup Y) = \text{rtd}_2(Y) \le t-1$) by setting $\bar{c}_3(Y, 1, d) = \bar{c}_2(t, Y \sqcup Y)$.

Now assume that $h > 1$ and that the result holds for $h-1$. Fix a copy of $Y \sqcup Y$. For each $y \in V(Y \sqcup Y)$ add $d$ vertices with $y$ as a unique neighbor. Furthermore, add $2d$ isolated vertices. We call the obtained graph $Z$ – see Figure 15. To keep things in order, we write $V(Z) = V_Y \cup V_Z$, where $V_Y$ are the vertices of $Y \sqcup Y$ in $Z$ and $V_Z$ are all the added vertices. Let

$$\bar{c}_3(Y, h, d) = \bar{c}_2(t, Z) + \bar{c}_3(Z, h-1, d).$$
By (r8) and (r4), $\mathrm{rtd}_2(Z) \le \max\{2, \mathrm{rtd}_2(Y)\} \le t-1$ since $t \ge 3$.

Let $\mathcal{F}'$ be the family of all the connected subgraphs $H$ of $G$ such that $H$ has an $\mathcal{F}|_H$-rich model of $T'_{h-1,d}(Y)$. We claim that there is no $\mathcal{F}'$-rich model of $K_1 \oplus Z$ in $G$. Suppose to the contrary that such a model $(A_y \mid y \in V(K_1 \oplus Z))$ exists. Let $s$ be the vertex of $K_1$ in $K_1 \oplus Z$. In particular, $V(K_1 \oplus Z) = \{s\} \cup V_Y \cup V_Z$. For every vertex $z \in V_Z$, we define its parent in $K_1 \oplus Z$ in the following way. Note that $z$ has at most one neighbor in $Z$. If $z$ has a neighbor in $Z$, then the neighbor is its parent and if $z$ is isolated in $Z$, then $s$ is its parent. Let $z \in V_Z$ with the parent $p_z$ and let $u_z \in A_z$ be such that there is an edge between $u_z$ and a vertex in $A_{p_z}$. Since the model is $\mathcal{F}'$-rich, $G[A_z]$ contains an $\mathcal{F}|_{G[A_z]}$-rich model of $T'_{h-1,d}(Y)$. Let $H_z$ be a copy of $T_{h-1,d}(Y)$ with a root $s_z$. By Lemma 29 applied to $Y$, $G[A_z]$, and $u$, there is an $\mathcal{F}|_{G[A_z]}$-rich model $(B_{z,x} \mid x \in V(H_z))$ of $H_z$ in $G[A_z]$ such that $u_z \in B_{z,s_z}$. In particular, there is an edge between $B_{z,s_z}$ and $A_{p_z}$ in $G$. Finally, we construct an $\mathcal{F}$-rich model of $T'_{h,d}(Y)$ in $G$. Observe that the graph obtained from $(K_1 \oplus Z)[\{s\} \cup V_Y]$ (this graph is isomorphic to $K_1 \oplus (Y \sqcup Y)$) and the disjoint union of $H_z$ for each $z \in V_Z$ by identifying $s_z \in V(H_z)$ with $p_z \in \{s\} \cup V_Y$ for each $z \in V_Z$ is isomorphic to $T'_{h,d}(Y)$. For each $p \in \{s\} \cup V_Y$, let $P_y$ be the set of all $z \in V_Z$ such that $p$ is the parent of $z$. Let

(i) $D_p = A_p \cup \bigcup_{z \in P_p} B_{z,s_z}$ for every $p \in \{s\} \cup V_Y$ and

(ii) $D_x = B_{z,x}$ for every $z \in V_Z$ and $x \in V(H_z - \{s_z\})$.

It follows that $(D_x \mid x \in \{s\} \cup V_Y \cup \bigcup_{z \in V_Z} V(H_z - \{s_z\}))$ is an $\mathcal{F}$-rich model of $T'_{h,d}(Y)$ in $G$. This is a contradiction, hence, $G$ has no $\mathcal{F}'$-rich model of $K_1 \oplus Z$.

By Claim 5, applied to $Z$, $G$, and $\mathcal{F}'$ there exists $S_0 \subseteq V(G)$ such that

5.(a) $V(F) \cap S_0 \ne \emptyset$ for every $F \in \mathcal{F}'$;

5.(b) for every component $C$ of $G - S_0$, $N_G(V(C))$ intersects at four components of $G - V(C)$;

5.(c) $\mathrm{wcol}_r(G, S_0) \le \bar{c}_2(t, 1, Z)k \cdot r^{t-2} \log r$ for every integer $r$ with $r \ge 2$.

Let $C$ be a component of $G - S_0$. Since $V(F) \cap S_0 \ne \emptyset$ for every $F \in \mathcal{F}'$, $C$ has no $\mathcal{F}|_C$-rich model of $T'_{h-1,d}(Y)$. Therefore, by induction hypothesis, there exists $S_C \subseteq V(C)$ such that

(a') $V(F) \cap S_C \ne \emptyset$ for every $F \in \mathcal{F}|_C$;

(b') for every component $C'$ of $C - S$, $N_C(V(C'))$ intersects at most $4(h-1)$ components of $C - V(C')$;

(c') $\mathrm{wcol}_r(C, S_C) \le \bar{c}_3(Y, h-1, d)k \cdot r^{t-2} \log r$ for every integer $r$ with $r \ge 2$.

Let $C$ be the family of all the components of $G - S_0$ and let

$$S = S_0 \cup \bigcup_{C \in C} S_C.$$

We claim that (a)-(c) hold. Let $F \in \mathcal{F}$. If $V(F) \cap S_0 = \emptyset$, then $V(F) \subseteq V(C)$ for some component $C$ of $G - S_0$. In particular, $F \in \mathcal{F}|_C$, and thus, by (a'), $V(F) \cap S_C \ne \emptyset$, which proves (a). Let $C$ be a component of $G - S$, and let $C'$ be the component of $G - S_0$ intersecting $V(C)$. By (b'), $N_C(V(C'))$ intersects at most $4(h-1)$ components of $C - V(C')$, and by 2.(b), $N_G(V(C')$ intersects at most four components of $G - V(C')$. Hence, $N_G(V(C))$ intersects at most $4h$ components of $G - V(C)$, which yields (b). The following sequence of inequalities
concludes the proof of (c) and the claim:

$$
\begin{align*}
\mathrm{wcol}_r(G, S) &\le \mathrm{wcol}_r(G, S_0) + \mathrm{wcol}_r\left(G - S_0, \bigcup_{C \in \mathcal{C}} S_C\right) &\text{by Observation 12} \\
&\le \mathrm{wcol}_r(G, S_0) + \max_{C \in \mathcal{C}} \mathrm{wcol}_r(C, S_C) &\text{by Observation 11} \\
&\le \bar{c}_2(t, Z)k \cdot r^{t-2} \log r + \bar{c}_3(Y, h-1, d)k \cdot r^{t-2} \log r &\text{by 5.(c) and (c')} \\
&\le (\bar{c}_2(t, Z) + \bar{c}_3(Y, h-1, d))k \cdot r^{t-1} \log r \\
&= \bar{c}_3(Y, h, d)k \cdot r^{t-1} \log r.
\end{align*}
$$

◇

Finally, by Lemma 28, for every graph $X$ with $\mathrm{rtd}_2(X) \le t$, there exists a graph $Y$ with $\mathrm{rtd}_2(Y) \le t-1$ and positive integers $h, d$ such that $X \subseteq T_{h,d}(Y) \subseteq T'_{h,d}(Y)$. Let $G$ be a graph with $\mathrm{tw}(G) < k$ and let $\mathcal{F}$ be a family of nonnull connected subgraphs of $G$. Suppose that $G$ has no $\mathcal{F}$-rich model of $X$. By Claim 6, there exists $S_0 \subseteq V(G)$ such that

6.(a) $V(F) \cap S_0 \neq \emptyset$ for every $F \in \mathcal{F}$;

6.(b) for every component $C$ of $G - S_0$, $N_G(V(C))$ intersects at most $4h$ components of $G - V(C)$;

6.(c) $\mathrm{wcol}_r(G, S) \le \bar{c}_3(Y, h, d)k \cdot r^{t-2} \log r$ for every integer $r$ with $r \ge 2$.

Let $\mathcal{C}$ be the family of components of $G - S_0$. Consider a component $C \in \mathcal{C}$. By 6.(b), $N_G(V(C))$ intersects at most $4h$ components of $G - V(C)$. Let $\mathcal{Q}_C$ be a collection of at most $4h-1$ geodesics in $C$ such that for every component $C'$ of $G - V(C)$ with $N_G(V(C)) \cap V(C') \neq \emptyset$, there is $Q \in \mathcal{Q}_C$ with $V(Q) \cap N_G(V(C')) \neq \emptyset$.

Let

$$
S = S_0 \cup \bigcup_{C \in \mathcal{C}} \bigcup_{Q \in \mathcal{Q}_C} V(Q).
$$

Item (A) follows from 6.(a). Let $C'$ be a component of $G-S$, and let $C$ be the component of $G-S_0$ intersecting $V(C')$. Then $N_G(V(C')) \subseteq N_G(V(C)) \cup \bigcup_{Q \in \mathcal{Q}_C} V(Q)$, and since $\bigcup_{Q \in \mathcal{Q}_C} V(Q)$ induces a connected subgraph of $C$ and contains a neighbor of every component of $G-V(C)$ having a neighbor in $V(C)$, we deduce that $N_G(V(C'))$ intersects at most one component of $G-S$. This proves that (B) holds. And finally, (C) is true once we set $\bar{c}(t, X) = \bar{c}_3(Y, h, d) + (4h-1) \cdot 3$ since

$$
\begin{align*}
\mathrm{wcol}_r(G, S) &\le \mathrm{wcol}_r(G, S_0) + \mathrm{wcol}_r\left(G - S_0, \bigcup_{C \in \mathcal{C}} \bigcup_{Q \in \mathcal{Q}_C} V(Q)\right) &\text{by Observation 12} \\
&\le \mathrm{wcol}_r(G, S_0) + \max_{C \in \mathcal{C}} \mathrm{wcol}_r\left(C, \bigcup_{Q \in \mathcal{Q}_C} V(Q)\right) &\text{by Observation 11} \\
&\le \mathrm{wcol}_r(G, S_0) + \max_{C \in \mathcal{C}} |\mathcal{Q}_C|(2r+1) &\text{by Observation 13} \\
&\le \bar{c}_3(Y, h, d)k \cdot r^{t-2} \log r + (4h-1)(2r+1) &\text{by 6.(c)} \\
&\le (\bar{c}_3(Y, h, d) + (4h-1) \cdot 3) k \cdot r^{t-2} \log r. &\square
\end{align*}
$$
REFERENCES

[1] Guantao T. Chen and Richard H. Schelp. Graphs with linearly bounded Ramsey numbers. *Journal of Combinatorial Theory, Series B*, 57(1):138-149, 1993.

[2] Vida Dujmovic, Robert Hickingbotham, Jędrzej Hodor, Gwenaël Joret, Hoang La, Piotr Micek, Pat Morin, Clément Rambaud, and David R. Wood. The grid-minor theorem revisited. In *David P. Woodruff, editor, Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA 2024, Alexandria, VA, USA, January 7-10, 2024*, pages 1241–1245. SIAM, 2024. arXiv:2307.02816.

[3] Vida Dujmović, Robert Hickingbotham, Gwenaël Joret, Piotr Micek, Pat Morin, and David R. Wood. The excluded tree minor theorem revisited. *Combinatorics, Probability and Computing*, 33(1):85-90, 2023. arXiv:2303.14970.

[4] Zdeněk Dvořák. Constant-factor approximation of the domination number in sparse graphs. *European Journal of Combinatorics*, 34(5):833–840, 2013. arXiv:1110.5190.

[5] Kord Eickmeyer, Archontia C. Giannopoulou, Stephan Kreutzer, O-joung Kwon, Michal Pilipczuk, Roman Rabinovich, and Sebastian Siebertz. Neighborhood Complexity and Kernelization for Nowhere Dense Classes of Graphs. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, *44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)*, volume 80 of *Leibniz International Proceedings in Informatics (LIPICS)*, pages 63:1–63:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. arXiv:1612.08197.

[6] Pierre Fraigniaud and Nicolas Nisse. Connected treewidth and connected graph searching. In José R. Correa, Alejandro Hevia, and Marcos A. Kiwi, editors, *Proc. 7th Latin American Symposium on Theoretical Informatics, LATIN 2006*, volume 3887 of *Lecture Notes in Comput. Sci.*, pages 479–490. Springer, 2006.

[7] Carla Groenland, Gwenaël Joret, Wojciech Nadara, and Bartosz Walczak. Approximating pathwidth for graphs of small treewidth. *ACM Transactions on Algorithms*, 19(2), 2023. arXiv:2008.00779.

[8] Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos. Coloring and covering nowhere dense graphs. *SIAM Journal on Discrete Mathematics*, 32(4):2467–2481, 2018. arXiv:1602.05926.

[9] Martin Grohe, Stephan Kreutzer, and Sebastian Siebertz. Deciding first-order properties of nowhere dense graphs. *Journal of the ACM*, 64(3), 2017. arXiv:1311.3899.

[10] Jan van den Heuvel and David R. Wood. Improper colourings inspired by Hadwiger's conjecture. *Journal of the London Mathematical Society*, 98(1):129-148, 2018. arXiv:1704.06536.

[11] Jan van den Heuvel, Patrice Ossona de Mendez, Daniel Quiroz, Roman Rabinovich, and Sebastian Siebertz. On the generalised colouring numbers of graphs that exclude a fixed minor. *European Journal of Combinatorics*, 66:129-144, 2017. arXiv:1602.09052.

[12] Tony Huynh, Gwenaël Joret, Piotr Micek, Michal T. Seweryn, and Paul Wollan. Excluding a ladder. *Combinatorica*, 42(3):405-432, 2022. arXiv:2002.00496.

[13] Gwenaël Joret and Piotr Micek. Improved bounds for weak coloring numbers. *The Electronic Journal of Combinatorics*, 29(1), 2022. arXiv:2102.10061.

[14] Hal A. Kierstead and Daqing Yang. Orderings on graphs and game coloring number. *Order*, 20(3):255-264, 2003.

[15] Jaroslav Nešetřil and Patrice Ossona de Mendez. *Sparsity — Graphs, Structures, and Algorithms*, volume 28 of *Algorithms and Combinatorics*. Springer, 2012.

[16] Marcin Pilipczuk, Michał Pilipczuk, and Sebastian Siebertz. Lecture notes for the course "Sparsity" given at Faculty of Mathematics, Informatics, and Mechanics of the University of Warsaw, Winter semesters 2017/18 and 2019/20. https://www.mimuw.edu.pl/~mp248287/sparsity2.

[17] Michal Pilipczuk and Sebastian Siebertz. Polynomial bounds for centered colorings on proper minor-closed graph classes. *Journal of Combinatorial Theory, Series B*, 151:111-147, 2021. arXiv:1807.03683.

[18] Felix Reidl and Blair D. Sullivan. A color-avoiding approach to subgraph counting in bounded expansion classes. *Algorithmica*, 85(8):2318-2347, 2023. arXiv:2001.05236.

[19] Neil Robertson and Paul Seymour. Graph minors. I. Excluding a forest. *Journal of Combinatorial Theory, Series B*, 35(1):39-61, 1983.

[20] Neil Robertson and Paul Seymour. Graph minors. V. Excluding a planar graph. *Journal of Combinatorial Theory, Series B*, 41(1):92-114, 1986.

[21] Xuding Zhu. Colouring graphs with bounded generalized colouring number. *Discrete Mathematics*, 309(18):5562-5568, 2009.