2. Treedepth

Say $G$ is a subgraph of the closure of some rooted tree $T$ . For each vertex $v\in V(T)$ , let $T_v$ be the maximal subtree of $T$ rooted at $v$ (consisting of $v$ and all its descendants), and let $G[T_v]$ be the subgraph of $G$ induced by $V(T_v)$ .

The weak closure of a rooted tree $T$ is the graph $G$ with vertex set $V(T)$ , where two vertices $v,w\in V(T)$ are adjacent in $G$ whenever $v$ is a leaf of $T$ and $w$ is an ancestor of $v$ in $T$ . As illustrated in Figure 2, let $W\langle{h,k}\rangle$ be the weak closure of the complete $k$ -ary tree of height $h$ .

Figure 2. The weak closure $W\langle{4,2}\rangle$ .

Note that $W\langle{h,k}\rangle$ is a proper subgraph of $C\langle{h,k}\rangle$ for $h\geqslant 3$ . On the other hand, Norin et al. [Reference Norin, Scott, Seymour and Wood19] showed that $W\langle{h,k}\rangle$ contains $C\langle{h,k-1}\rangle$ as a minor for all $h,k\geqslant 2$ . Therefore, Theorem 1 is an immediate consequence of the following lemma.

Proof. Throughout this proof, $d$ , $k$ and $h$ are fixed, and we make no attempt to optimise $c$ .

We may assume that $G$ is connected. So $G$ is a subgraph of the closure of some rooted tree of depth at most $d$ . Choose a tree $T$ of depth at most $d$ rooted at some vertex $r$ , such that $G$ is a subgraph of the closure of $T$ , and subject to this, $\sum _{v\in V(T)} \text{dist}_T(v,r)$ is minimal. Suppose that $G[T_v]$ is disconnected for some vertex $v$ in $T$ . Choose such a vertex $v$ at maximum distance from r. Since $G$ is connected, $v\neq r$ . By the choice of $v$ , for each child $w$ of $v$ , the subgraph $G[T_w]$ is connected. Thus, for some child $w$ of $v$ , there is no edge in $G$ joining $v$ and $G[T_w]$ . Let $u$ be the parent of $v$ . Let $T'$ be obtained from $T$ by deleting the edge $vw$ and adding the edge $uw$ , so that $w$ is a child of $u$ in $T'$ . Note that $G$ is a subgraph of the closure of $T'$ (since $v$ has no neighbour in $G[T_w]$ ). Moreover, $\text{dist}_{T'}(x,r) = \text{dist}_T(x,r)-1$ for every vertex $x\in V(T_w)$ , and $\text{dist}_{T'}(y,r) = \text{dist}_T(y,r)$ for every vertex $y\in V(T)\setminus V(T_w)$ . Hence, $\sum _{v\in V(T')} \text{dist}_{T'}(v,r)\lt \sum _{v\in V(T)} \text{dist}_T(v,r)$ , which contradicts our choice of $T$ . Therefore, $G[T_v]$ is connected for every vertex $v$ of $T$ .

Consider each vertex $v\in V(T)$ . Define the level $\ell (v)\;:\!=\; \text{dist}_T(r,v) \in [0,d-1]$ . Let $T^+_v$ be the subtree of $T$ consisting of $T_v$ plus the $vr$ -path in $T$ , and let $G[T^+_v]$ be the subgraph of $G$ induced by $V(T^+_v)$ . For a subtree $X$ of $T$ rooted at vertex $v$ , define the level $\ell (X)\;:\!=\;\ell (v)$ .

A ranked graph (for fixed $d$ ) is a triple $(H,L,\preceq )$ where:

• $H$ is a graph,

• $L\;:\;V(H)\rightarrow [0,d-1]$ is a function,

• $\preceq$ is a partial order on $V(H)$ such that $L(v) \lt L(w)$ whenever $v \prec w$ .

Here and throughout this proof, $v\prec w$ means that $v\preceq w$ and $v\neq w$ . Up to isomorphism, the number of ranked graphs on $n$ vertices is at most $2^{\binom{n}{2}}\,d^n\, 3^{\binom{n}{2}}$ . For a vertex $v$ of $T$ , a ranked graph $(H,L,\preceq )$ is said to be contained in $G[T^+_v]$ if there is an isomorphism $\phi$ from $H$ to some subgraph of $G[T^+_v]$ such that:

1. (A) for each vertex $v\in V(H)$ we have $L(v)=\ell (\phi (v))$ , and

2. (B) for all distinct vertices $v,w\in V(H)$ we have that $v\prec w$ if and only if $\phi (v)$ is an ancestor of $\phi (w)$ in $T$ .

Say $(H,L,\preceq )$ is a ranked graph and $i\in [0,d-1]$ . Below we define the $i$ -splice of $(H,L,\preceq )$ to be a particular ranked graph $(H',L',\preceq{\kern-2pt}')$ , which (intuitively speaking) is obtained from $(H,L,\preceq )$ by copying $k$ times the subgraph of $H$ induced by the vertices $v$ with $L(v)\gt i$ . Formally, let

\begin{align*} V(H') \;:\!=\; & \{ (v,0) \;:\; v \in V(H), L(v) \in [0,i] \} \;\cup \\ & \{ (v,j) \;:\; v \in V(H), L(v) \in [i+1,d], j \in [1,k] \}.\\ E(H') \;:\!=\; & \{ (v,0)(w,0) \;:\; vw \in E(H), L(v) \in [0,i], L(w) \in [0,i] \} \;\cup \\ & \{ (v,0)(w,j) \;:\; vw \in E(H), L(v) \in [0,i], L(w) \in [i+1,d], j \in [1,k] \} \; \cup \\ & \{ (v,j)(w,j) \;:\; vw \in E(H), L(v)\in [i+1,d], L(w) \in [i+1,d], j \in [1,k] \}. \end{align*}

Define $L'((v,j)) \;:\!=\; L(v)$ for every vertex $(v,j)\in V(H')$ . Now define the following partial order $\preceq{\kern-2pt}'$ on $V(H')$ :

