Proof. Given \(r\) set \(t = \max( a(r, r, r), b(r) )\) where \(a\) is the function guaranteed by Proposition 2, while \(b\) is the function guaranteed by Proposition 3.

Suppose now that \(G\) contains \(K_{t,t}\) or \(W_{t\times t}\) as an induced minor. If \(G\) contains \(K_{t,t}\) as an induced minor then, by 2, \(G\) contains an induced subgraph isomorphic to \(K_{r,r}\), a subdivision of \(W_{r\times r}\) or the line graph of a subdivision of \(W_{r\times r}\), or \(G\) contains an \((r, r)\)-constellation. If \(G\) contains \(W_{t\times t}\) as an induced minor then, by 3, \(G\) contains as an induced subgraph either a subdivision of \(W_{r\times r}\), or the line graph of a subdivision of \(W_{r\times r}\). ◻

Proof. Set \(\tilde{t} := a(t,t,t)\), where \(a\) is as in 2. Suppose for contradiction that \(G\in\mathcal{C}_t\) has a Squiggly \(K_{\tilde{t},\tilde{t}}\), witnessed by \(\{A_1,\dots,A_{\tilde{t}}\}\cup\{B_1,\dots,B_{\tilde{t}}\}\). Let \(G' := \mathsf{twin}(G)\) and observe that by construction each \(G'-V(G)\) is isomorphic to \(G\). So the sets \(B_1^\star,\dots,B_{\tilde{t}}^\star\) are connected and pairwise non-touching. Furthermore, since each \(A_i\) touches each \(B_j\), we have that \(N(A_i)\cap B_j^\star\) is non-empty for every \(i,j\in[\tilde{t}]\). Consequently \(\{A_1,\dots,A_{\tilde{t}}\}\cup\{B_1^\star,\dots,B_{\tilde{t}}^\star\}\) is the induced minor model of a \(K_{\tilde{t},\tilde{t}}\) in \(G'\).

By 2, \(G'\) contains an induced subgraph \(H\) isomorphic to one of: \(K_{t,t}\), a subdivision of \(W_{t\times t}\), the line graph of a subdivision of \(W_{t\times t}\), or a \((t,t)\)-constellation. In all cases, no two vertices of \(H\) are true-twins in \(G'\), and so \(H\) is isomorphic to an induced subgraph of \(G\). But then, in all cases we conclude that \(G\) contains the induced-minor \(W_{t \times t}\)-model, or an induced \(K_{t,t}\)-model, contrary to the fact that \(G \in \mathcal{C}_t\). ◻

Proof. Let \(a:=a(t,t,t)\) be given by 2 and let \(b:=b(t)\) be given by 3. Apply Proposition 5 with parameter \(\max\{a,b\}\), and let \(p,q\) be the resulting integers. Let \(\{S_1,\dots,S_p\}\) be pairwise disjoint, anticomplete, connected sets in \(G\in\mathcal{C}_t\). Let \(G' := \mathsf{twin}(G)\) and define \(G''\) to be the graph obtained from \(G'\) by contracting each \(S_i\subseteq V(G')\) to a single vertex \(s_i\). Since the \(S_i\) are pairwise disjoint and anticomplete in \(G\), \(\hat{S} = \{s_1,\dots,s_p\}\) is an independent set of size \(p\) in \(G''\). Now, suppose for contradiction that no pair \(S_i,S_j\) is \(q\)-slim in \(G\).

By the contrapositive of 5, \(G''\) must contain a \(K_{a,a}\) or \(W_{b\times b}\) as an induced minor, witnessed by some induced subgraph \(H''\subseteq G''\). But then, the induced subgraph \(H'\) of \(G'\) obtained by replacing any \(s_i\in V(H'')\cap \hat{S}\) with \(S_i\subseteq V(G')\) witnesses a \(K_{a,a}\) or \(W_{b\times b}\) as an induced minor of \(G'\). Hence, from 2 and 3 we conclude that, \(G'\) contains an induced subgraph \(H\) isomorphic to one of: \(K_{t,t}\), a subdivision of \(W_{t\times t}\), the line graph of a subdivision of \(W_{t\times t}\), or a \((t,t)\)-constellation. In all cases, no two vertices of \(H\) are true-twins in \(G'\), and so \(H\) is isomorphic to an induced subgraph of \(G\). But then, in all cases, we obtain an induced-minor model of \(W_{t \times t}\) or \(K_{t,t}\) in \(G\), contradicting the fact that \(G\in\mathcal{C}_t\). ◻

Proof. Condition 3 holds since for every \(t \le p\), \(b\geq 1\), and every \(v \in G_{i_t}\) we have \(\vec{S}'_{\le t-1} \subseteq \vec{S}_{\le i_t - 1}\), and therefore \[L_b\!\left(N_{G_{i_t}}^{r}[v], \vec{S}'_{\le t-1}\right) \quad \subseteq\quad L_b\!\left(N_{G_{i_t}}^{r}[v], \vec{S}_{\le i_t - 1}\right).\] Hence, \[\left|L_b\left(N_{G_{i_t}}^{r}[v], \vec{S}'_{\le t-1}\right)\right| \quad \le \quad \left|L_b\left(N_{G_{i_t}}^{r}[v], \vec{S}_{\le i_t - 1}\right)\right| \quad \le \quad \frac{|G|}{2^b (2ka)}.\]

Condition 4 holds since the property is monotone under taking subgraphs, so \(G_{i_1}\) is \((ka,r)\)-clean with respect to \(G\). All remaining conditions are inherited directly from the original sequence, so \(\vec{S}', \vec{\hat{S}}', \vec{G}'\) forms a \((k,r,a)\)-cleaning sequence. ◻

Proof. First we prove the case \(i=1\). Let \(1\leq q\leq \ell\). Since \(\hat{S}_q\) is a \((k,r)\)-cover of \(S_q\) in \(G_q\), we have \[S_q\subseteq \bigcup_{x\in \hat{S}_q}N^r_{G_q}[x].\] Moreover, \(G_q\subseteq G_1\). Hence, for every \(x\in \hat{S}_q\), we have \(N^r_{G_q}[x]\subseteq N^r_{G_1}[x]\). By Condition 4, \(G_1\) is \((ka,r)\)-clean with respect to \(G\), and so

\[\abs{S_q} \quad \leq\quad \sum_{x\in \hat{S}_q}\abs{N^r_{G_q}[x]} \quad \leq\quad |\hat{S}_q|\frac{|G|}{2ka} \quad \leq\quad \frac{|G|}{2a}.\] Therefore, for every \(1\leq j\leq \ell\), \[\abs{L_1(G_j,\vec{S}_{\leq j})} \quad \leq\quad \sum_{q\leq j}\abs{S_q} \quad \leq\quad \frac{|G|}{2}\frac{j}{a}.\]

We now prove the statement for \(i\geq 2\) by induction on \(j\). The case \(j=1\) is trivial, since \(L_i(G_1,\vec{S}_{\leq 1})=\emptyset\) for every \(i\geq 2\). Let \(j\geq 1\), and suppose that the statement holds for \(j\). We prove it for \(j+1\). If \(i>j+1\), then \(L_i(G_{j+1},\vec{S}_{\leq j+1})=\emptyset\), so there is nothing to prove. Thus, we may assume that \(2\leq i\leq j+1\). We have \[\abs{L_i(G_{j+1},\vec{S}_{\leq j+1})} \quad \leq\quad \abs{L_i(G_j,\vec{S}_{\leq j})} \;+\; \abs{L_{i-1}(S_{j+1},\vec{S}_{\leq j})}.\] By the induction hypothesis, or trivially if \(i>j\), \[\abs{L_i(G_j,\vec{S}_{\leq j})} \quad \leq\quad \frac{|G|}{2^i}\frac{j}{a}.\] It remains to bound the second term. Since \(\hat{S}_{j+1}\) is a \((k,r)\)-cover of \(S_{j+1}\) in \(G_{j+1}\), \[\abs{L_{i-1}(S_{j+1},\vec{S}_{\leq j})} \quad \leq\quad \sum_{x\in \hat{S}_{j+1}} \abs{L_{i-1}(N^r_{G_{j+1}}[x],\vec{S}_{\leq j})}.\] Since \(i\geq 2\), we have \(i-1\geq 1\). Also, by Condition 3, \(G_{j+1}\) is \((2ka,r)\)-clean with respect to \(\vec{S}_{\leq j}\). Hence \[\abs{L_{i-1}(N^r_{G_{j+1}}[x],\vec{S}_{\leq j})} \quad \leq\quad \frac{|G|}{2^{i-1}}\frac{1}{2ka}.\] Therefore \[\abs{L_{i-1}(S_{j+1},\vec{S}_{\leq j})} \quad \leq\quad |\hat{S}_{j+1}|\frac{|G|}{2^{i-1}}\frac{1}{2ka} \quad \leq\quad k\frac{|G|}{2^{i-1}}\frac{1}{2ka} \quad =\quad \frac{|G|}{2^i a}.\] Combining both inequalities yields \[\abs{L_i(G_{j+1},\vec{S}_{\leq j+1})} \quad \leq\quad \frac{|G|}{2^i}\frac{j}{a} \;+\; \frac{|G|}{2^i a} \quad =\quad \frac{|G|}{2^i}\frac{j+1}{a},\] as desired. ◻

Proof. By induction on \(p\). If \(p=1\) then the statement is trivially true. Let \(\ell = pk \left\lceil \log n \right\rceil\). By 8, we have that \[\abs{L_{\left\lceil \log n \right\rceil}(G_\ell,\vec{S}_{\leq \ell})} \quad \leq\quad \frac{n}{2^{\left\lceil \log n \right\rceil}} \frac{\ell}{a} \quad <\quad 1\] so \(L_{\left\lceil \log n \right\rceil}(G_\ell,\vec{S}_{\leq \ell}) = \emptyset\). Therefore, there are fewer than \(k \left\lceil \log n \right\rceil\) of the sets in \(S\) intersecting \(\hat{S}_\ell\). Taking the subsequence not intersecting \(\hat{S}_\ell\) and applying the induction hypothesis lets us conclude. ◻

Proof. Let \(\mu = \mu'(2r+1,t)+3\) where \(\mu'\) is defined as in 10. Let \(G_0=G\), \(\hat{S}_0=\emptyset\) and \(T_0 = Z(G,G,2r+1,2ka)\). Set \(\ell=pk\left\lceil \log n \right\rceil\). For every \(0< j\leq \ell\), let \(G_{j} =G_{j-1}\setminus(T_{j-1}\cup \hat{S}_{j-1})\), \(S_j\) be a \((k,r)\)-coverable set in \(G_j\) with cover \(\hat{S}_j\) such that \(G_j\) is \(S_j\)-close to \(\mathcal{P}\). By enlarging \(S_j\) if necessary, we may assume that \(S_j=N^r_{G_j}[\hat{S}_j]\). Let \(S_j' = N_{G_j}^{2r+1}[\hat{S}_j]\). Let \[T_j = \bigcup_{i\leq j} Z\left(G_j,L_i(G_j,\vec{S}_{\leq j}'),2r+1,2ak\right).\] Finally, let \(T=\bigcup_{0\leq j\leq \ell} \left( T_j \cup \hat{S}_j \right)\). By 10, we have that \(|T| \leq a^2 (2aks)^{\mu'(2r+1,t)} + ka \leq (2aks)^{\mu}\).

If \(G\) is \(T\)-close to \(\mathcal{P}\) there is nothing to show. Therefore, we may assume that \(G\setminus T \notin \mathcal{P}\). We check that \(\vec{S}'\), \(\vec{\hat{S}}\), and \(\vec{G}\) form a \((k,2r+1,a)\)-cleaning sequence. We prove this by induction on \(\ell\). If \(\ell = 1\), we have that we have that \(G_1 = G\setminus T_0\) and so \(G_1\) is \((ka,2r+1)\)-clean with respect to \(G\), and the other conditions to be a \((k,2r+1,a)\)-cleaning sequence are clearly satisfied. We may assume that \(\vec{S}_{\leq\ell-1}'\), \(\vec{\hat{S}}_{\leq\ell-1}\) and \(\vec{G}_{\leq\ell-1}\) forms a \((k,2r+1,a)\)-cleaning sequence. Since \((k,2r+1,a)\)-cleaning sequences are closed under taking prefixes, it suffices to verify that \(G_\ell\) is \((2ka,2r+1)\)-clean with respect to \(\vec{S'}_{\leq \ell-1 }\). For every \(m\in {\mathbb{N}}\) and \(v\in G_\ell\), we have that \[\begin{align} \abs{L_m\left(N_{G_\ell}^{2r+1}[v] ,\vec{S}_{\leq \ell-1 }'\right)} \quad &\leq\quad \frac{\abs{L_m(G_{\ell-1},\vec{S}_{\leq \ell-1 }')}}{2ka}\\ &\leq\quad \frac{|G|}{2^m} \frac{\ell-1}{a} \frac{1}{2ka}\\ &\leq\quad \frac{|G|}{2^m} \frac{1}{2ka}. \end{align}\] Therefore, \(\vec{S}, \vec{S'},\vec{G}\) form a \((k,2r+1,a)\)-cleaning sequence.

We apply 9 to the cleaning sequence \(\vec{S}'\), \(\vec{\hat{S}}\), and \(\vec{G}\). Thus, there are indices \(i_1<\cdots<i_p\) such that \(\hat{S}_{i_e}\cap S'_{i_f}=\emptyset\) for every \(e\neq f\). For \(e\in[p]\), let \(R_e=S_{i_e}\). We claim that \(R_1,\dots,R_p\) satisfy the conclusion. Fix \(e<f\). Since \(\hat{S}_{i_f}\cap S'_{i_e}=\emptyset\) and \(S'_{i_e}=N^{2r+1}_{G_{i_e}}[\hat{S}_{i_e}]\), while \(\hat{S}_{i_f}\subseteq V(G_{i_f})\subseteq V(G_{i_e})\), we have \(\mathop{\mathrm{dist}}_{G_{i_e}}(\hat{S}_{i_e},\hat{S}_{i_f})>2r+1\). Since \(G_{i_f}\subseteq G_{i_e}\), if \(R_e\) and \(R_f\) were not disjoint and anticomplete, then there would be a path in \(G_{i_e}\) of length at most \(2r+1\) from \(\hat{S}_{i_e}\) to \(\hat{S}_{i_f}\), a contradiction. Thus the sets \(R_1,\dots,R_p\) are pairwise disjoint and anticomplete.

Moreover, each \(R_e\) is internally \((k,r)\)-coverable, with cover \(\hat{S}_{i_e}\subseteq R_e\), and has at most \(k\) connected components. Finally, since \(G\setminus T\subseteq G_{i_e}\) and \(G_{i_e}\setminus R_e\in\mathcal{P}\), the heredity of \(\mathcal{P}\) implies that \((G\setminus T)\setminus R_e\in\mathcal{P}\). Thus \(G\setminus T\) is \(R_e\)-close to \(\mathcal{P}\) for every \(e\in[p]\), and the sets \(R_1,\dots,R_p\) satisfy the conclusion. ◻

Proof. Let \(G\in\mathcal{C}_t\) be an \(n\)-vertex graph and let \(w\) be a weight function on \(V(G)\). If \(w(G)=0\), then the empty set is a \((w,\frac{1}{4})\)-balanced separator, so we may assume that \(w(G)>0\). Let \((T,\chi)\) be a tree decomposition of \(G\) as in 12. Applying 1 to \((T,\chi)\) and \(w\) gives a bag \(S_1\) which is a \((w,\frac{1}{2})\)-balanced separator in \(G\). In particular, every component of \(G\setminus S_1\) has weight at most \(1/2\).

Let \(C_1,\ldots,C_m\) be the components of \(G\setminus S_1\) with weight more than \(1/4\). Since these components are pairwise disjoint, we have \(m\leq 3\). For each \(i\in[m]\), define a weight function \(w_i\) on \(G[C_i]\) by \(w_i(v)=w(v)/w(C_i)\). Since \(\mathcal{C}_t\) is hereditary, \(G[C_i]\in\mathcal{C}_t\). Applying 12 to \(G[C_i]\) and 1 to \(w_i\), we obtain a set \(S_i'\subseteq C_i\) which is a \((w_i,\frac{1}{2})\)-balanced separator in \(G[C_i]\) and is \((k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,|C_i|),8)\)-coverable in \(G[C_i]\). Since \(|C_i|\leq n\), this implies that \(S_i'\) is \((k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,n),8)\)-coverable in \(G\).

Let \(S:=S_1\cup\bigcup_{i=1}^m S_i'\). Then \(S\) is \((4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,n),8)\)-coverable in \(G\), since \(S_1\) and each \(S_i'\) can be covered by at most \(k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,n)\) balls of radius \(8\), and \(m\leq 3\).

It remains to show that \(S\) is \((w,\frac{1}{4})\)-balanced. Let \(C\) be a component of \(G\setminus S\). If \(C\) is contained in a component of \(G\setminus S_1\) that is not among \(C_1,\ldots,C_m\), then \(w(C)\leq 1/4\). Otherwise, \(C\subseteq C_i\setminus S_i'\) for some \(i\in[m]\). Since \(S_i'\) is \((w_i,\frac{1}{2})\)-balanced in \(G[C_i]\), we have \(w_i(C)\leq 1/2\), and therefore \(w(C)\leq w(C_i)/2\leq 1/4\). Thus \(S\) is a \((w,\frac{1}{4})\)-balanced separator in \(G\). ◻

Proof. If \(Y=\emptyset\), then the empty set is a \((Y,\frac{1}{2})\)-balanced separator, so we may assume that \(Y\neq\emptyset\). Define a weight function \(w:V(G)\to\mathbb{R}_{\geq 0}\) by setting \(w(v)=1/|Y|\) for \(v\in Y\), and \(w(v)=0\) otherwise. Let \(\mathcal{P}\) be the hereditary property of labeled induced subgraphs \(H\subseteq G\) such that \(H\) is \((w,\frac{1}{4})\)-balanced.

We first check that every induced subgraph of \(G\) is \((K,8,\mathcal{P})\)-close. Let \(H\subseteq G\) be an induced subgraph. Since \(\mathcal{C}_t\) is hereditary, \(H\in\mathcal{C}_t\). By 1, applied to \(H\) and the restricted weight function \(w|_{V(H)}\), there exists a \((w|_{V(H)},\frac{1}{4})\)-balanced separator \(X\) in \(H\) which is \((4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,|H|),8)\)-coverable in \(H\). Since \(|H|\leq n\), the set \(X\) is \((K,8)\)-coverable in \(G\), and \(H\setminus X\in\mathcal{P}\). Thus \(H\) is \((K,8,\mathcal{P})\)-close.

Since \(\mathcal{C}_t\subseteq\mathcal{F}_t\), we may apply 11 with parameters \(k=K\), \(r=8\), \(p=\ell\), \(s=\omega+1\), and \(a = h'\). Since \(h'>\ell K\left\lceil \log n \right\rceil\), we obtain a set \(T\subseteq V(G)\) with \(|T|\leq\kappa\) such that either \(G\setminus T\in\mathcal{P}\), or there exist sets \(R_1,\dots,R_\ell\) which are pairwise disjoint and anticomplete, each have at most \(K\) connected components and are internally \((K,8)\)-coverable, and such that \((G\setminus T)\setminus R_i\in\mathcal{P}\) for every \(i\in[\ell]\).

If \(G\setminus T\in\mathcal{P}\), then \(T\) is a \((Y,\frac{1}{4})\)-balanced separator, and hence a \((Y,\frac{1}{2})\)-balanced separator. Thus we may assume that the second case holds. Set \(Y':=Y\cap V(G\setminus T)\). If \(|Y'|\leq |Y|/2\), then \(T\) is a \((Y,\frac{1}{2})\)-balanced separator, so we may assume that \(|Y'|>|Y|/2\).

For every \(i\in[\ell]\), set \(C_i:=R_i\cap T\), \(S_i:=R_i\setminus T\), and let \(D:=T\setminus\bigcup_{i\in[\ell]}C_i\). Then \(D':=D\cup\bigcup_{i\in[\ell]}C_i=T\), and \(S_i\cup C_i=R_i\) for every \(i\). As above, \((D,\{(S_i,C_i):i\in[\ell]\})\) is a \(K\)-thick clean-set-packing of length \(\ell\) and cost at most \(\kappa\).

It remains to check the separator condition. Since \((G\setminus T)\setminus R_i=(G\setminus D')\setminus S_i\in\mathcal{P}\), every component of \((G\setminus D')\setminus S_i\) contains at most \(|Y|/4\) vertices of \(Y\). Since \(|Y'|>|Y|/2\), this is at most \(|Y'|/2\). Hence \(S_i\) is a \((Y',\frac{1}{2})\)-balanced separator in \(G\setminus D'\) for every \(i\in[\ell]\). Therefore the clean-set-packing is a \((Y,\frac{1}{2})\)-packing. ◻

Proof of 2. Let \(G\in\mathcal{C}_t\) be an \(n\)-vertex graph, and let \(A,B\subseteq V(G)\) be \(q\)-slim in \(G\). Let \((T,\chi)\) be a tree decomposition of \(G\) as in 12. Thus every bag is \((k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,n),8)\)-coverable in \(G\).

For every \(A\)–\(B\) path \(P\) in \(G\), let \(T_P=\{x\in V(T):\chi(x)\cap V(P)\neq\emptyset\}.\) Then \(T_P\) is a subtree of \(T\). We claim that the family \(\mathcal{T}=\{T_P:P\text{ is an }A\text{--}B\text{ path in }G\}\) contains no \(q\) pairwise vertex-disjoint subtrees. Indeed, if \(T_{P_1},\dots,T_{P_q}\) are pairwise vertex-disjoint, then the paths \(P_1,\dots,P_q\) are pairwise vertex-disjoint and anticomplete, contradicting that \(A\) and \(B\) are \(q\)-slim. Indeed, a common vertex, or an edge between two of the paths, would be contained in some bag, forcing the corresponding subtrees to intersect.

By 14, there exists a set \(Z\subseteq V(T)\) with \(|Z|<q\) such that \(Z\) intersects every subtree in \(\mathcal{T}\). Let \[X=\bigcup_{z\in Z}\chi(z).\] Then \(X\) intersects every \(A\)–\(B\) path in \(G\). Hence no connected component of \(G\setminus X\) contains both a vertex of \(A\) and a vertex of \(B\), and so \(G\setminus X\in\mathcal{P}_{A,B}\).

Finally, since each bag \(\chi(z)\) is \((k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,n),8)\)-coverable in \(G\) and \(|Z|<q\), the set \(X\) is \((qk^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,n),8)\)-coverable in \(G\). Thus \(G\) is \((qk^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,n),8,\mathcal{P}_{A,B})\)-close, as desired. ◻

Proof. Let \(\mathcal{P}:=\mathcal{P}_{A,B}\). We first check that every induced subgraph of \(G\) is \((\tau,8,\mathcal{P})\)-close. Let \(H\subseteq G\) be an induced subgraph. Since \(\mathcal{C}_t\) is hereditary, \(H\in\mathcal{C}_t\). Moreover, \(A\cap V(H)\) and \(B\cap V(H)\) are \(q\)-slim in \(H\). By 2, there is an \((A\cap V(H))\)–\((B\cap V(H))\) separator \(X\) in \(H\) which is \((qk^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(t,|H|),8)\)-coverable in \(H\). Since \(|H|\leq n\), the set \(X\) is \((\tau,8)\)-coverable in \(G\), and \(H\setminus X\in\mathcal{P}\). Thus \(H\) is \((\tau,8,\mathcal{P})\)-close.

Since \(\mathcal{C}_t\subseteq\mathcal{F}_t\), we may apply 11 with parameters \(k=\tau\), \(r=8\), \(p=\ell\), \(s=\omega+1\), and \(a = h\). Since \(h>\ell \tau\left\lceil \log n \right\rceil\), we obtain a set \(T\subseteq V(G)\) with \(|T|\leq c_{A,B}\) such that either \(G\setminus T\in\mathcal{P}\), or there exist sets \(R_1,\dots,R_\ell\) which are pairwise disjoint and anticomplete, each have at most \(\tau\) connected components and are internally \((\tau,8)\)-coverable, and such that \((G\setminus T)\setminus R_i\in\mathcal{P}\) for every \(i\in[\ell]\).

In the first case, \(T\) is an \(A\)–\(B\) separator of size at most \(c_{A,B}\). Thus we may assume that the second case holds. For every \(i\in[\ell]\), set \(C_i:=R_i\cap T\), \(S_i:=R_i\setminus T\), and let \(D:=T\setminus\bigcup_{i\in[\ell]}C_i\). Then \(D':=D\cup\bigcup_{i\in[\ell]}C_i=T\), and \(S_i\cup C_i=R_i\) for every \(i\). Since the sets \(R_1,\dots,R_\ell\) are pairwise disjoint and anticomplete, \((D,\{(S_i,C_i):i\in[\ell]\})\) is a clean-set-packing of length \(\ell\).

It is \(\tau\)-thick because, for every \(i\), the graph induced by \(S_i\cup C_i=R_i\) in \(G\setminus(D'\setminus C_i)\) has at most \(\tau\) connected components. Also, its cost is \(|D'|=|T|\leq c_{A,B}\). Finally, since \((G\setminus T)\setminus R_i=(G\setminus D')\setminus S_i\in\mathcal{P}_{A,B}\), the set \(S_i\) is an \(A'\!\)–\(B'\) separator in \(G\setminus D'\), where \(A':=A\cap V(G\setminus D')\) and \(B':=B\cap V(G\setminus D')\). Hence this is an \((A,B)\)-packing. ◻

Proof. Fix \(i\in[\ell']\). We have \(A'\subseteq\mathcal{B}_1\subseteq\mathcal{B}_{(2i-1)\gamma}\), since \(d(v)\leq 1\) for every \(v\in A'\) and \((2i-1)\gamma\geq 1\). Similarly \(B'\subseteq \Bar{\mathcal{B}}_{2\ell'\gamma}\subseteq \Bar{\mathcal{B}}_{2i\gamma}\), since \(d(v)=\ell\) for every \(v\in B'\) and \(2i\gamma < \ell\). For the second condition, let \(P\) be a \(\mathcal{B}_{(2i-1)\gamma}\)–\(\Bar{\mathcal{B}}_{2i\gamma}\) path in \(G'\). Define \(u\) to be the last vertex of \(P\) that lies in \(V(P)\cap \mathcal{B}_{(2i-1)\gamma}\) and let \(v\) be the first vertex of \(P\) after \(u\) that lies in \(V(P)\cap \Bar{\mathcal{B}}_{2i\gamma})\). Observe that both are well defined since the first and last vertex of \(P\) lies in \(\mathcal{B}_{(2i-1)\gamma}\) and \(\Bar{\mathcal{B}}_{2i\gamma}\) respectively. Let \(P'\) be the \(u\)–\(v\) subpath of \(P\), and observe that the interior of \(P'\) is contained in \(\mathcal{L}_i\). Hence \((\mathcal{B}_{(2i-1)\gamma},\,\mathcal{L}_i,\,\Bar{\mathcal{B}}_{2i\gamma})\) is strong-barrier.

Now to show that it is \(\gamma\)-broad, let \(P\) be a \(u\)–\(v\) path with \(u\in \mathcal{B}_{(2i-1)\gamma}\) and \(v\in \Bar{\mathcal{B}}_{2i\gamma}\). Let \(P''\) be an \(A'\)–\(u\) path witnessing \(d(u)\), and let \(Q\) be an \(A'\)–\(v\) path within the \(A'\)–\(v\) walk obtained by concatenating \(P''\) and \(P\). Observe that \(Q\) intersects more than \(2i\gamma\) distinct sets \(S_j\) as \(d(v) > 2i\gamma\), while \(V(P'')\) intersects at most \((2i-1)\gamma\) as \(d(u)\leq(2i-1)\gamma\), and \(v\) lies in at most one. Thus the interior of \(P\) intersects at least \(\gamma\) distinct sets \(S_j\). Since the sets \(S_j\cup C_j\) for \(j\in[\ell]\) pairwise do not touch in \(G\), each fragment lies in a single \(S_j\cup C_j\). Consequently, we conclude that \(P\) intersects at least \(\gamma\) distinct fragments. ◻

Proof. Let \(I\subseteq[\ell']\) denote the set of \(i\in[\ell']\) such that \(\mathcal{L}_i\) satisfies \(\bigl|\bigcup_{C\in\mathcal{A}_i}V(C)\bigr|\leq \lambda_1\). We first show that \(|I|\geq\ell'/2\). Suppose for contradiction that \(|[\ell']\setminus I|>\ell'/2\). The layers \(\mathcal{L}_i\), \(i\in[\ell']\), are pairwise disjoint subsets of \(V(G')\) with \(\bigcup_{C\in\mathcal{A}_i}V(C)\subseteq\mathcal{L}_i\) for every \(i\in[\ell']\). Hence, \[\sum_{i\in[\ell']}|\mathcal{L}_i| \quad \geq\quad \sum_{i\in[\ell']\setminus I} \sum_{C\in\mathcal{A}_i}|V(C)| \quad >\quad |[\ell']\setminus I|\cdot\lambda_1 \quad \geq \quad |[\ell']\setminus I|\cdot\frac{2n}{\ell'} \quad >\quad \frac{\ell'}{2}\cdot\frac{2n}{\ell'} \quad =\quad n.\]

Define \(\mathcal{A}_I := \bigcup_{i\in I}\mathcal{A}_i\). Construct an auxiliary graph \(H\) with vertex set \(\mathcal{A}_I\cup\mathcal{F}\), joining two vertices of \(H\) by an edge whenever the vertex subsets of \(G\) they represent touch in \(G\).

For this proof, we say that a vertex subset forms a twin class if it is a maximal set of pairwise false-twins.

Now, since \(|I|\geq\ell'/2\), we conclude that there exists \(i\in I\subseteq[\ell']\subseteq[\ell]\), such that: \[\begin{align} \abs{\{F\in\mathcal{F}: V(F)\cap C\neq\emptyset,\, C\in\mathcal{A}_i\}}\qquad &\leq\qquad \frac{1}{|I|}\sum_{i\in I}\abs{\{F\in\mathcal{F}: V(F)\cap C\neq\emptyset,\, C\in\mathcal{A}_i\}} \\ &\leq\qquad \frac{1}{|I|}\sum_{C\in\mathcal{A}_I}\deg_H(C) &&=\quad \frac{|E(H)|}{|I|} \\ &<\qquad \frac{\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}}g^{\text{\scalebox{0.7}{\tiny\ref*{prop:bipartite_lemma}}}}(\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}})|\mathcal{F}|}{\ell'/2} &&\leq\quad \frac{2\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}}g^{\text{\scalebox{0.7}{\tiny\ref*{prop:bipartite_lemma}}}}(\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}})\ell k}{\ell'} \\ &\leq\qquad 16\,\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}}\,g^{\text{\scalebox{0.7}{\tiny\ref*{prop:bipartite_lemma}}}}(\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}})\,\gamma k &&=\quad \lambda_2 . \end{align}\] Here, the second inequality holds since every \(F\in\mathcal{F}\) with \(V(F)\cap C\neq\emptyset\) for some \(C\in\mathcal{A}_i\), touches \(C\) and is hence adjacent to it in \(H\). The strict inequality follows from 4 together with \(|I|\geq\ell'/2\), the next inequality holds since the \((A,B)\)-packing\((D,\left\{(S_j,C_j):j\in[\ell]\right\})\) is \(k\)-thick, so that each \(\mathcal{F}_j\) has at most \(k\) elements and \(|\mathcal{F}|=\sum_{j=1}^\ell|\mathcal{F}_j|\leq\ell k\). The final inequality uses \(\ell/\ell'\leq 8\gamma\). ◻

Proof. We prove this by induction on \(n\). For the base case observe that if \(n < n_0\), then the inequality holds trivially. Now, fix a positive integer \(n \geq n_0\) and assume that the statement holds for all strictly smaller positive integers. Let \(G\in \mathcal{C}_t\) and \(A,B\subseteq V(G)\) be the graph and the pair of vertex subsets of \(G\) that realize \(T^\omega_t(n)\).

Assume that \(|V(G)| = n\), otherwise the size of the smallest \(A\)–\(B\) separator in \(G\) has size less than \(T_t^\omega(n-1)\), which is at most \(T_t^\omega(n)\) as \(c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}\), \(\lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}\) and \(\lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}\) are non-decreasing in \(n\). Since it is clear that \(T^\omega_t(n)\leq n\), we focus on the second term. Let \(\ell = \ell_t(n)\). By 15 applied to the tuple \((G,A,B,q,\ell)\), \(G\) either has an \((A,B)\)-separator of size \(c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega)\), or a \(\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n)\)-thick \((A,B)\)-packing\(\Pi\) in \(G\) of length \(\ell\) and cost at most \(c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega)\). Assume the latter since in the former case, we are done. Now, as \(\ell \geq \ell_t(n_0) \geq 8\gamma\) and as \(\gamma \geq \tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}}\), we may apply [thm:strong95barrier] to obtain a strong-barrier \((L,Z,R)\) corresponding to \(\Pi\) which is \(\gamma\)-broad and \((\lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,n,\ell),\, \lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,t,\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n)))\)-light. Let \(Z' := \bigcup_{C\in\mathcal{A}}V(C)\), where \(\mathcal{A}\) denotes the active components of \((L,Z,R)\). Let \(\mathcal{F}\) denote the fragments of \(\Pi\) and let \(\mathcal{F}' := \{F\in\mathcal{F}: V(F)\cap Z'\neq\emptyset\}\). Consider the graph \(G'[Z']\), and denote \(V(F)\cap Z'\) using \(F'\) for every \(F\in\mathcal{F}'\). Let, \[\hat{\mathcal{F}}\;\;:=\;\;\{\{F_{i},F_{j}\}~:~F_{i},F_{j}\in\mathcal{F}',\, F'_{i},F'_{j} \text{ is a q-slim pair in }G'[Z']\}.\] Let \(\Psi := \bigcup_{\{F_i,F_j\}\in\hat{\mathcal{F}}}\Psi_{ij}\), where, for each \(\{F_i,F_j\}\in\hat{\mathcal{F}}\), \(\Psi_{ij}\) denotes the smallest \(F'_i\)–\(F'_j\) separator in \(G'[Z']\).

Now, from 5 it follows that, \[\begin{align} T_t^\omega(n)\quad &\leq\quad |D'| + |\Psi| \\ &\leq\quad c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega) \;\;+\;\;\sum_{\{F_i,F_j\}\in\hat{\mathcal{F}}} |\Psi_{ij}| \\ &\leq\quad c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega) \;\;+\;\;\lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,t,\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n))^2\cdot T^\omega_t\bigl(\lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,n,\ell)\bigr). \end{align}\] The last inequality uses that \((L,Z,R)\) is \(\bigl(\lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,n,\ell),\lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,t,\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n))\bigr)\)-light, which gives two bounds. First, \(|\hat{\mathcal{F}}|\leq\lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,t,\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n))^2\), since \(\hat{\mathcal{F}}\subseteq\mathcal{F}'\times\mathcal{F}'\). Second, for every \(\{F_i,F_j\}\in\hat{\mathcal{F}}\), \(|\Psi_{ij}|\leq T^\omega_t\bigl(\lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,n,\ell)\bigr)\), since \(G'[Z']\in\mathcal{C}_t\) with \(|Z'|\leq\lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,n,\ell)\) and \(\omega(G'[Z'])\leq\omega\), and \(F'_i,F'_j\) form a \(q\)-slim pair. ◻

Proof. For ease of exposition, we write \(c(n) := c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega)\), \(\lambda_1(n) := \lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,n,\ell)\), and \(\lambda_2(n) := \lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,t,\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n))\). To prove the lemma, for each positive integer \(N\) we define a function on the positive integers by \[H_N(n) \;\;=\;\; \begin{cases} n_0, & \text{if } n \leq n_0, \\[4pt] c(N) + \lambda_2(N)^2\cdot H_N\bigl(\lambda_1(n)\bigr), & \text{otherwise}. \end{cases}\] Since the functions \(c\) and \(\lambda_2\) are non-decreasing in \(n\), \(T_t^\omega(n) \leq H_N(n)\) for every positive integer \(N\) and every \(n \in [N]\). Hence, to prove the lemma, it suffices to upper bound \(H_N(N)\). To this end, we claim that \[H_N(n) \;\;\leq\;\;(n_0+1)\cdot c(N)\cdot\lambda_2(N)^{2D_\ell(n)} \;-\; \frac{c(N)}{\lambda_2(N)^2 - 1}\] for all positive integers \(n,N\). The right-hand side is well defined since \(\lambda_2(N) > 1\) for every \(N\). We fix an arbitrary positive integer \(N\) and prove the claim for that \(N\) by induction on \(n\). For the base case, observe that when \(n < n_0\), since \(\lambda_2(N) \geq 2\) and \(c(N)\geq 1\), we have, \[\begin{align} (n_0+1)\cdot c(N)\cdot\lambda_2(N)^{2D_\ell(n)} - \frac{c(N)}{\lambda_2(N)^2 - 1} \quad &\geq\quad (n_0+1)\cdot c(N) - c(N) \\ &\geq\quad n_0 \quad =\quad H_N(n). \end{align}\] For the inductive step, fix a positive integer \(n \geq n_0\) and assume that the statement holds for all positive integers smaller than \(n\). We have,

\[\begin{align} H_N(n)\;\; &= \;\;c(N) + \lambda_2(N)^2\cdot H_N\bigl(\lambda_1(n)\bigr) \\ &\leq \;\;c(N) + \lambda_2(N)^2\cdot \Biggl((n_0+1)\cdot c(N)\cdot \lambda_2(N)^{2D_\ell(\lambda_1(n))} \;-\; \frac{c(N)}{\lambda_2(N)^2 - 1} \Biggr) \\ &\leq \;\;c(N) + (n_0+1)\cdot c(N)\cdot \lambda_2(N)^{2(D_\ell(\lambda_1(n)) + 1)} \;-\; c(N)\cdot \frac{\lambda_2(N)^2}{\lambda_2(N)^2 - 1} \\ &\leq \;\;(n_0+1)\cdot c(N)\cdot \lambda_2(N)^{2D_\ell(n)} \;-\; c(N)\left(\frac{\lambda_2(N)^2}{\lambda_2(N)^2 - 1} - 1 \right) \\ &\leq \;\;(n_0+1)\cdot c(N)\cdot \lambda_2(N)^{2D_\ell(n)} \;-\; \frac{c(N)}{\lambda_2(N)^2 - 1}. \end{align}\] This proves our claim and consequently the lemma. ◻

Proof. Since \(O(\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n) \subseteq o(\log n)\), we have \(\ell_t(n) = o(n)\), and since \(\ell_t\) is a monotonically increasing function, \(\ell_t(n) > 256\gamma^2\) for some positive integer \(n\). Consequently \(D_\ell(n)\) is well-defined. Let \(n_0\) be the smallest integer \(n\) such that \(\ell_t(n) > 256\gamma^2\). For each positive integer \(n\), write \(\lambda_1(n) := \lambda_1^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,n,\ell_t(n)) = 16\gamma n/\ell_t(n)\). By definition of \(n_0\) and monotonicity of \(\ell_t\), for every \(n\geq n_0\) we have \(\log(\ell_t(n)) \geq \log(\ell_t(n_0)) > 2\log(16\gamma)\), and hence \[\log n - \log\lambda_1(n) \;=\;\log n\; -\; \left(\log(16\gamma) + \log n - \log(\ell_t(n))\right)\;=\;\log(\ell_t(n)) - \log(16\gamma) \;\geq\;\tfrac{1}{2}\log(\ell_t(n)).\]