• $(v,j)\preceq{\kern-2pt}' (v,j)$ for all $(v,j)\in V(H')$ ;

• if $v \prec w$ and $L(v),L(w) \in [0,i]$ , then $(v,0) \prec ' (w,0)$ ;

• if $v \prec w$ and $L(v)\in [0,i]$ and $L(w) \in [i+1,d]$ , then $(v,0) \prec ' (w,j)$ for all $j\in [1,k]$ ; and

• if $v \prec w$ and $L(v),L(w) \in [i+1,d]$ , then $(v,j) \prec ' (w,j)$ for all $j\in [1,k]$ .

Note that if $(v,a)\prec ' (w,b)$ , then $a\leqslant b$ and $v\prec w$ (implying $(L(v)\lt L(w)$ ). It follows that $\prec '$ is a partial order on $V(H')$ such that $L'((v,a)) \lt L'((w,b))$ whenever $(v,a) \prec ' (w,b)$ . Thus, $(H',L',\preceq{\kern-2pt}')$ is a ranked graph.

For $\ell \in [0,d-1]$ , let

\begin{equation*} N_\ell \;:\!=\; (d+1)(h-1)(k+1)^{d-1-\ell }. \end{equation*}

For each vertex $v$ of $T$ , define the profile of $v$ to be the set of all ranked graphs $(H,L,\preceq )$ contained in $G[T_v^+]$ such that $|V(H)| \leqslant N_{\ell (v)}$ . Note that if $v$ is a descendant of $u$ , then the profile of $v$ is a subset of the profile of $u$ . For $\ell \in [0,d-1]$ , if $N=N_\ell$ then let

\begin{equation*} M_\ell \;:\!=\; 2^{ 2^{\binom {N}{2}}\,d^N\, 3^{\binom {N}{2}} }. \end{equation*}

Then there are at most $M_\ell$ possible profiles of a vertex at level $\ell$ .

We now partition $V(T)$ into subtrees. Each subtree is called a group. (At the end of the proof, vertices in a single group will be assigned the same colour.) We assign vertices to groups in non-increasing order of their distance from the root. Initialise this process by placing each leaf $v$ of $T$ into a singleton group. We now show how to determine the group of a non-leaf vertex. Let $v$ be a vertex not assigned to a group at maximum distance from $r$ . So each child of $v$ is assigned to a group. Let $Y_v$ be the set of children $y$ of $v$ , such that the number of children of $v$ that have the same profile as $y$ is in the range $[1,k-1]$ . If $Y_v =\emptyset$ start a new singleton group $\{v\}$ . If $Y_v\neq \emptyset$ then merge all the groups rooted at vertices in $Y_v$ into one group including $v$ . This defines our partition of $V(T)$ into groups. Each group $X$ is rooted at the vertex in $X$ closest to $r$ in $T$ . A group $Y$ is above a distinct group $X$ if the root of $Y$ is on the path in $T$ from the root of $X$ to $r$ .

The next claim is the key to the remainder of the proof.

Proof. Since $(H,L,\preceq )$ is in the profile of $v$ , there is an isomorphism $\phi$ from $H$ to some subgraph of $G[T^+_v]$ such that for each vertex $x\in V(H)$ we have $L(x)=\ell (\phi (x))$ , and for all distinct vertices $x,y\in V(H)$ we have that $x\prec y$ if and only if $\phi (x)$ is an ancestor of $\phi (y)$ in $T$ .

Since $u$ and $v$ are in different groups, there are $k$ children $y_1,\ldots,y_k$ of $u$ (one of which is $v$ ) such that the profiles of $y_1,\ldots,y_k$ are equal. Thus, $(H,L,\preceq )$ is in the profile of each of $y_1,\ldots,y_k$ . That is, for each $j\in [1,k]$ , there is an isomorphism $\phi _j$ from $H$ to some subgraph of $G[T^+_{y_j}]$ such that for each vertex $x\in V(H)$ we have $L(x)=\ell (\phi _j(x))$ , and for all distinct vertices $x,y\in V(H)$ we have that $x\prec y$ if and only if $\phi _j(x)$ is an ancestor of $\phi _j(y)$ in $T$ .

Let $(H',L',\preceq{\kern-2pt}')$ be the $\ell (u)$ -splice of $(H,L,\preceq )$ . We now define a function $\phi '$ from $V(H')$ to $V( G[ T^+_u] )$ . For each vertex $(x,0)$ of $H'$ (thus with $x\in V(H)$ and $L(x)\in [0,\ell (u)]$ ), define $\phi '((x,0)) \;:\!=\; \phi (x)$ . For every other vertex $(x,j)$ of $H'$ (thus with $x\in V(H)$ and $L(x)\in [\ell (u)+1,d-1]$ and $j\in [1,k]$ ), define $\phi '((x,j)) \;:\!=\; \phi _j(x)$ .

We now show that $\phi '$ is an isomorphism from $H'$ to a subgraph of $G[T^+_u]$ . Consider an edge $(x,a)(y,b)$ of $H'$ . Thus, $xy\in E(H)$ . It suffices to show that $\phi '((x,a))\phi '((y,b))\in E(G[T^+_u])$ . First suppose that $a=b=0$ . So $L(x)\in [0,\ell (u)]$ and $L(y)\in [0,\ell (u)]$ . Thus $\phi '((x,a))=\phi (x)$ and $\phi '((y,b))=\phi (y)$ . Since $\phi$ is an isomorphism to a subgraph of $G[ T^+_v]$ , we have $\phi (x)\phi (y) \in E(G[ T^+_v] )$ , which is a subgraph of $G[ T^+_u]$ . Hence, $\phi '((x,a))\phi '((y,b)) \in E(G[ T^+_u] )$ , as desired. Now suppose that $a=0$ and $b\in [1,k]$ . Thus, $\phi '((x,a))=\phi (x)$ and $\phi '((y,b))=\phi _b(y)$ . Moreover, both $\ell (\phi (x))$ and $\ell (\phi _b(x))$ equal $L(x)\in [0,\ell (u)]$ . There is only vertex $z$ in $T^+_v$ with $\ell (z)$ equal to a specific number in $[0,\ell (u)]$ . Thus, $\phi '((x,a))=\phi (x)=\phi _b(x)$ ( $=z$ ). Since $\phi _b$ is an isomorphism to a subgraph of $G[ T^+_{y_b}]$ , we have $\phi _b(x)\phi _b(y) \in E(G[ T^+_{y_b}] )$ , which is a subgraph of $G[ T^+_u]$ . Hence, $\phi '((x,a))\phi '((y,b)) \in E(G[ T^+_u] )$ , as desired. Finally, suppose that $a=b\in [1,k]$ . Thus, $\phi '((x,a))=\phi _a(x)$ and $\phi '((y,b))=\phi _b(y)=\phi _a(y)$ . Since $\phi _a$ is an isomorphism to a subgraph of $G[ T^+_{y_a}]$ , we have $\phi _a(x)\phi _a(y) \in E(G[ T^+_{y_a}] )$ , which is a subgraph of $G[ T^+_u]$ . Hence, $\phi '((x,a))\phi '((y,b)) \in E(G[ T^+_u] )$ , as desired. This shows that $\phi '$ is an isomorphism from $H'$ to a subgraph of $G[T^+_u]$ .

We now verify property (A) for $(H',L',\preceq{\kern-2pt}')$ . For each vertex $(x,0)$ of $H'$ (thus with $x\in V(H)$ and $L(x)\in [0,\ell (u)]$ ) we have $L'((x,0))=L(x)= \ell (\phi (x)) = \ell (\phi '((x,0)))$ , as desired. For every other vertex $(x,j)$ of $H'$ (thus with $x\in V(H)$ and $L(x)\in [\ell (u)+1,d-1]$ and $j\in [1,k]$ ) we have $L'((x,j))=L(x)= \ell (\phi _j(x)) = \ell (\phi '((x,j)))$ , as desired. Hence, property (A) is satisfied for $(H',L',\preceq{\kern-2pt}')$ .

We now verify property (B) for $(H',L',\preceq{\kern-2pt}')$ . Consider distinct vertices $(x,a),(y,b)\in V(H')$ . First suppose that $a=0$ and $b=0$ . Then $(x,a) \prec ' (y,b)$ if and only if $x \prec y$ if and only if $\phi (x)$ is an ancestor of $\phi (y)$ in $T$ if and only if $\phi '((x,a))$ is an ancestor of $\phi '((y,b))$ in $T$ , as desired. Now suppose that $a=0$ and $b\in [1,k]$ . Then $(x,a) \prec ' (y,b)$ if and only if $x \prec y$ if and only if $\phi (x)$ is an ancestor of $\phi _b(y)$ in $T$ if and only if $\phi '((x,a))$ is an ancestor of $\phi '((y,b))$ in $T$ , as desired. Now suppose that $a=b\in [1,k]$ . Then $(x,a) \prec ' (y,b)$ if and only if $x \prec y$ if and only if $\phi _a(x)$ is an ancestor of $\phi _b(y)$ in $T$ if and only if $\phi '((x,a))$ is an ancestor of $\phi '((y,b))$ in $T$ , as desired. Finally, suppose that $a,b\in [1,k]$ and $a\neq b$ . Then $(x,a)$ and $(y,b)$ are incomparable under $\prec '$ , and $\phi '((x,a))$ and $\phi '((y,b))$ in $T$ are unrelated in $T$ , as desired. Hence, property (B) is satisfied for $(H',L',\preceq{\kern-2pt}')$ .

So $\phi '$ is an isomorphism from $H'$ to a subgraph of $G[T^+_u]$ satisfying properties (A) and (B). Thus $(H',L',\preceq{\kern-2pt}')$ is contained in $G[T^+_u]$ , as desired. Since $(H,L,\preceq )$ is in the profile of $v$ , we have $|V(H)| \leqslant (d+1)(h-1)(k+1)^{h-\ell (v)}$ . Since $|V(H')|\leqslant (k+1) |V(H)|$ and $\ell (u)=\ell (v)-1$ , we have $|V(H')| \leqslant (d+1)(h-1)(k+1)^{h+1-\ell (v)} = (d+1)(h-1)(k+1)^{h-\ell (u)}$ . Thus, $(H',L',\preceq{\kern-2pt}')$ is in the profile of $u$ .

The proof now divides into two cases. If some group $X_0$ is adjacent in $G$ to at least $h-1$ other groups above $X_0$ , then we show that $G$ contains $W\langle{h,k}\rangle$ as a minor. Otherwise, every group $X$ is adjacent in $G$ to at most $h-2$ other groups above $X$ , in which case we show that $G$ is $(h-1)$ -colourable with bounded clustering.

Finding the minor

Suppose that some group $X_0$ is adjacent in $G$ to at least $h-1$ other groups $X_1,\ldots,X_{h-1}$ above $X_0$ . We now show that $G$ contains $W\langle{h,k}\rangle$ as a minor; refer to Figure 3. For $i\in [1,h-1]$ , since $X_i$ is above $X_0$ , the root $v_i$ of $X_i$ is on the $v_0r$ -path in $T$ . Without loss of generality, $v_0,v_1,\ldots,v_{h-1}$ appear in this order on the $v_0r$ -path in $T$ . For $i\in [1,h-1]$ , let $w_i$ be a vertex in $X_i$ adjacent to some vertex $z_i$ in $X_0$ ; since $G$ is a subgraph of the closure of $T$ , $w_i$ is on the $v_0r$ -path in $T$ . For $i\in [0,h-2]$ , let $u_i$ be the parent of $v_i$ in $T$ (which exists since $v_{h-2}\neq r$ ). So $u_i$ is not in $X_i$ (but may be in $X_{i+1}$ ). Note that $v_0,u_0,w_1,v_1,u_1,\ldots,w_{h-2},v_{h-2},u_{h-2},w_{h-1},v_{h-1}$ appear in this order on the $v_0r$ -path in $T$ , where $v_0,v_1,\ldots,v_{h-1}$ are distinct (since they are in distinct groups).

Let $P_j$ be the $z_jr$ -path in $T$ for $j\in [1,h-1]$ . Let $H_0$ be the graph with $V(H_0)\;:\!=\;V( P_1\cup \ldots \cup P_{h-1} )$ and $E(H_0) \;:\!=\; \{z_jw_j\;:\;j\in [1,h-1]\}$ . Define the function $L_0\;:\;V(H_0)\to [0,d-1]$ by $L_0(x)\;:\!=\;\ell (x)$ for each $x\in V(H_0)$ . Define the partial order $\preceq _0$ on $V(H_0)$ , where $x\prec _0 y$ if and only if $x$ is ancestor of $y$ in $T$ . Thus, $(H_0,L_0,\preceq _0)$ is a ranked graph. By construction, $(H_0,L_0,\preceq _0\!)$ is contained in $G[T^+_{v_0}]$ . Since $H_0$ has less than $(d+1)(h-1)$ vertices, $H_0$ is in the profile of $v_0$ . For $i=0,1,\ldots,h-2$ , let $(H_{i+1},L_{i+1},\prec _{i+1})$ be the $\ell (u_i)$ -splice of $(H_i,L_i,\prec _i\!)$ .

By induction on $i$ , using Claim 1 at each step and since $G[T^+_{u_i}]\subseteq G[T^+_{v_{i+1}}\!]$ , we conclude that for each $i\in [0,h-1]$ , the ranked graph $(H_i,L_i,\preceq _i)$ is in the profile of $v_i$ . In particular, $(H_{h-1},L_{h-1},\prec _{h-1})$ is in the profile of $v_{h-1}$ , and $H_{h-1}$ is isomorphic to a subgraph of $G$ . Note that each vertex of $H_{h-1}$ is of the form $(((\ldots (x,d_1),d_2),\ldots ),d_{h-1})$ for some $x\in V(H_0)$ and $d_1,\ldots,d_{h-1}\in [0,k]$ . For brevity, call such a vertex $x\langle{d_1,\ldots,d_{h-1}\rangle }$ . Note that if $x=w_j$ for some $j\in [1,h-1]$ , then $d_1=\ldots =d_j=0$ (since $w_j$ is above $u_i$ whenever $i\lt j$ , and $(H_{i+1},L_{i+1},\prec _{i+1}\!)$ is the $\ell (u_i)$ -splice of $(H_i,L_i,\preceq _i\!)$ ).

Figure 3. Construction of a $W\langle{4,k}\rangle$ minor (where $u_i$ might be in $X_{i+1}$ ).

For $x\in V(H_0)$ , let $\Lambda _x$ be the set of vertices $x\langle{d_1,\ldots,d_{h-1}\rangle }$ in $H_{h-1}$ . By construction, no two vertices in $\Lambda _x$ are comparable under $\preceq _{h-1}$ . Therefore, by property (B), $V(T_a)\cap V(T_b)=\emptyset$ for all distinct $a,b\in \Lambda _x$ . In particular, $V(T_{a})\cap V(T_b)=\emptyset$ for all distinct $a,b\in \Lambda _{v_0}$ . As proved above, $G[T_a]$ is connected for each $a\in V(T)$ . Let $G'$ be the graph obtained from $G$ by contracting $G[T_a]$ into a single vertex $\alpha{\kern-1pt}\langle{d_1,\ldots,d_{h-1}\rangle }$ , for each $a=v_0\langle{d_1,\ldots,d_{h-1}\rangle } \in \Lambda _{v_0}$ . So $G'$ is a minor of $G$ .

Let $U$ be the tree with vertex set

\begin{equation*} \{\langle { d_1,\ldots,d_{h-1} \rangle }\;:\; \exists j\in [0,h-1] \;d_1=\ldots =d_j=0\text { and }d_{j+1},\ldots,d_{h-1} \in [1,k] \}, \end{equation*}

where the parent of $(0,\ldots,0,d_{j+1},d_{j+2},\ldots,d_{h-1})$ is $(0,\ldots,0,d_{j+2},\ldots,d_{h-1})$ . Then $U$ is isomorphic to the complete $k$ -tree of height $h$ rooted at $\langle 0,\ldots,0\rangle$ . We now show that the weak closure of $U$ is a subgraph of $G$ ^′, where each vertex $\langle 0,\ldots,0,d_{j+1},\ldots,d_{h-1}\rangle$ of $U$ with $j\in [1,h-1]$ is mapped to vertex $w_j\langle 0,\ldots,0,d_{j+1},\ldots,d_{h-1}\rangle$ of $G'$ , and each other vertex $\langle d_1,\ldots,d_{h-1}\rangle$ of $U$ is mapped to $\alpha \langle d_1,\ldots,d_{h-1}\rangle$ of $G'$ . For all $d_1,\ldots,d_{h-1}\in [1,k]$ and $j\in [1,h-1]$ the vertex $z_j\langle{d_1,\ldots,d_{h-1}\rangle }$ of $G$ is contracted into the vertex $\alpha \langle{d_1,\ldots,d_{h-1}\rangle }$ of $G'$ . By construction, $z_j\langle{d_1,\ldots,d_{h-1}\rangle }$ is adjacent to $w_j\langle{0,\ldots,0,d_{j+1},\ldots,d_{h-1}\rangle }$ in $G$ . So $\alpha \langle{d_1,\ldots,d_{h-1}\rangle }$ is adjacent to $w_j\langle{0,\ldots,0,d_{j+1},\ldots,d_{h-1}\rangle }$ in $G'$ . This implies that the weak closure of $U$ (that is, $W\langle{h,k}\rangle$ ) is isomorphic to a subgraph of $G$ ’, and is therefore a minor of $G$ .

Finding the colouring

Now assume that every group $X$ is adjacent in $G$ to at most $h-2$ other groups above $X$ . Then $(h-1)$ -colour the groups in order of distance from the root, such that every group $X$ is assigned a colour different from the colours assigned to the neighbouring groups above $X$ . Assign each vertex within a group the same colour as that assigned to the whole group. This defines an $(h-1)$ -colouring of $G$ .

Consider the function $s\;:\;[0,d-1]\to \mathbb{N}$ recursively defined by

\begin{equation*} s(\ell ) \;:\!=\; \begin {cases} 1 & \text { if }\ell =d-1\\ (k-1) \cdot M_{\ell +1} \cdot s(\ell +1) & \text { if } \ell \in [0,d-2]. \end {cases} \end{equation*}

Then every group at level $\ell$ has at most $s(\ell )$ vertices. By construction, our $(h-1)$ -colouring of $G$ has clustering $s(0)$ , which is bounded by a function of $d$ , $k$ and $h$ , as desired.

3. Pathwidth

The following lemma of independent interest is the key to proving Theorem 2. Note that Eppstein [Reference Eppstein24] independently discovered the same result (with a slightly weaker bound on the path length). The decomposition method in the proof has been previously used, for example, by Dujmović, Joret, Kozik, and Wood [Reference Dujmović, Joret, Kozik and Wood25, Lemma 17].

Proof. We proceed by induction on $w\geqslant 1$ . Every graph with pathwidth 1 is a caterpillar, and is thus properly 2-colourable. Now assume $w\geqslant 2$ and the result holds for graphs with pathwidth at most $w-1$ . Let $G$ be a graph with pathwidth at most $w$ . Let $(B_1,\ldots,B_n)$ be a path-decomposition of $G$ with width at most $w$ . Let $t_1,t_2,\ldots,t_m$ be a maximal sequence such that $t_1=1$ and for each $i\geqslant 2$ , $t_i$ is the minimum integer such that $B_{t_i} \cap B_{t_{i-1}}=\emptyset$ . For odd $i$ , colour every vertex in $B_{t_i}$ ‘red’. For even $i$ , colour every vertex in $B_{t_i}$ ‘blue’. Since $B_{t_i} \cap B_{t_{i-1}}=\emptyset$ for $i\geqslant 2$ , no vertex is coloured twice. Let $G'$ be the subgraph of $G$ induced by the uncoloured vertices. By the choice of $B_{t_i}$ , for $i\geqslant 2$ each bag $B_j$ with $j\in [t_{i-1}+1,t_i-1]$ intersects $B_{t_{i-1}}$ . Thus, $(B_1\cap V(G'),\ldots,B_n\cap V(G'))$ is a path-decomposition of $G'$ of width at most $w-1$ . By induction, $G'$ has a vertex 2-colouring such that each monochromatic path has at most $(w+3)^{w-1}$ vertices. Since $B_{t_i}\cup B_{t_{i+2}}$ separates $B_{t_i+1}\cup \ldots \cup B_{t_{i+2}-1}$ from the rest of $G$ , each monochromatic component of $G$ is contained in $B_{t_i+1}\cup \ldots \cup B_{t_{i+2}-1}$ for some $i\in [0,n-2]$ . Consider a monochromatic path $P$ in $G[ B_{t_i+1}\cup \ldots \cup B_{t_{i+2}-1} ]$ . Then $P$ has at most $w+1$ vertices in $B_{t_{i+1}}$ . Note that $P- B_{t_{i+1}}$ is contained in $G'$ . Thus, $P$ consists of up to $w+2$ monochromatic subpaths in $G'$ plus $w+1$ vertices in $B_{t_{i+1}}$ . Hence, $P$ has at most $(w+2) (w+3)^{w-1} + (w+1) \lt (w+3)^{w}$ vertices.

Nešetřil and Ossona de Mendez [Reference Nešetřil and Ossona de Mendez23] showed that if a graph $G$ contains no path on $k$ vertices, then $\text{td}(G)\lt k$ (since $G$ is a subgraph of the closure of a DFS spanning tree with height at most $k$ ). Thus Lemma 9 implies:

Note that Lemma 9 cannot be extended to the setting of bounded tree-width graphs: Esperet and Joret (see [[Reference Liu and Oum14], Theorem 4.1]) proved that for all positive integers $w$ and $d$ there exists a graph $G$ with tree-width at most $w$ such that for every $w$ -colouring of $G$ there exists a monochromatic component of $G$ with diameter greater than $d$ (and thus with a monochromatic path on more than $d$ vertices, and thus with treedepth at least $\log _2 d$ ).

4. Fractional colouring

This section proves Theorem 6. The starting point is the following key result of Dvořák and Sereni [Reference Dvořák and Sereni26].Footnote ²

We now prove a lower bound on the fractional defective chromatic number of the closure of complete trees of given height.

Proof. We show by induction on $h$ that if $C \langle h,k\rangle$ is fractionally $t$ -colourable with defect $d$ , then $t\geqslant h - (h-1)d/k$ . This clearly implies the lemma. The base case $h=1$ is trivial.

For the induction step, suppose that $G\;:\!=\;C \langle h,k\rangle$ is fractionally $t$ -colourable with defect $d$ . Thus, there exist $Y_1,Y_2, \ldots, Y_s \subseteq V(G)$ and $\alpha _1,\ldots,\alpha _s \in [0,1]$ such that:

• every component of $G[Y_i]$ has maximum degree at most $d$ ,

• $\sum _{i=1}^s \alpha _i \leqslant t$ , and

• $\sum _{i{\kern1pt}:v \in Y_i}\alpha _i \geqslant 1$ for every $v \in V(G)$ .

Let $r$ be the vertex of $G$ corresponding to the root of the complete $k$ -ary tree and let $H_1,\ldots,H_k$ be the components of $G - r$ . Then each $H_i$ is isomorphic to $C \langle h-1,k\rangle$ . Let $J_0 \;:\!=\; \{j \;:\; r \in Y_j \}$ , and let $J_i \;:\!=\; \{j \;:\; Y_j \cap V(H_i) \neq \emptyset \}$ for $i\in [1,k]$ . Denote $\sum _{j \in J_i} \alpha _j$ by $\alpha (J_i)$ for brevity. Thus, $\alpha (J_0) \geqslant 1$ . For $i\in [1,k]$ , the subgraph $H_i$ is $\alpha (J_i)$ -colourable with defect $d$ , and thus $\alpha (J_i) \geqslant h-1 - (h-2)d/k$ by the induction hypothesis. Thus,

\begin{equation*} (k-d)\alpha (J_0) + \sum _{i=1}^{k}\alpha (J_i) \geqslant (k-d)+k(h-1) - (h-2)d = kh-(h-1)d. \end{equation*}

If $j \in J_0$ then $Y_j$ intersects at most $d$ of $H_1,\ldots,H_k$ (since $G[Y_j]$ has maximum degree at most $d$ ). Thus, every $\alpha _j$ appears with coefficient at most $k$ in the left side of the above inequality, implying

\begin{equation*} (k-d)\alpha (J_0) + \sum _{i=1}^{k}\alpha (J_i) \leqslant k \sum _{i=1}^s \alpha _i \leqslant kt. \end{equation*}

Combining the above inequalities yields the claimed bound on $t$ .

Proof of Theorem 6.By Lemma 12,

\begin{equation*} \chi ^f_{\star }(\mathcal {G}) \geqslant \chi ^f_{\Delta }(\mathcal {G}) \geqslant \text {tcn}(\mathcal {G}) -1. \end{equation*}

It remains to show that $\chi ^f_{\star }(\mathcal{G}) \leqslant \text{tcn}(\mathcal{G}) -1$ . Equivalently, we need to show that for all $h,k \in \mathbb{N}$ and $\varepsilon \gt 0$ , if $C\langle{h,k}\rangle \not \in \mathcal{G}$ then there exists $c$ such that every graph in $\mathcal{G}$ is fractionally $(h-1+\varepsilon )$ -colourable with clustering $c$ . This is trivial for $h=1$ , and so we assume $h \geqslant 2$ .

Let $d \in \mathbb{N}$ satisfy the conclusion of Theorem 11 for the class $\mathcal{G}$ and $\delta = 1 - \frac{1}{1+\varepsilon/(h-1)}$ . Choose $c=c(d,k+1,h)$ to satisfy the conclusion of Lemma 8. We show that $c$ is as desired.

Consider $G \in \mathcal{G}$ . By the choice of $d$ there exists $s \in \mathbb{N}$ and $X_1,X_2, \ldots, X_s \subseteq V(G)$ such that:

• $\text{td}(G[X_i]) \leqslant d$ , and

• every $v \in V(G)$ belongs to at least $(1 - \delta )s$ of these sets.

Since $C\langle{h,k}\rangle \not \in \mathcal{G}$ , we have $W\langle{h,k+1}\rangle \not \in \mathcal{G}$ , and by the choice of $c$ , for each $i\in [1,s]$ there exists a partition $(Y^1_i,Y^2_i,\ldots,Y^{h-1}_i)$ of $X_i$ such that every component of $G[Y^j_i]$ has at most $c$ vertices. Every vertex of $G$ belongs to at least $(1 - \delta )s$ sets $Y^{j}_i$ where $i\in [1,s]$ and $j\in [1,h-1]$ . Considering these sets with equal coefficients $\alpha ^{j}_i \;:\!=\; \frac{1}{(1 - \delta )s}$ , we conclude that $G$ is fractionally $\frac{h-1}{1-\delta }$ -colourable with clustering $c$ , as desired (since $\frac{h-1}{1-\delta }=h-1+\varepsilon$ ).