We show by strong induction on \(n\) that \(D_\ell(n)\leq \tfrac{4}{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2} n\) for every positive integer \(n\). For the base case, observe that when \(n < n_0\), we have \(D_\ell(n)=0\leq \tfrac{4}{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2} n\), as required. For the inductive step, fix a positive integer \(n \geq n_0\) and assume that the statement holds for all positive integers smaller than \(n\). Now, we get the following inequality, \[\begin{align} \log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n - \log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}\lambda_1(n)\quad &\geq\quad \tfrac{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}{2}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2-1}n\cdot\bigl(\log n-\log\lambda_1(n)\bigr) \\ &\geq\quad \tfrac{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}{2}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2-1}n\cdot\tfrac{1}{2}\log(\ell_t(n)) \\ &\geq\quad \tfrac{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}{2}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2-1}n\cdot\tfrac{1}{2}d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n \\ &=\quad \tfrac{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}{4}. \end{align}\] Here the first inequality applies the mean value theorem to the function \(x\mapsto x^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}\) on \([\log\lambda_1(n),\log n]\): since the derivative \(\frac{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}{2}x^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2-1}\) is decreasing in \(x\) as \(\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2-1<0\), it is minimized at \(x=\log n\), giving the lower bound \(\frac{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}{2}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2-1}n\cdot(\log n-\log\lambda_1(n))\). The second uses \(n \geq n_0\) combined with our earlier observation, and the last one substitutes \(\log(\ell_t(n))=d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n\). Combining this with the definition of \(D_\ell\) and the inductive assumption, yields the following. \[\begin{align} D_\ell(n) \quad &=\quad D_\ell(\lambda_1(n)) + 1 \\ &\leq\quad \tfrac{4}{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}(\lambda_1(n)) + 1 \\ &\leq\quad \tfrac{4}{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}\Bigl(\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2} n - \tfrac{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}{4}\Bigr) + 1 \\ &=\quad \tfrac{4}{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2} n. \end{align}\] This completes the induction and thereby the proof of the lemma. ◻

Proof. Let us assume without loss of generality that \(n \geq 2\), since otherwise the theorem holds trivially. Fix \(t\), let \(\omega\) be a positive integer, set \(q:=q^{\text{\scalebox{0.7}{\tiny\ref*{lem:pqslim}}}}\), and let \(\ell=\ell_t(n):=2^{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n}\). Let \(n_0\) be the smallest integer \(n\) such that \(\ell_t(n) > 256\gamma^2\), which exists since \(\ell_t\) is a monotonically increasing function on \(n\). By 20, \[T^\omega_t(n) \;\;\leq\;\;(n_0+1)\cdot c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega)\cdot\lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,t,\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n))^{2D_\ell(n)}. \]

We begin by upper bounding \(c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega)\): \[\begin{align} c^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(t,q,\ell,n,\omega)\quad &=\quad \Bigl(2h\cdot(\omega+1)\cdot\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n)\Bigr)^\mu \\ &=\quad \Bigl(2\cdot\bigl(\ell\, qk^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(\left\lceil \log n \right\rceil+1)\bigr)\cdot qk^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\cdot (\omega+1)\Bigr)^\mu\\ &\leq\quad c_1\cdot \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}} \cdot \left({k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}^{2}\cdot \ell\cdot (\left\lceil \log n \right\rceil+1)\right)^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}} \\ &\leq\quad \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}} \cdot 2^{\log c_1\, +\, \mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(2d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n\, +\, d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n\, +\, c_2\log\log n)}\\ &\leq\quad \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}} \cdot 2^{c_3\,\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n}\end{align}\] Here \(c_1,c_2\) and \(c_3\) are suitable constants that depend only on \(t\). The last inequality uses the fact that \(O(\log\log n)\subseteq O(\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n)\subseteq o(\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n)\) and that \(n \geq 2\). The rest of the transitions only involve substituting definitions or performing simplifications. Next, since \(\gamma,\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}},g^{\text{\scalebox{0.7}{\tiny\ref*{prop:bipartite_lemma}}}}(\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}})\) and \(q\) depend only on \(t\) and since \(D_\ell(n)\leq\tfrac{4}{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n\), we have the following bound: \[\begin{align} \lambda_2^{\text{\scalebox{0.7}{\tiny\ref*{thm:strong_barrier}}}}(\gamma,t,\tau^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}(q,t,n))^{2D_\ell(n)} \quad &=\quad \bigl(16\gamma\,\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}}\,g^{\text{\scalebox{0.7}{\tiny\ref*{prop:bipartite_lemma}}}}(\tilde{t}^{\text{\scalebox{0.7}{\tiny\ref*{lem:squigglyktt}}}})\cdot qk^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\bigr)^{2D_\ell(n)} \\ \quad &\leq\quad \bigl(c_4\,2^{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n}\bigr)^{\tfrac{8}{d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}\log^{\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \\ \quad &\leq\quad 2^{c_5\,\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n}. \end{align}\] Here \(c_4\) and \(c_5\) are suitable constants that depend only on \(t\). Combining (1) and (2) via \((\dagger)\), gives \[\begin{align} T^\omega_t(n) \quad &\leq\quad (n_0+1)\cdot \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}}\cdot 2^{c_3\,\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n}\cdot 2^{c_5\,\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \\ \quad &\leq\quad \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}}\cdot 2^{\log (n_0+1)\, +\, (c_3+c_5)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \\ \quad &=\quad \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}}\cdot 2^{\beta(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n}. \end{align}\] Here \(\beta(t)\) is a suitably chosen constant that depends only on \(t\). This completes the proof of the theorem. ◻

Proof. Let us assume without loss of generality that \(n \geq 2\), since otherwise the theorem holds trivially. Write \(p:=p^{\text{\scalebox{0.7}{\tiny\ref*{lem:pqslim}}}}\), \(q:=q^{\text{\scalebox{0.7}{\tiny\ref*{lem:pqslim}}}}\), and \(\omega:=\omega(G)\). By 13 applied to \((G,Y)\) with \(\ell = p\), \(G\) either has a \(Y\)-balanced-separator of size \(\kappa^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(t,p,n,\omega)\), or a \((Y,\frac{1}{2})\)-packing\((D,\left\{(S_i,C_i):i\in[p]\right\})\) of length \(p\) that is \(4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\)-thick and \(\kappa^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(t,p,n,\omega)\)-costly. Assume the latter since in the former case, we are done via the upper bound on \(\kappa^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(t,p,n,\omega)\) that we prove towards the end of this lemma. Set \(D':=D\cup\bigcup_{i=1}^p C_i\) and \(G':=G-D'\), so that each \(S_i\) is a \((Y,\frac{1}{2})\)-balanced separator in \(G'\). For every \(i\in[p]\), let \(\mathcal{F}_i\) denote the set of connected components of \(G[S_i\cup C_i]\), which, with slight abuse of notations, we call fragments. Since \((D,\left\{(S_i,C_i):i\in[p]\right\})\) is \(4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\)-thick, we have \(|\mathcal{F}_i|\leq 4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\) for every \(i\in [p]\). Let \(\mathcal{F}:= \bigcup_{i\in[p]}\mathcal{F}_i\) and let \(F' := F\cap V(G')\) for every \(F\in\mathcal{F}\). Let, \[\hat{\mathcal{F}}\quad :=\quad \{\{F_{i},F_{j}\}~:~F_{i},F_{j}\in\mathcal{F}, F'_i,F'_j \text{ is a q-slim pair in } G'\}.\] For every \(\{F_{i},F_{j}\}\in\hat{\mathcal{F}}\), let \(\Psi_{ij}\) denote the smallest \(F'_{i}\)–\(F'_{j}\) separator in \(G'\), which by [thm:slim95implies95separable] has size at most \(T^\omega_t(n)\). Finally, let \(\Psi := \bigcup_{\{F_i,F_j\}\in\hat{\mathcal{F}}}\Psi_{ij}\).

Now, from 6 it follows that, \(D'\cup\Psi\) is a \((Y,\frac{1}{2})\)-balanced separator in \(G\) of size at most \(\kappa^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(t,p,n,\omega) + (4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}p)^2\cdot T^\omega_t(n)\), since there are at most \(\sum_{i=1}^p|\mathcal{F}_i|\leq 4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}p\) fragments in total, each contributing a separator of size at most \(T^\omega_t(n)\). It remains to bound \(\kappa^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(t,p,n,\omega) + (4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}p)^2\cdot T^\omega_t(n)\). We begin with the following, \[\begin{align} \kappa^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(t,p,n,\omega)\quad &=\quad \Bigl(2h'\cdot(\omega+1)\cdot 4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\Bigr)^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}} \\ &=\quad \Bigl(2\cdot\bigl(p\, 4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}(\left\lceil \log n \right\rceil+1)\bigr)\cdot 4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\cdot (\omega+1)\Bigr)^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}}\\ &\leq\quad c_1\cdot \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}} \cdot \left({k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}^{2}\cdot (\left\lceil \log n \right\rceil+1)\right)^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}} \\ &\leq\quad \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}} \cdot 2^{\log c_1\, +\, \mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(2d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n\, +\, c_2\log\log n)}\\ &\leq\quad \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}} \cdot 2^{c_3\,\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n}\end{align}\] Here \(c_1,c_2,c_3\) are suitable constants that depend only on \(t\). The last inequality uses the fact that \(O(\log\log n)\subseteq o(\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n)\). The rest of the transitions only involve substituting definitions or performing simplifications. Combining this with the upper bound on \(T^\omega_t(n)\) from [thm:slim95implies95separable] yields, \[\begin{align} \kappa^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}(t,p,n,\omega)\; +\; (4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}p)^2\cdot T^\omega_t(n) \;\;&\leq\;\;\omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}}\cdot 2^{c_3\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n}\; +\; (4k^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}p)^2\cdot \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}}\cdot 2^{\beta(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \\ \;\;&\leq\;\;\omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:Y_packing_new}}}}}\cdot 2^{c_3\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n}\; +\; c_4\cdot 2^{2d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n}\cdot \omega^{\mu^{\text{\scalebox{0.7}{\tiny\ref*{lem:AB_packing_new}}}}}\cdot 2^{\beta(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \\ \;\;&\leq\;\;\omega^{\mu(t)}\cdot 2^{c_3\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n\; +\; \log c_4\; +\; 2d^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}}n\; +\; \beta(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \\ \;\;&\leq\;\;\omega^{\mu(t)}\cdot 2^{\nu(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n}, \end{align}\] Here \(c_4\), \(\mu(t)\) and \(\nu(t)\) are suitable constants that depend only on \(t\), which completes the proof of the lemma. ◻

Proof. Let us assume without loss of generality that \(n \geq 2\), since otherwise the theorem holds trivially. Let \(G\in\mathcal{C}_t\) be a graph on \(n\) vertices. Set \(a:=(2t\cdot \log n + 3)^4\) and let \(c_1\) be the smallest constant such that \(a\leq c_1\log^4 (n+1)\) for every non-negative integer \(n\), and observe that \(c_1\) depends only on \(t\). Since \(G\in\mathcal{C}_t\), we have that \(G\) is \(\overline{2K_t}\)-free, and so 23 applied to the tuple \((G,t,2,1)\) implies the existence of a \((1,a)\)-container family \(\mathcal{F}\) in \(G\) satisfying \(|\mathcal{F}|\leq(n+1)^a\). Define \(\hat{\nu}(t)\) to be the smallest positive integer \(z\) such that, for every \(n \geq 2\), \[(\omega_n(z))^{\mu(t)}\cdot f_n(\nu(t)) \;\;<\;\;f_n(z),\] where \(\mu(t)\) and \(\nu(t)\) are the constants in 22, and \(f_n(z)\) and \(\omega_n(z)\) are functions on the set of positive integers, defined as follows: \[f_n(z) := 2^{z\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \;\;\text{and}\;\; \omega_n(z) := 42\cdot(\left\lceil a\cdot \log (n+1) + 2 \right\rceil + 680000\cdot\left\lceil \log 2n\cdot a^3\cdot\log(a\, f_n(z)+4) \right\rceil)\]

Let us denote \(\omega_n(\hat{\nu}(t))\) as \(\omega_n\) and \(f_n(\hat{\nu}(t))\) as \(f_n\). Now, suppose for contradiction that \(tw_\alpha(G) > 1020000\cdot\left\lceil \log(2n)\cdot a^3\cdot\log(a\, f_n+4)\cdot f_n \right\rceil\). Applying 24 to the tuple \((G,f_n,a,1,\mathcal{F})\), we obtain an induced subgraph \(G'\subseteq G\) and an independent set \(I\subseteq V(G')\), such that every induced subgraph \(H\) of \(G'\) with \(\alpha(H)\leq 1\) satisfies \(|V(H)|\leq \omega_n\), and every \((I,\frac{1}{2})\)-balanced separator \(S\) in \(G'\) satisfies \(\mathrm{cov}_\mathcal{F}(S)\geq f_n\). Since a maximum clique \(H\) of \(G'\) satisfies \(\alpha(H)\leq1\) and \(|V(H)|=\omega(G')\), the former property gives \(\omega(G')\leq\omega_n\). Furthermore, \(G'\in\mathcal{C}_t\) since \(\mathcal{C}_t\) is hereditary. Thus, applying 22 to \(G'\) yields an \((I,\tfrac{1}{2})\)-balanced separator \(S\) of size at most \(\omega(G')^{\mu}\cdot f_{n'}(\nu(t))\), which is at most \(\omega_n^{\mu}\cdot f_n(\nu(t))< f_n\). As \(\mathcal{F}\) is a \((1,a)\)-container family, this implies \(\mathrm{cov}_\mathcal{F}(S)\leq|S|<f_n\), which is a contradiction. Thus, we get, \[\begin{align} tw_\alpha(G) \;\; &\leq\;\;1020000\cdot\left\lceil \log(2n)\cdot a^3\cdot\log(af_n+4)\cdot f_n \right\rceil \\ &=\;\;1020000\cdot\Bigl\lceil \log(2n)\cdot c_1^3\cdot\log^{12}(n+1)\cdot \log\bigl(c_1\cdot \log^4(n+1)\cdot 2^{\hat{\nu}(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} + 4\bigr) \cdot f_n \Bigr\rceil\\ &\leq\;\;c_2\cdot \log^{13} n\cdot \Bigl(\log c_1 + 4\log\log (n+1) + \hat{\nu}(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n + 2\Bigr) \cdot f_n \\ &\leq\;\;c_3\cdot \log^{14} n\cdot 2^{\hat{\nu}(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n}\\ &\leq\;\;2^{\log(c_3)\, +\, 14\log\log n\, +\, \hat{\nu}(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n} \end{align}\] Since \(O(\log\log n)\subseteq o(\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n)\), we conclude that there exists some constant \(\nu'(t)\) depending only on \(t\) such that, for every \(n\geq 2\), \[\log c_3\;+\;14\log\log n\;+\;\hat{\nu}(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n \quad \leq \quad \nu'(t)\log^{1-\epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2}n\] Thus, setting \(\nu'(t)\) as above and \(\epsilon(t) = \epsilon^{\text{\scalebox{0.7}{\tiny\ref*{prop:coarse_treewidth_our_class}}}}/2\) completes the proof of the theorem. ◻

Proof. Write \(n:=|V(G)|\) and let \(b:=O\bigl(t^3\sqrt{|E(G)|}\bigr)\) denote the size bound of 25 for \(G\). If \(|Y|\le1\), then \(S:=Y\) is a \((Y,\tfrac12)\)-balanced separator of size at most one, so assume \(|Y|\ge2\).

We prove by induction on |C| that, for every \(C\subseteq V(G)\) there is a set \(S\subseteq C\) with \(|S|\le b\bigl(\log_{3/2}|C|+1\bigr)\) such that every connected component of \(G[C]-S\) contains at most \(\tfrac12|Y|\) vertices of \(Y\). The lemma then follows from this statement by taking \(C:=V(G)\), since \(b\bigl(\log_{3/2}n+1\bigr)=O(b\log n)= O\bigl(t^3\log n\cdot\sqrt{|E(G)|}\bigr)\).

We argue by induction on \(|C|\). If no connected component of \(G[C]\) contains more than \(\tfrac12|Y|\) vertices of \(Y\), then \(S:=\emptyset\) suffices. Otherwise 25 provides a \((V(C),\tfrac23)\)-balanced separator \(S_1\) of \(G[C]\) with \(|S_1|\le b\). Every connected component of \(G[C]-S_1\) has at most \(\tfrac23|C|\) vertices, and since these components partition \(Y\cap C\), at most one of them contains more than \(\tfrac12|Y|\) vertices of \(Y\). If there is no such component, then \(S:=S_1\) suffices, as \(|S_1|\le b\le b(\log_{3/2}|C|+1)\). Otherwise let \(C'\) be the unique such component, so \(|C'|\le\tfrac23|C|\) and in particular \(|C'|<|C|\). By the induction hypothesis applied to \(C'\) there is a set \(S_2\subseteq C'\) with \[|S_2|\le b(\log_{3/2}|C'|+1)\le b(\log_{3/2}(\tfrac23|C|)+1)=b\log_{3/2}|C|\] such that every component of \(G[C']-S_2\) contains at most \(\tfrac12|Y|\) vertices of \(Y\). Set \(S:=S_1\cup S_2\). Every connected component of \(G[C]-S\) either is a component of \(G[C]-S_1\) other than \(C'\), or is a component of \(G[C']-S_2\); in both cases it contains at most \(\tfrac12|Y|\) vertices of \(Y\). Finally \(|S|\le|S_1|+|S_2|\le b+b\log_{3/2}|C|=b(\log_{3/2}|C|+1)\), completing the induction. ◻

Proof of 3. Let \(G\) be a \(K_{t,t}\)-induced-minor-free graph and set \(n:=|V(G)|\). We may assume that \(n\) is larger than some constant \(n_0=n_0(t)\): for smaller \(n\) we have \(\mathrm{tw}_\alpha(G)\le n=O(1)\), so the claimed bound holds by taking the constant in the \(O\)-notation large enough. Throughout, asymptotic notation hides constants depending only on \(t\).

Since \(\overline{2K_t}=K_{t,t}\) and \(G\) contains no induced \(K_{t,t}\), \(G\) is \(\overline{2K_t}\)-free. Applying 23 to the tuple \((G,t,2,1)\) therefore yields a \((1,a)\)-container family \(\mathcal{F}\) of \(G\) with \(a\;\le\;(2t\log n+3)^4\;=\;O(\log^4 n)\) and \(|\mathcal{F}|\;\le\;(n+1)^a\). Since a \((1,1)\)-container family is also a \((1,2)\) container family without loss of generality \(a \geq 2\). Furthermore, \(\log|\mathcal{F}|\le a\log(n+1)=O(\log^5 n)\).

Let \(c,d_0>0\) be the constants provided by 27 for \(t\), and set \[f\;:=\;\bigl\lceil \sqrt n\,(\log n)^{7d_0+2}\bigr\rceil .\] Suppose towards a contradiction that \[\mathrm{tw}_\alpha(G)\;>\;1020000\, \bigl\lceil \log 2n\cdot a^3\cdot\log(af+4)\cdot f\bigr\rceil .\] Since \(a\ge2\), 24 applied to \((G,f,a,1,\mathcal{F})\) produces an induced subgraph \(G'\subseteq G\) and an independent set \(I\subseteq V(G')\) such that

• every clique \(H\) of \(G'\) satisfies \(|V(H)|\le 42\bigl(\lceil\log 4|\mathcal{F}|\rceil +680000\lceil\log 2n\cdot a^3\cdot\log(af+4)\rceil\bigr)\); and

• every \((I,\tfrac12)\)-balanced separator \(S\) of \(G'\) satisfies \(\mathrm{cov}_{\mathcal{F}}(S)\ge f\).

We show that the clique number of \(G'\) is polylogarithmic. Let \(H\) be the largest clique in \(G'\), and set \(\omega = |H|\). As \(f\le\sqrt n(\log n)^{7d_0+2}+1\le n\) for \(n\ge n_0\), we have \(\log(af+4)=O(\log n)\). By (i) we have that \[\omega \le\;42\bigl(\lceil\log 4|\mathcal{F}|\rceil +680000\lceil\log 2n\cdot a^3\cdot\log(af+4)\rceil\bigr) \;=\;O(\log^5 n)+O(\log^{14} n)\;=\;O(\log^{14} n),\] where we used \(a^3=O(\log^{12}n)\) and \(\log 2n\) and \(\log(af+4)\) are both upper bounded by \(O(\log n)\).

Since \(G'\) contains no induced subdivision of \(K_{t,t}\) and has no clique on more than \(\omega\) vertices, 27 bounds the average degree of \(G'\) by \(c\omega^{d_0}=O(\log^{14 d_0}n)\). Therefore \(|E(G')| = O(n\log^{14 d_0}n)\), so \(\sqrt{|E(G')|} = O(\sqrt n\,\log^{7d_0}n)\). Hence, applying 26 to \(t\), the (\(K_{t,t}\)-induced-minor-free) graph \(G'\), and \(Y:=I\) yields an \((I,\tfrac12)\)-balanced separator \(S\) of \(G'\) with \[|S|\;=\;O\bigl(t^3\log|V(G')|\cdot\sqrt{|E(G')|}\bigr) \;=\;O\bigl(\log n\cdot\sqrt n\,\log^{7d_0}n\bigr) \;=\;O\bigl(\sqrt n\,\log^{7d_0+1}n\bigr).\] On the other hand every vertex in \(V(G)\) is contained in some set in \(\mathcal{F}\) (since it is a clique), thus \(\mathrm{cov}_{\mathcal{F}}(S)\le|S|\), and combining this with (ii) gives \(|S|\ge\mathrm{cov}_{\mathcal{F}}(S)\ge f=\bigl\lceil\sqrt n(\log n)^{7d_0+2} \bigr\rceil\). But \(O(\sqrt n\,\log^{7d_0+1}n)<\sqrt n(\log n)^{7d_0+2}\le f\) for \(n\ge n_0\), a contradiction.

We conclude that \[\begin{align} \mathrm{tw}_\alpha(G) & \leq 1020000 \cdot \bigl\lceil \log 2n\cdot a^3\cdot\log(af+4)\cdot f\bigr\rceil = O\bigl(\log n\cdot\log^{12}n\cdot\log n\cdot\sqrt n\,\log^{7d_0+2}n\bigr) \\ & = O\bigl(\sqrt n\,(\log n)^{7d_0+16}\bigr). \end{align}\] The theorem follows with \(d:=7d_0+16\). ◻