# Induced subgraphs and tree decompositions
X. Towards logarithmic treewidth for even-hole-free graphs

Tara Abrishami∗† ,  Bogdan Alecu∗∗¶ ,  Maria Chudnovsky∗† ,  Sepehr Hajebi §
and  Sophie Spirkl§∥ ∗Princeton University, Princeton, NJ, USA  ¶ Supported by
DMS-EPSRC Grant EP/V002813/1.  ∗∗School of Computing, University of Leeds,
Leeds, UK  §Department of Combinatorics and Optimization, University of
Waterloo, Waterloo, Ontario, Canada  † Supported by NSF-EPSRC Grant
DMS-2120644 and by AFOSR grant FA9550-22-1-0083.  ∥ We acknowledge the support
of the Natural Sciences and Engineering Research Council of Canada (NSERC),
[funding reference number RGPIN-2020-03912]. Cette recherche a été financée
par le Conseil de recherches en sciences naturelles et en génie du Canada
(CRSNG), [numéro de référence RGPIN-2020-03912]. This project was funded in
part by the Government of Ontario.

###### Abstract.

A generalized $t$-pyramid is a graph obtained from a certain kind of tree (a
subdivided star or a subdivided cubic caterpillar) and the line graph of a
subdivided cubic caterpillar by identifying simplicial vertices. We prove that
for every integer $t$ there exists a constant $c(t)$ such that every
$n$-vertex even-hole-free graph with no clique of size $t$ and no induced
subgraph isomorphic to a generalized $t$-pyramid has treewidth at most
$c(t)\log{n}$. This settles a special case of a conjecture of Sintiari and
Trotignon; this bound is also best possible for the class. It follows that
several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and
Coloring admit polynomial-time algorithms on this class of graphs.

##  1\. Introduction

All graphs in this paper are finite and simple. Let $G=(V(G),E(G))$ be a
graph. For a set $X\subseteq V(G)$, we denote by $G[X]$ the subgraph of $G$
induced by $X$. For $X\subseteq V(G)$, $G\setminus X$ denotes the subgraph
induced by $V(G)\setminus X$. In this paper, we use induced subgraphs and
their vertex sets interchangeably.

For graphs $G$ and $H$, we say that $G$ contains $H$ if some induced subgraph
of $G$ is isomorphic to $H$. For a family $\mathcal{H}$ of graphs, $G$
contains $\mathcal{H}$ if $G$ contains a member of $\mathcal{H}$. Finally, $G$
is $\mathcal{H}$-free if $G$ does not contain $\mathcal{H}$.

Let $v\in V(G)$. The _open neighborhood of $v$_, denoted by $N(v)$, is the set
of all vertices in $V(G)$ adjacent to $v$. The _closed neighborhood of $v$_,
denoted by $N[v]$, is $N(v)\cup\\{v\\}$. Let $X\subseteq V(G)$. The _open
neighborhood of $X$_, denoted by $N(X)$, is the set of all vertices in
$V(G)\setminus X$ with at least one neighbor in $X$. The _closed neighborhood
of $X$_, denoted by $N[X]$, is $N(X)\cup X$. If $H$ is an induced subgraph of
$G$ and $X\subseteq V(G)$, then $N_{H}(X)=N(X)\cap H$ and
$N_{H}[X]=N_{H}(X)\cup(X\cap H)$. Let $Y\subseteq V(G)$ be disjoint from $X$.
We say $X$ is complete to $Y$ if all possible edges with an end in $X$ and an
end in $Y$ are present in $G$, and $X$ is _anticomplete_ to $Y$ if there are
no edges between $X$ and $Y$.

For a graph $G=(V(G),E(G))$, a _tree decomposition_ $(T,\chi)$ of $G$ consists
of a tree $T$ and a map $\chi:V(T)\to 2^{V(G)}$ with the following properties:

  1. (i)

For every $v\in V(G)$, there exists $t\in V(T)$ such that $v\in\chi(t)$.

  2. (ii)

For every $v_{1}v_{2}\in E(G)$, there exists $t\in V(T)$ such that
$v_{1},v_{2}\in\chi(t)$.

  3. (iii)

For every $v\in V(G)$, the subgraph of $T$ induced by $\\{t\in V(T)\mid
v\in\chi(t)\\}$ is connected.

For each $t\in V(T)$, we refer to $\chi(t)$ as a bag of $(T,\chi)$. The
_width_ of a tree decomposition $(T,\chi)$, denoted by
$\operatorname{width}(T,\chi)$, is $\max_{t\in V(T)}|\chi(t)|-1$. The
_treewidth_ of $G$, denoted by $\operatorname{tw}(G)$, is the minimum width of
a tree decomposition of $G$. The term “treewidth” and the study of the
structure of graphs with large treewidth were introduced by Robertson and
Seymour [16] as part of the Graph Minors series.

A hole in a graph is an induced cycle with at least four vertices. The length
of a hole is the number of vertices in it. A hole is even it it has even
length, and odd otherwise. The class of even-hole-free graphs has been studied
extensively (see the survey [19]), but many open questions remain. Among them
are several algorithmic problems: Stable Set, Vertex Cover, Dominating Set,
$k$-Coloring and Coloring. The structural complexity of this class of graphs
is further evidenced by the fact that there exist even-hole-free graphs of
arbitrarily large tree-width [18] (even when the clique number is bounded).
Closer examination of the constructions of [18] led the authors of [18] to
make the following two conjectures (the diamond is the unique simple graph
with four vertices and five edges):

######  Conjecture 1.1 (Sintiari and Trotignon [18]).

For every integer $t$, there exists a constant $c_{t}$ such that every even-
hole-free graph $G$ with no diamond and no clique of size $t$ satisfies
$\operatorname{tw}(G)\leq C_{t}$.

######  Conjecture 1.2 (Sintiari and Trotignon [18]).

For every integer $t$, there exists a constant $C_{t}$ such that every even-
hole-free graph $G$ with no clique of size $t$ satisfies
$\operatorname{tw}(G)\leq C_{t}\log|V(G)|$.

(In fact, [18] only states the two conjectures above for $t=4$.) Conjecture
1.1 was recently proved in [6]. Here we prove a special case of Conjecture
1.2. A generalized $t$-pyramid is a graph obtained from a certain kind of tree
(a subdivided star or a subdivided cubic caterpillar) and the line graph of a
subdivided cubic caterpillar by identifying their simplicial vertices (we give
a precise definition later). We prove:

######  Theorem 1.3.

For every integer $t$, there exists a constant $C_{t}$ such that every even-
hole-free graph $G$ with no clique of size $t$ and no generalized $t$-pyramid
satisfies $\operatorname{tw}(G)\leq c_{t}\log|V(G)|$.

We remark that the construction of [18] shows that the logarithmic bound of
Theorem 1.3 is best possible for this class. Furthermore, before Theorem 1.3
was proved, the complexity of Stable Set, Vertex Cover, Dominating Set,
$k$-Coloring and Coloring when restricted to this class of graphs was not
known.

Given a graph $G$, a path in $G$ is an induced subgraph of $G$ that is a path.
If $P$ is a path in $G$, we write $P=p_{1}\hbox{-}\dots\hbox{-}p_{k}$ to mean
that $V(P)=\\{p_{1},\dots,p_{k}\\}$, and $p_{i}$ is adjacent to $p_{j}$ if and
only if $|i-j|=1$. We call the vertices $p_{1}$ and $p_{k}$ the _ends of $P$_,
and say that $P$ is a path _from $p_{1}$ to $p_{k}$_. The _interior of $P$_,
denoted by $P^{*}$, is the set $V(P)\setminus\\{p_{1},p_{k}\\}$. The _length_
of a path $P$ is the number of edges in $P$. We denote by $C_{k}$ a cycle with
$k$ vertices.

Next we describe a few types of graphs that we will need (see Figures 1 and
2).

Figure 1. Theta, prism, pyramid and an even wheel. Dashed lines represent
paths of length at least one.

A _theta_ is a graph consisting of three internally vertex-disjoint paths
$P_{1}=a\hbox{-}\ldots\hbox{-}b$, $P_{2}=a\hbox{-}\dots\hbox{-}b$, and
$P_{3}=a\hbox{-}\dots\hbox{-}b$, each of length at least 2, such that
$P_{1}^{*},P_{2}^{*},P_{3}^{*}$ are pairwise anticomplete. In this case we
call $a$ and $b$ the ends of the theta.

A _prism_ is a graph consisting of three vertex-disjoint paths
$P_{1}=a_{1}\hbox{-}\dots\hbox{-}b_{1}$,
$P_{2}=a_{2}\hbox{-}\dots\hbox{-}b_{2}$, and
$P_{3}=a_{3}\hbox{-}\dots\hbox{-}b_{3}$, each of length at least 1, such that
$a_{1}a_{2}a_{3}$ and $b_{1}b_{2}b_{3}$ are triangles, and no edges exist
between the paths except those of the two triangles.

Given an integer $k$, a generalized $k$-pyramid is a graph whose vertex set is
the disjoint union of $k+2$ paths $P,Q,R_{1},\dots,R_{k}$, such that the
following hold:

  * •

$P\cup Q$ is a hole.

  * •

For every $i\in\\{1,\dots,k\\}$, the path $R_{i}$ has ends $a_{i}$ and
$b_{i}$.

  * •

For every $i\in\\{1,\dots,k\\}$, $a_{i}$ has exactly two neighbors
$x_{i},y_{i}$ in $P$. Moreover, $x_{i},y_{i}\in P^{*}$ and $x_{i}$ is adjacent
to $y_{i}$.

  * •

For every $i\in\\{1,\dots,k\\}$, $b_{i}$ has exactly one neighbor $z_{i}$ in
$Q$.

  * •

$P$ traverses $x_{1},y_{1},x_{2},y_{2},\dots,x_{k},y_{k}$ in this order.

  * •

$Q$ traverses $z_{1},z_{2},\dots,z_{k}$ in this order (but note that some of
these vertices may coincide).

  * •

For every $i\in\\{1,\dots,k-1\\}$, we have that $y_{i}\neq x_{i+1}$ (and so
$x_{1},y_{1},x_{2},y_{2},\dots,x_{k},y_{k}$ are all distinct).

A generalized $k$-pyramid where $|Q^{*}|=1$ is sometimes referred to as a _$k$
-pyramid_, and a $1$-pyramid is usually called a pyramid.

A _wheel_ $(H,x)$ consists of a hole $H$ and a vertex $x$ such that $x$ has at
least three neighbors in $H$. A wheel $(H,x)$ is even if $x$ has an even
number of neighbors on $H$.

Our main result is a slight strengthening of Theorem 1.3. Let $\mathcal{C}$ be
the class of ($C_{4}$, theta, prism, even wheel)-free graphs (these are
sometimes called “$C_{4}$-free odd-signable graphs”). For every integer $t\geq
1$, let $\mathcal{C}_{t}$ be the class of all graphs in $\mathcal{C}$ with no
clique of size $t$, and let $\mathcal{C}_{tt}$ be the class of all graphs in
$\mathcal{C}_{t}$ that are also generalized $t$-pyramid-free. It is easy to
see that every even-hole-free graph is in $\mathcal{C}$. We prove:

######  Theorem 1.4.

For every integer $t$, there exists a constant $c_{t}$ such that every
$G\in\mathcal{C}_{tt}$ satisfies $\operatorname{tw}(G)\leq C_{t}\log|V(G)|$.

The general idea of the proof of 1.4 is similar to the proof of the main
result of [2]. However, there were several technical steps in [2], dealing
with so called “balanced vertices”, that we managed to circumvent here, using
a much more elegant approach of $k$-lean tree decompositions. In addition to
making the proof less technical, using this tool also allowed us to only
exclude generalized $t$-pyramids instead of pyramids (note that every
generalized $t$-pyramid contains a pyramid).

Figure 2. Examples of generalized $3$-pyramids. Dashed lines represent paths
of length at least one.

###  1.1. Proof outline and organization

Let us now discuss the main ideas of the proof of Theorem 1.4. We will give
precise definitions of the concepts used below later in the paper; our goal
here is to sketch a road map of where we are going. Obtaining a tree
decomposition is usually closely related to producing a collection of “non-
crossing separations,” which roughly means that the separations “cooperate”
with each other, and the pieces that are obtained when the graph is
simultaneously decomposed by all the separations in the collection “line up”
to form a tree structure.

We remark that most of our arguments work for graphs in the larger class
$\mathcal{C}_{t}$; we will specify the point when we need to make the
assumption that generalized $t$-pyramids are excluded. In the case of graphs
in $\mathcal{C}_{t}$ (as well as some other graph classes addressed in other
papers of this series), there is a natural family of separations to turn to;
they correspond to special vertices of the graph called “hubs,” and are
discussed in Section 3. Unfortunately, these natural separations are very far
from being non-crossing, and therefore we cannot use them in traditional ways
to get tree decompositions. Similarly to [2], we use degeneracy to partition
the set of all hubs (which yields a partition of all the natural separations)
of an $n$-vertex graph $G$ in $\mathcal{C}_{t}$ into collections
$S_{1},\dots,S_{p}$, where each $S_{i}$ is “non-crossing” (this property is
captured in Lemma 4.6), $p\leq C(t)\log n$ (where $C(t)$ only depends on $t$
and works for all $G\in\mathcal{C}_{t}$) and each vertex of $S_{i}$ has at
most $d$ (where $d$ depends on $t$) neighbors in $\bigcup_{j=i}^{p}S_{j}$. Our
main result is that the treewidth of $G$ is bounded by a linear function of
$p+\log n$.

First we will show that graphs in $\mathcal{C}_{t}$ that do not have hubs have
treewidth that is bounded as a function of $t$; thus we may assume that $p>0$.
In fact, we will prove that there exists a constant $k$, depending on $t$,
such that if two non-adjacent vertices $u,v$ of a graph in $\mathcal{C}_{t}$
are joined by $k$ vertex-disjoint paths $P_{1},\dots,P_{k}$, then for at least
one $i\in\\{1,\dots,k\\}$, the neighbor of $v$ in $P_{i}$ is a hub.

We now proceed as follows. Let $m=2d+k$. We first consider a so-called
$m$-lean tree decomposition $(T,\chi)$ of $G$ (discussed in Section 2). By
standard arguments on tree decompositions, we deduce that some bag
$\chi(t_{0})$ of $(T,\chi)$ is in some sense central to the tree
decomposition, and we focus on it. We can then show that all but at most one
vertex of $S_{1}$ has bounded degree in the torso of $\chi(t_{0})$. We would
like to use this fact in order to construct a tree decomposition of the torso
of $\chi(t_{0})$ and then use it to obtain a tree decomposition of $G$.
Unfortunately, the torso of $\chi(t_{0})$ is not a graph in $\mathcal{C}_{t}$.
Instead, we find an induced subgraph of $G$, which we call $\beta$, that
consists of $\chi(t_{0})$ together with a collection of disjoint vertex sets
$Conn(t)$ for $t\in V(T)\setminus\\{t_{0}\\}$, where each $Conn(t)$
“remembers” the component of $G\setminus\chi(t_{0})$ that meets $\chi(t)$.
Moreover, no vertex of $\beta\setminus\chi(t_{0})$ is a hub of $\beta$, and
all but one vertex of $S_{1}$ have bounded degree in $\beta$.

Next, we decompose $\beta$, simultaneously, by all the separations
corresponding to the hubs in $S_{1}$ whose degree in $\beta$ is bounded, and
delete the unique vertex of $S_{1}$ of high degree (if one exists). We denote
the resulting graph by $\beta^{A}(S_{1})$ and call it the “central bag” for
$S_{1}$. The parameter $p$ is smaller for $\beta^{A}(S_{1})$ than it is for
$G$, and so we can use induction to obtain a bound on the treewidth of
$\beta^{A}(S_{1})$. We then start with a special optimal tree decomposition of
$\beta^{A}(S_{1})$, where each bag is a “potential maximal clique” (see
Section 2). Also inductively (this time on the number of vertices) we have
tree decompositions for each component of $\beta\setminus\beta^{A}(S_{1})$.

Now we use the special nature of our “natural separations” and properties of
potential maximal cliques to combine the tree decompositions above into a tree
decomposition of $\beta$, where the size of the bag only grows by an additive
constant.

Then we repeat a similar procedure to combine the tree decomposition of
$\beta$ that we just obtained with tree decompositions of the components of
$G\setminus\chi(t_{0})$ to obtain a tree decomposition of $G$, where again the
size of the bag only grows by an additive constant.

Let us now discuss how we obtain the bound on the growth of a bag. In the
first step of the growing process, we add to each existing bag $B$ the
neighbor sets of the vertices of $S_{1}\cap B$. The number of vertices of
$S_{1}$ in each bag is bounded by Theorem 6.3, because no vertex of $S_{1}$ is
a hub in $\beta^{A}(S_{1})$ (this is proved in Theorem 4.7).

In the second growing step, we first turn the tree decomposition of $\beta$
that we just constructed into a tree decomposition of the same width with the
additional property that every bag is a potential maximal clique of $G$. Next,
for each bag $B$ of this tree decomposition, and for every $t\in N_{T}(t_{0})$
such that $B\cap Conn(t)\neq\emptyset$, we add to $B$ the adhesion
$\chi(t_{0})\cap\chi(t)$. One of the properties of $m$-lean tree
decompositions is that the size of each adhesion is bounded. The number of
adhesions added to a given bag is again bounded by Theorem 6.3 since distinct
sets $Conn(t)$ are pairwise disjoint and anticomplete to each other, and no
vertex of $Conn(t)$ is a hub.

Theorem 6.3 is the only result in the paper that uses the stronger assumption
that generalized $t$-pyramids are excluded.

The paper is organized as follows. In Section 2, we discuss several types of
tree decompositions that we use in this paper. In Section 3, we summarize
results guaranteeing the existence of useful separations. In Section 4, we
discuss the construction of the graphs $\beta$ and $\beta^{A}(S_{1})$, and how
to use their tree decompositions to obtain a tree decomposition of $G$. In
Section 5, we analyze the structure of minimal separators in graphs of
$\mathcal{C}_{t}$. In Section 6.3, we use the results of Section 5 to obtain a
bound on the size of a stable set of non-hubs in a potential maximal clique of
a graph in $\mathcal{C}_{tt}$. Section 7 puts together the results of all the
previous sections to prove Theorem 1.4. Finally, Section 8 discusses
algorithmic consequences of Theorem 1.4.

##  2\. Special tree decompositions and connectivity

In this section we discuss several known results related to connectivity, and
a describe a few special kinds of tree decompositions. Let $G$ be a graph. Let
$X,Y,Z$ be subsets of $V(G)$. By a _path from $Y$ to $Z$_ we mean a path from
some $y\in Y$ to some $z\in Z$. We say that $X$ separates $Y$ from $Z$ (in
$G$) if every path $P$ with an end in $Y$ and an end in $Z$ satisfies $P\cap
X\neq\emptyset$. In this case we also say that $Y$ is separated from $Z$ by
$X$. We start by recalling a classical result of Menger:

######  Theorem 2.1 (Menger [15]).

Let $k\geq 1$ be an integer, let $G$ be a graph and let $X,Y\subseteq V(G)$
with $|X|=|Y|=k$. Then either there exists $M\subseteq V(G)$ with $|M|<k$ such
that $M$ separates $X$ from $Y$, or or there are $k$ pairwise vertex-disjoint
paths in $G$ from $X$ to $Y$.

Theorem 2.1 immediately implies:

######  Theorem 2.2 (Menger [15]).

Let $k\geq 1$ be an integer, let $G$ be a graph and let $u,v\in G$ be distinct
and non-adjacent. Then either there exists a set $M\subseteq
G\setminus\\{u,v\\}$ with $|M|<k$ such that $M$ separates $u$ and $v$ in $G$,
or there are $k$ pairwise internally vertex-disjoint paths in $G$ from $u$ to
$v$.

For a tree $T$ and vertices $t,t^{\prime}\in V(T)$, we denote by
$tTt^{\prime}$ the unique path of $T$ from $t$ to $t^{\prime}$. Let $(T,\chi)$
be a tree decomposition of a graph $G$. For every $x\in V(T)$, the torso at
$x$, denoted by $\hat{\chi}(x)$, is the graph obtained from the bag $\chi(x)$
by, for each $y\in N_{T}(x)$, adding an edge between every two non-adjacent
vertices $u,v\in\chi(x)\cap\chi(y)$. For every $uv\in E(T)$, the adhesion at
$uv$, denoted by $adh(uv)$, is the set $\chi(u)\cap\chi(v)$. We define
$adh(T,\chi)=\max_{uv\in E(T)}|adh(uv)|$.

In the proof of Theorem 1.4, we will use several special kinds of tree
decompositions that we explain now.

###  2.1. Potential Maximal Cliques

For a graph $G$ and a set $F\subseteq\binom{V(G)}{2}\setminus E(G)$, we denote
by $G+F$ the graph obtained from $G$ by making the pairs in $F$ adjacent, that
is, $E(G+F)=E(G)\cup F$. A set $F\subseteq\binom{V(G)}{2}\setminus E(G)$ is a
_chordal fill-in_ of $G$ if $G+F$ is chordal; in this case, $G+F$ is a chordal
completion of $G$. A chordal fill-in (and the corresponding chordal
completion) is _minimal_ if it is inclusion-wise minimal.

Let $X\subseteq V(G)$. The set $X$ is a _minimal separator_ if there exist
$u,v\in V(G)$ such that $u$ and $v$ are in different connected components of
$G\setminus X$, and $u$ and $v$ are in the same connected component of
$G\setminus Y$ for every $Y\subsetneq X$. A component $D$ of $G\setminus X$ is
a _full component_ for $X$ if $N(D)=X$. It is well-known that a set
$X\subseteq V(G)$ is a minimal separator if and only if there are at least two
distinct full components for $X$.

A _potential maximal clique_ (PMC) of a graph $G$ is a set $\Omega\subseteq
V(G)$ such that $\Omega$ is a maximal clique of some minimal chordal
completion $G+F$ of $G$. The following result characterizes PMCs:

######  Theorem 2.3 (Bouchitté and Todinca [9]).

A set $\Omega\subseteq V(G)$ is a PMC of $G$ if and only if:

  1. (1)

for all distinct $x,y\in\Omega$ with $xy\not\in E(G)$, there exists a
component $D$ of $G\setminus\Omega$ such that $x,y\in N(D)$; and

  2. (2)

for every component $D$ of $G\setminus\Omega$ it holds that $N(D)\neq\Omega$
(that is, there are no full components for $\Omega$).

We also need the following result relating PMCs and minimal separators:

######  Theorem 2.4 (Bouchitté and Todinca [9]).

Let $\Omega\subseteq V(G)$ be a PMC of $G$. Then, for every component $D$ of
$G\setminus\Omega$, the set $N(D)$ is a minimal separator of $G$.

We remind the reader of the following well-known property of tree
decompositions:

######  Theorem 2.5 (see Diestel [12]).

Let $G$ be a graph, let $K$ be a clique of $G$, and let $(T,\chi)$ be a tree
decomposition of $G$. Then, there is $v\in V(T)$ such that
$K\subseteq\chi(v)$.

Let us say that a tree decomposition $(T,\chi)$ of a graph $G$ is structured
if $\chi(v)$ is a PMC of $G$ for every $v\in V(T)$. We need the following
well-known result which allows us to turn a tree decomposition into a
structured tree decomposition; we include the proof for completeness.

######  Theorem 2.6.

Let $G$ be a graph and let $(T,\chi)$ be a tree decomposition of $G$. There
exists a structured tree decomposition $(T^{\prime},\chi^{\prime})$ of $G$
such that for every $v^{\prime}\in T^{\prime}$ there exists $v\in T$ with
$\chi^{\prime}(v^{\prime})\subseteq\chi(v)$.

###### Proof.

Let $(T,\chi)$ be a tree decomposition of $G$. It is easy to check that the
graph $G^{\prime}$ obtained from $G$ by adding all edges $xy$ such that
$x,y\in\chi(v)$ for some $v\in V(T)$ is chordal and that $(T,\chi)$ is a tree
decomposition of $G^{\prime}$. It follows that there exists a minimal chordal
fill-in $F$ of $G$ such that $F\subseteq E(G^{\prime})\setminus E(G)$; let
$G^{\prime\prime}=G+F$. In particular, every clique of $G^{\prime\prime}$ is a
subset of a clique of $G^{\prime}$. Since by Theorem 2.5 every clique of
$G^{\prime}$ is contained in a bag $\chi(v)$ for some $v\in V(T)$, it follows
that every clique of $G^{\prime\prime}$ is contained in a bag $\chi(v)$ for
some $v\in T$.

Next, since $G^{\prime\prime}$ is chordal, there is a tree decomposition
$(T^{\prime\prime},\chi^{\prime\prime})$ of $G^{\prime\prime}$ such that
$\chi^{\prime\prime}(v)$ is a clique of $G^{\prime\prime}$ (and therefore a
PMC of $G$) for every $v\in V(T^{\prime\prime})$. Lastly, since $G$ is a
subgraph of $G^{\prime\prime}$, it follows that
$(T^{\prime\prime},\chi^{\prime\prime})$ is a tree decomposition of $G$. This
proves Theorem 2.6. ∎

###  2.2. Lean tree decompositions

Let $k>0$ be an integer. A tree decomposition $(T,\chi)$ is called $k$-lean if
the following hold:

  * •

$adh(T,\chi)<k$; and

  * •

for all $t,t^{\prime}\in V(T)$ and sets $Z\subseteq\chi(t)$ and
$Z^{\prime}\subseteq\chi(t^{\prime})$ with $|Z|=|Z^{\prime}|\leq k$, either
$G$ contains $|Z|$ disjoint paths from $Z$ to $Z^{\prime}$, or some edge
$ss^{\prime}$ of $tTt^{\prime}$ satisfies $|adh(ss^{\prime})|<|Z|$.

For a tree $T$ and an edge $tt^{\prime}$ of $T$, we denote by $T_{t\rightarrow
t^{\prime}}$ the component of $T\setminus t$ containing $t^{\prime}$. Let
$G_{t\rightarrow t^{\prime}}=G[\bigcup_{v\in T_{t\rightarrow
t^{\prime}}}\chi(t)]$. A tree decomposition $(T,\chi)$ is tight if for every
edge $tt^{\prime}\in E(T)$ there is a component $D$ of $G_{t\rightarrow
t^{\prime}}\setminus\chi(t)$ such that $\chi(t)\cap\chi(t^{\prime})\subseteq
N(D)$ (and therefore $\chi(t)\cap\chi(t^{\prime})=N(D)$).

The following definition first appeared in [7]. Given a tree decomposition
$(T,\chi)$ of an $n$-vertex graph $G$, its _fatness_ is the vector
$(a_{n},\dots,a_{0})$ where $a_{i}$ denotes the number of bags of $T$ of size
$i$. A tree decomposition $(T,\chi)$ of $G$ is _$k$ -atomic_ if
$adh(T,\chi)<k$ and the fatness of $(T,\chi)$ is lexicographically minimum
among all tree decompositions of $G$ with adhesion less than $k$. Using
Theorem 2.6, we immediately obtain that every $k$-atomic tree decomposition is
structured.

The following is immediate from the definition:

######  Theorem 2.7.

For every $k>1$, every graph admits a $k$-atomic tree decomposition.

It was observed in [10] that [7] contains a proof of the following:

######  Theorem 2.8 (Bellenbaum and Diestel [7], see Carmesin, Diestel,
Hamann, Hundertmark [10], see also Weißauer [20]).

Every $k$-atomic tree decomposition is $k$-lean.

The same proof also gives the following, which is in fact part of the
definition of $k$-leanness in [10]:

######  Theorem 2.9 (Bellenbaum and Diestel [7], see Carmesin, Diestel,
Hamann, Hundertmark [10], see also Weißauer [20]).

Let $(T,\chi)$ be a $k$-atomic tree decomposition of $G$ and let $tt^{\prime}$
be an edge of $T$. Then both $\chi(t)\setminus\chi(t^{\prime})\neq\emptyset$
and $\chi(t^{\prime})\setminus\chi(t)\neq\emptyset$.

We also need the following:

######  Theorem 2.10 (Weißauer [20]).

Every $k$-atomic tree decomposition is tight.

We also have the following, which can be easily deduced by combining Lemmas 7
and 9 of Weißauer [20] and using Theorem 2.8.

######  Theorem 2.11.

Let $G$ be a graph, let $k\geq 3$ and let $(T,\chi)$ be $k$-atomic tree
decomposition of $G$. Let $t\in V(T)$. If $u,v\in\chi(t)$ have degree at least
$(2k-2)(k-2)$ in $\hat{\chi}(t)$, then $u$ and $v$ are not separated in $G$ by
a set $X\subseteq V(G)\setminus\\{u,v\\}$ of size less than $k$.

Using Theorem 2.2, we deduce:

######  Theorem 2.12.

Let $G$ be a graph, let $k\geq 3$ and let $(T,\chi)$ be $k$-atomic tree
decomposition of $G$. Let $t\in V(T)$. If $u,v\in\chi(t)$ have degree at least
$(2k-2)(k-2)$ in $\hat{\chi}(t)$, then there are $k$ pairwise internally
vertex-disjoint paths in $G$ from $u$ to $v$.

We finish this subsection with a theorem about tight tree decompositions in
theta-free graphs. Note that by Theorem 2.10, the following result applies in
particular to $k$-atomic tree decompositions for every $k$.

A _cutset_ $C\subseteq V(G)$ of $G$ is a (possibly empty) set of vertices such
that $G\setminus C$ is disconnected. A clique cutset is a cutset that is a
clique.

######  Theorem 2.13.

Let $G$ be a theta-free graph and assume that $G$ does not admit a clique
cutset. Let $(T,\chi)$ be a tight tree decomposition of $G$. Then for every
edge $t_{1}t_{2}$ of $T$ the graph $G_{t_{1}\rightarrow
t_{2}}\setminus\chi(t_{1})$ is connected and $N(G_{t_{1}\rightarrow
t_{2}}\setminus\chi(t_{1}))=\chi(t_{1})\cap\chi(t_{2})$. Moreover, if
$t_{0},t_{1},t_{2}\in V(T)$ and $t_{1},t_{2}\in N_{T}(t_{0})$, then
$\chi(t_{0})\cap\chi(t_{1})\neq\chi(t_{0})\cap\chi(t_{2})$.

###### Proof.

Suppose that $G_{t_{1}\rightarrow t_{2}}\setminus\chi(t_{1})$ is not
connected. Then there exists a component $D_{1}$ of $G_{t_{1}\rightarrow
t_{2}}\setminus\chi(t_{1})$ such that $N(D_{1})=\chi(t_{1})\cap\chi(t_{2})$.
Let $D_{0}$ be a component of $G_{t_{1}\rightarrow t_{2}}\setminus\chi(t_{1})$
different from $D_{1}$. Since $(T,\chi)$ is tight, there exists a component
$D_{2}$ of $G_{t_{2}\rightarrow t_{1}}\setminus\chi(t_{2})$ such that
$N(D_{2})=\chi(t_{1})\cap\chi(t_{2})$. Since $N(D_{0})$ is not a clique cutset
in $G$, there exist non-adjacent $x,y\in
N(D_{0})\subseteq\chi(t_{1})\cap\chi(t_{2})$. But now we get a theta with ends
$x,y$ and paths with interiors in $D_{0},D_{1}$ and $D_{2}$, respectively, a
contradiction. This proves that $G_{t_{1}\rightarrow
t_{2}}\setminus\chi(t_{1})$ is connected.

To prove the second assertion, let $t_{1},t_{2}\in N_{T}(t_{0})$ and assume
that $\chi(t_{0})\cap\chi(t_{1})=\chi(t_{0})\cap\chi(t_{2})$. Then, there
exist $v_{0}\in\chi(t_{0})\setminus\chi(t_{2})$ and
$v_{2}\in\chi(t_{2})\setminus\chi(t_{0})$. Since
$\chi(t_{0})\cap\chi(t_{1})=\chi(t_{0})\cap\chi(t_{2})$ and
$\chi(t_{1})\cap\chi(t_{2})\subseteq\chi(t_{0})$, it follows that
$v_{0},v_{2}\not\in\chi(t_{1})$. But then $v_{0}$ and $v_{2}$ belong to
different components of $G_{t_{1}\rightarrow t_{0}}\setminus\chi(t_{1})$,
contrary to the claim of the previous paragraph. This proves Theorem 2.13. ∎

###  2.3. Centers of tree decomposition

We discuss another important feature of tree decompositions that we need. Let
$G$ be an $n$-vertex graph and let $(T,\chi)$ be a tree decomposition of $G$.
A vertex $t_{0}$ of $T$ is a center of $(T,\chi)$ if for every $t^{\prime}\in
N_{T}(t_{0})$ we have $|G_{t_{0}\rightarrow
t^{\prime}}\setminus\chi(t_{0})|\leq\frac{n}{2}$. The following lemma is a
analogous to the standard proof that every tree has a centroid.

######  Theorem 2.14.

Let $(T,\chi)$ be a tree decomposition of a graph $G$. Then $(T,\chi)$ has a
center.

###### Proof.

Write $|V(G)|=n$. Let $D$ be the directed graph obtained from $T$ as follows.
Let $tt^{\prime}$ be an edge of $T$; direct $tt^{\prime}$ from $t$ to
$t^{\prime}$ if $|G_{t\rightarrow t^{\prime}}\setminus\chi(t)|>\frac{n}{2}$.
As $G_{t\rightarrow t^{\prime}}\setminus\chi(t)$ is disjoint from
$G_{t^{\prime}\rightarrow t}\setminus\chi(t^{\prime})$ (because
$G_{t\rightarrow t^{\prime}}\cap G_{t^{\prime}\rightarrow
t}=\chi(t)\cap\chi(t^{\prime})$), this does not prescribe conflicting
orientations for edges of $T$. For each edge whose direction is not determined
by this, direct it arbitrarily.

It follows that $D$ has a sink $t_{0}$. Let $t^{\prime}\in N_{T}(t_{0})$.
Then, because the edge $t_{0}t^{\prime}$ is not directed from $t_{0}$ to
$t^{\prime}$, it follows that $|G_{t_{0}\rightarrow
t^{\prime}}\setminus\chi(t_{0})|\leq\frac{n}{2}$. This proves Theorem 2.14. ∎

###  2.4. Small separators

We conclude this section by proving one more straightforward and well-known
lemma about tree decompositions.

######  Lemma 2.15.

Let $G$ be a graph. Let $X\subseteq V(G)$, and let $D_{1},\dots,D_{s}$ be the
components of $G\setminus X$. Then
$\operatorname{tw}(G)\leq|X|+\max_{i\in\\{1,\dots,s\\}}\operatorname{tw}(D_{i})$.

###### Proof.

For every $i$, we let $(T_{i},\chi_{i})$ be a tree decomposition of $D_{i}$ of
width $\operatorname{tw}(D_{i})$. Let $T$ be a tree obtained from the union of
$T_{1},\dots,T_{s}$ by adding a new vertex $t$ and making $t$ adjacent to
exactly one vertex of each $T_{i}$. We now construct a tree decomposition
$(T,\chi)$ of $G$. Let $\chi(t)=X$, and for every $t^{\prime}\in T\cap T_{i}$
let $\chi(t^{\prime})=\chi_{i}(t)\cup X$. It is easy to check that $(T,\chi)$
is a tree decomposition of $G$, and
$\operatorname{width}(T,\chi)\leq\max_{i\in\\{1,\dots,s\\}}\operatorname{tw}(D_{i})+|X|$.
∎

##  3\. Star cutsets, wheels and blocks

A star cutset in a graph $G$ is a cutset $S\subseteq V(G)$ such that either
$S=\emptyset$ or for some $x\in S$, $S\subseteq N[x]$.

Recall that a _wheel_ $(H,x)$ of $G$ consists of a hole $H$ and a vertex $x$
that has at least three neighbors in $H$. A _sector_ of $(H,x)$ is a path $P$
of $H$ whose ends are distinct and adjacent to $x$, and such that $x$ is
anticomplete to $P^{*}$. A sector $P$ is a _long sector_ if $P^{*}$ is non-
empty. We now define several types of wheels that we will need.

A wheel $(H,x)$ is a _universal wheel_ if $x$ is complete to $H$. A wheel
$(H,x)$ is a _twin wheel_ if $N(x)\cap H$ induces a path of length two. A
wheel $(H,x)$ is a _short pyramid_ if $|N(x)\cap H|=3$ and $x$ has exactly two
adjacent neighbors in $H$. A wheel is _proper_ if it is not a twin wheel or a
short pyramid. We say that $x\in V(G)$ is a wheel center or a hub if there
exists $H$ such that $(H,x)$ is a proper wheel in $G$. We denote by
$\operatorname{Hub}(G)$ the set of all hubs of $G$.

We need the following result, which was observed in [1]:

######  Theorem 3.1 (Abrishami, Chudnovsky, Vušković [1]).

Let $G\in\mathcal{C}$ and let $(H,v)$ be a proper wheel in $G$. Then there is
no component $D$ of $G\setminus N[v]$ such that $H\subseteq N[D]$.

The majority of this paper is devoted to dealing with hubs and star cutsets
arising from them in graphs in $\mathcal{C}$, but in the remainder of this
section we focus on the case when $\operatorname{Hub}(G)=\emptyset$. To do
that, we combine several earlier results from this series.

Let $k$ be a positive integer and let $G$ be a graph. A $k$-block in $G$ is a
set $B$ of at least $k$ vertices in $G$ such that for every
$\\{x,y\\}\subseteq B$, there exists a collection $\mathcal{P}_{\\{x,y\\}}$ of
at least $k$ distinct and pairwise internally vertex-disjoint paths in $G$
from $x$ to $y$. A slight strengthening of the following was proved in [5]:

######  Theorem 3.2 (Abrishami, Alecu, Chudnovsky, Hajebi, Spirkl [5]).

For all integers $k,t\geq 1$, there exists an integer $\beta=\beta(k,t)$ such
that if $G\in\mathcal{C}_{t}$ and $G$ has no $k$-block, then
$\operatorname{tw}(G)\leq\beta(k,t)$.

We also need the following result from [5]:

######  Theorem 3.3.

For all integers $\nu,t\geq 1$, there exists an integer $\psi=\psi(t,\nu)\geq
1$ with the following property. Let $G\in\mathcal{C}_{t}$, let $a,b\in G$ be
distinct and non-adjacent and let $\\{P_{i}:i\in[\psi]\\}$ be a collection of
$\psi$ pairwise internally disjoint paths in $G$ from $a$ to $b$. For each
$i\in[\nu]$, let $a_{i}$ be the neighbor of $a$ in $P_{i}$ (so $a_{i}\neq b$).
Then there exists $I\subseteq[\phi]$ with $|I|=\nu$ for which the following
holds.

  * •

$\\{a_{i}:i\in I\\}\cup\\{b\\}$ is a stable set in $G$.

  * •

For all $i,j\in I$ with $i<j$, $a_{i}$ has a neighbor in
$P_{j}^{*}\setminus\\{a_{j}\\}$.

Additionally, we use a result of [3]:

######  Theorem 3.4 (Abrishami, Alecu, Chudnovsky, Hajebi, Spirkl [3]).

Let $G$ be an even wheel-free graph, let $H$ be a hole of $G$, and let
$v_{1},v_{2}\in V(G)$ be adjacent vertices each with at least two non-adjacent
neighbors in $H$. Then, $v_{1}$ and $v_{2}$ have a common neighbor in $H$.

We also remind the reader the following well-known version of Ramsey’s theorem
[17]:

######  Theorem 3.5.

For all positive integers $a,b,c$ , there is a positive integer $M=M(a,b,c)$
such that if $G$ is a graph with no $K_{a}$ and no induced subgraph isomorphic
to $K_{b,b}$, and $G$ contains a collection $\mathcal{M}$ of $M$ pairwise
disjoint subsets of vertices, each of size at most $a$, then some two members
of $\mathcal{M}$ are anticomplete to each other.

Next we show:

######  Theorem 3.6.

For every integer $t\geq 1$ there exists an integer $k=k(t)$ such that if
$G\in\mathcal{C}_{t}$ and $x,y\in V(G)$ are non-adjacent and
$N(x)\cap\operatorname{Hub}(G)=\emptyset$, then there do not exist $k$
pairwise internally vertex-disjoint paths in $G$ from $x$ to $y$.

###### Proof.

Let $M=M(2,t,2)$ be as in Theorem 3.5 and let $\nu=\psi(\psi(M,t),t)$ be as in
Theorem 3.3. Let $k=\psi(6\nu+3,t)$ be as in Theorem 3.3, and suppose that
there are $k$ vertex disjoint paths from $x$ to $y$ in $G$. Let $I$ be as in
the conclusion of Theorem 3.3 applied with $a=x$ and $b=y$; renumbering the
paths if necessary we may assume that $I=\\{1,\dots,6\nu+3\\}$. Then each of
$a_{1},a_{2},a_{3}$ has a neighbor in each of the paths
$P_{4},\dots,P_{6\nu+3}$. For $i\geq 4$, let $Q_{i}$ be a minimal subpath of
$P_{i}$ such that all of $a_{1},a_{2},a_{3}$ have neighbors in $Q_{i}$; let
$l_{i}$ and $r_{i}$ be the ends of $Q_{i}$. By the minimality of $Q_{i}$, for
every $i$ there exist distinct $s,r\in\\{a_{1},a_{2},a_{3}\\}$ such that
$l_{i}$ is the unique neighbor of $s$ in $Q_{i}$, and $r_{i}$ is the unique
neighbor of $r$ in $Q_{i}$. By permuting $a_{1}$, $a_{2}$ and $a_{3}$ if
necessary, we may assume that there exists $J\subseteq\\{4,\dots,6\nu+3\\}$
with $|J|=\nu$ such that for every $i\in J$, $l_{i}$ is the unique neighbor of
$a_{1}$ in $Q_{i}$, and $r_{i}$ is the unique neighbor of $a_{3}$ in $Q_{i}$.
Renumbering $a_{4},\dots a_{6\nu}+3$ we write $J=\\{4,\dots,\nu+3\\}$. For
every $i\in J$ let $H_{i}$ be the hole
$a_{1}\hbox{-}l_{i}\hbox{-}Q_{i}\hbox{-}r_{i}\hbox{-}a_{3}\hbox{-}x\hbox{-}a_{1}$.
Since $(H_{i},a_{2})$ is not a proper wheel (recall that
$N(x)\cap\operatorname{Hub}(G)=\emptyset$), and since $H_{i}\cup a_{2}$ is not
a theta, it follows that $a_{2}$ has exactly two neighbors $x_{i},y_{i}$ in
$Q_{i}$ and they are adjacent. We may assume that $Q_{i}$ traverses
$l_{i},x_{i},y_{i},r_{i}$ in this order.

We now apply Theorem 3.3 again to the paths
$a_{1}\hbox{-}l_{i}\hbox{-}Q_{i}\hbox{-}x_{i}\hbox{-}a_{2}$ (with
$i\in\\{4,\dots,\nu+3\\}$) from $a_{1}$ to $a_{2}$ with $a=a_{2}$ and
$b=a_{1}$. Let $K$ be the set of indices as in the conclusion of the theorem,
so $|K|=\psi(M,t)$. Now apply Theorem 3.3 for the third time, to the paths
$a_{3}\hbox{-}r_{i}\hbox{-}Q_{i}\hbox{-}y_{i}\hbox{-}a_{2}$ (with $i\in K$)
from $a_{2}$ to $a_{3}$ with $a=a_{2}$ and $b=a_{3}$. Let $L$ be the set of
indices as in the conclusion of the theorem. Since $G\in\mathcal{C}_{t}$,
applying Theorem 3.5 to the collections
$\mathcal{M}=\\{\\{x_{i},y_{i}\\}\;:\;i\in L\\}$ we deduce that there exist
two values $i<j\in L$ such that

  * •

$\\{x_{i},y_{i}\\}$ is anticomplete to $\\{x_{j},y_{j}\\}$, and

  * •

$x_{i}$ has a neighbor in $l_{j}\hbox{-}Q_{j}\hbox{-}x_{j}$, and

  * •

$y_{i}$ has a neighbor in $y_{j}\hbox{-}Q_{j}\hbox{-}r_{j}$.

We claim that $x_{i}$ has exactly two neighbors in $Q_{j}$ and they are
adjacent. Suppose first that $x_{i}$ has a unique neighbor $u$ in $Q_{j}$.
Then $u\in l_{j}\hbox{-}Q_{j}\hbox{-}x_{j}$, and the hole
$l_{j}\hbox{-}Q_{j}\hbox{-}x_{j}\hbox{-}a_{2}\hbox{-}x\hbox{-}a_{1}\hbox{-}l_{j}$
together with $x_{i}$ is a theta with ends $a_{2},u$, a contradiction. Next
suppose that $x_{i}$ has at least two non-adjacent neighbors in $Q_{j}$. Then
by Theorem 3.4 applied to $H_{j}$, $a_{2}$ and $x_{i}$, it follows that
$a_{2}$ and $x_{i}$ have a common neighbor in $H_{j}$, and therefore $x_{i}$
is adjacent to one of $x_{j},y_{j}$, a contradiction. We deduce that $x_{i}$
has exactly two neighbors $p_{j},q_{j}$ in $Q_{j}$ and they are adjacent.
Since $x_{i}$ is non-adjacent to $x_{j}$ and has a neighbor in
$l_{j}\hbox{-}Q_{j}\hbox{-}x_{j}$, it follows that $p_{j},q_{j}\in
l_{j}\hbox{-}Q_{j}\hbox{-}x_{j}$. Similarly $y_{i}$ has exactly two neighbors
$s_{j},t_{j}$ in $Q_{j}$, $s_{j}$ is adjacent to $t_{j}$, and $s_{j},t_{j}\in
y_{j}\hbox{-}Q_{j}\hbox{-}r_{j}$. We may assume that $Q_{j}$ traverses
$l_{j},p_{j},q_{j},x_{j},y_{j},s_{j},t_{j},r_{j}$ in this order (possibly
$l_{j}=p_{j}$ or $t_{j}=r_{j}$). But now we get a prism with triangles
$x_{i}p_{j}q_{j}$ and $y_{i}t_{j}s_{j}$ and paths $x_{i}\hbox{-}y_{i}$,
$q_{j}\hbox{-}Q_{j}\hbox{-}s_{j}$ and
$p_{j}\hbox{-}Q_{j}\hbox{-}l_{j}\hbox{-}a_{1}\hbox{-}x\hbox{-}a_{3}\hbox{-}r_{j}\hbox{-}Q_{j}\hbox{-}t_{j}$,
a contradiction. This proves Theorem 3.6. ∎

From Theorems 3.2 and 3.6 we deduce:

######  Theorem 3.7.

For every integer $t$, there exists an integer $\gamma=\gamma(t)$ such that
every $G\in\mathcal{C}_{t}$ with $\operatorname{Hub}(G)=\emptyset$ satisfies
$\operatorname{tw}(G)\leq\gamma$.

##  4\. Stable sets of safe hubs

Let $c\in[0,1]$. A set $X\subseteq V(G)$ is a $c$-balanced separator if
$|D|\leq c|V(G)|$ for every component $D$ of $G\setminus X$. The set $X$ is a
balanced separator if $X$ is a $\frac{1}{2}$-balanced separator.

Let $t,d$ be integers. We make the following assumptions throughout this
section. Let $G\in\mathcal{C}_{t}$ with $|V(G)|=n$. Let $m=k+2d$ where
$k=k(t)$ is as in Theorem 3.6, and assume that $G$ does not have a balanced
separator of size less than $m$. Let $(T,\chi)$ be an $m$-atomic tree
decomposition of $G$. We say that a vertex $v$ is $d$-safe if
$|N(v)\cap\operatorname{Hub}(G)|\leq d$.

By Theorems 2.8 and 2.10, we have that $(T,\chi)$ is tight and $m$-lean. By
Theorem 2.14, there exists $t_{0}\in T$ such that $t_{0}$ is a center for $T$.
A vertex $v\in V(G)$ is $t_{0}$-cooperative if either $v\not\in\chi(t_{0})$,
or $\deg_{\hat{\chi}(t_{0})}(v)<2m(m-1)$. We show that $t_{0}$-cooperative
vertices have the following important property.

######  Lemma 4.1.

If $u,v\in\chi(t_{0})$ are $d$-safe and not $t_{0}$-cooperative, then $u$ is
adjacent to $v$.

###### Proof.

Since $u,v$ are not $t_{0}$-cooperative, it follows that both $u,v$ have
degree at least $2m(m-1)$ in $\hat{\chi}(t_{0})$. Since $(T,\chi)$ is an
$m$-atomic tree decomposition, Theorem 2.12 implies that there are $m$
pairwise internally disjoint paths in $G$ from $u$ to $v$. Let $Y=(N(u)\cup
N(v))\cap\operatorname{Hub}(G)$ and let $G^{\prime}=G\setminus Y$. Then
$|Y|\leq 2d$, and so in $G^{\prime}$ there are $k$ pairwise internally vertex
disjoint paths from $u$ to $v$. But
$N_{G^{\prime}}(u)\cap\operatorname{Hub}(G^{\prime})=N_{G^{\prime}}(v)\cap\operatorname{Hub}(G^{\prime})=\emptyset$,
contrary to Theorem 3.6. This proves Lemma 4.1. ∎

In the theory of tree decompositions, working with the torso of a bag is a
natural way to focus on the bag while still keeping track of its relation to
the rest of the graph. Unfortunately, taking torsos is not an operation closed
under induced subgraphs, and so this method does not work when general
hereditary classes are considered. The goal of the next theorem is to design a
tool that will allow us to construct a safe alternative to torsos.

######  Theorem 4.2.

Assume that $G$ does not admit a clique cutset. For every $t\in N_{T}(t_{0})$,
there exists $Conn(t)\subseteq G_{t_{0}\rightarrow t}$ such that

  1. (1)

We have $\chi(t)\cap\chi(t_{0})\subseteq Conn(t)$.

  2. (2)

$Conn(t)\setminus\chi(t_{0})$ is connected and
$N(Conn(t)\setminus\chi(t_{0}))=\chi(t_{0})\cap\chi(t)$.

  3. (3)

No vertex of $Conn(t)\setminus\chi(t_{0})$ is a hub in the graph $(G\setminus
G_{t_{0}\rightarrow t})\cup Conn(t)$.

###### Proof.

Write $\chi(t_{0})\cap\chi(t)=M$. Let $K$ be a minimal connected subgraph of
$G_{t_{0}\rightarrow t}\setminus\chi(t_{0})$ such that
$\chi(t_{0})\cap\chi(t)\subseteq N(K)$ (such $K$ exists by Theorem 2.13). Let
$M=\\{m_{1},\dots,m_{s}\\}$. Since $G$ does not admit a clique cutset, we have
that $s\geq 2$.

(1) _No vertex of $K$ is a hub of $(G\setminus G_{t_{0}\rightarrow
t})\cup(K\cup M)$._

Let $v\in K$ and let $(H,v)$ be a proper wheel in $G^{\prime}=(G\setminus
G_{t_{0}\rightarrow t})\cup(K\cup M)$. Then $(H,v)$ is a proper wheel in $G$.
Since $v\in K$, it follows that $N_{G}(v)\subseteq G_{t_{0}\rightarrow t}$. By
Theorem 2.13, $G\setminus G_{t_{0}\rightarrow t}$ is connected, and since
$(T,\chi)$ is tight, every vertex of $M$ has a neighbor in $G\setminus
G_{t_{0}\rightarrow t}$. It follows that $G\setminus G_{t_{0}\rightarrow t}$
is contained in a component $D$ of $G\setminus N[v]$, and $M\subseteq
N_{G}[D]$. Theorem 3.1 implies that $H\not\subseteq N_{G}[D]$. Since
$H\subseteq G^{\prime}\setminus\\{v\\}=(G\setminus G_{t_{0}\rightarrow t})\cup
M\cup(K\setminus\\{v\\})\subseteq N_{G}[D]\cup(K\setminus\\{v\\})$, it follows
that $H$ contains a vertex in $(K\setminus\\{v\\})\setminus N_{G}[D]$. Let
$K^{\prime}=\\{v\\}\cup(K\cap N_{G}[D])$. Then $K^{\prime}\subsetneq K$, and
so from the minimality of $K$, it follows that either $K^{\prime}$ is not
connected, or $M\not\subseteq N(K^{\prime})$. Suppose first that the latter
happens. Then there is an $m_{i}\in M\setminus N(K^{\prime})$. It follows that
$m_{i}\not\in N(v)$ as $v\in K^{\prime}$, and therefore $m_{i}\in D$. Let $k$
be a neighbor of $m_{i}$ in $K$. Then $k\in N[D]$, and so $k\in K^{\prime}$, a
contradiction; this shows that $M\subseteq N(K^{\prime})$. It follows that
$K^{\prime}$ is not connected. Since $K$ is connected, it follows that for
every $x\in K$, there is a path $P_{x}$ from $x$ to $v$ with $P_{x}\subseteq
K$. Moreover, since $D$ is a component of $G\setminus N[v]$, if $x\in N[D]$,
then $P_{x}\subseteq(N[D]\cap K)\cup\\{v\\}$. Therefore, for every $x\in
K^{\prime}$, we have $P_{x}\subseteq K^{\prime}$; so $K^{\prime}$ is
connected. This is a contradiction and proves (4).

Setting $Conn(t)=K\cup M$, Theorem 4.2 follows. ∎

We now construct a graph that is a safe alternative for $\hat{\chi}(t_{0})$.
Let $S^{\prime}$ be a stable set of hubs of $G$, and assume that every $s\in
S^{\prime}$ is $d$-safe. Let $S_{bad}$ denote the set of all vertices in
$S^{\prime}$ that are not $t_{0}$-cooperative; by Lemma 4.1, we have that
$|S_{bad}|\leq 1$. Let $S=S^{\prime}\setminus S_{bad}$ and set

$\beta(S^{\prime})=\left(\chi(t_{0})\cup\bigcup_{t\in
N_{T}(t_{0})}Conn(t)\right)\setminus S_{bad}.$

Write $\beta=\beta(S^{\prime})$. It follows that for every $t\in
N_{T}(t_{0})$, we have that $\beta\subseteq(G\setminus G_{t_{0}\rightarrow
t})\cup Conn(t)$.

From now on, assume that $\beta$ does not admit a balanced separator of size
at most $2m(m-1)+\gamma(t)+1$ where $\gamma(t)$ is as in Theorem 3.7. Let us
say that a vertex $v$ is unbalanced if there is a component $D$ of
$\beta\setminus N[v]$ such that $|D|>\frac{|\beta|}{2}$.

######  Lemma 4.3.

Suppose that $G$ does not admit a clique cutset and let $s\in
S\cap\chi(t_{0})$. Then the following hold.

  1. (1)

$|N_{\hat{\chi}(t_{0})}(s)|<2m(m-1)$.

  2. (2)

$|N_{\chi(t_{0})}(s)|<2m(m-1)$.

  3. (3)

The vertex $s$ is unbalanced (in $\beta$).

###### Proof.

Let $s\in S$. Since $s$ is $t_{0}$-cooperative, we have that
$|N_{\hat{\chi}(t_{0})}(s)|<2m(m-1)$, and the first assertion of the theorem
holds. Since $\chi(t_{0})$ is a subgraph of $\hat{\chi}(t_{0})$, the second
assertion follows immediately from the first.

We now prove the third assertion. Let $\delta(s)$ be the set of all vertices
$t\in N_{T}(t_{0})$ such that $s\in\chi(t_{0})\cap\chi(t)$. Write
$\Delta(s)=N_{\chi(t_{0})}(s)\cup\bigcup_{t\in\delta(s)}(\chi(t)\cap\chi(t_{0}))$.
Since $\Delta(s)\subseteq N_{\hat{\chi}(t_{0})}[s]$, by the first assertion of
the theorem, we have that $|\Delta(s)|\leq 2m(m-1)$. Since $\beta$ does not
admit a $2m(m-1)$-balanced separator, it follows that there is a component
$D^{\prime}$ of $\beta\setminus\Delta(s)$ with
$|D^{\prime}|>\frac{|\beta|}{2}$.

(2) _We have that $D^{\prime}\cap Conn(t)=\emptyset$ for every
$t\in\delta(s)$._

Suppose not, and let $t\in\delta(s)$ be such that $D^{\prime}\cap
Conn(t)\neq\emptyset$. Since $D^{\prime}$ is a component of
$\beta\setminus\Delta(s)$, it follows that
$D^{\prime}=Conn(t)\setminus\chi(t_{0})$. By Theorem 4.2(3), we have that
$\operatorname{Hub}(D^{\prime})=\emptyset$. Now by Theorem 3.7, we conclude
that $D^{\prime}$ has a balanced separator $X$ of size $\gamma(t)+1$. But now
$X\cup\Delta(s)$ is a balanced separator of $\beta$ of size
$2m(m-1)+\gamma(t)+1$, a contradiction. This proves (4).

Since $N_{\beta}(s)\setminus\Delta(s)\subseteq\bigcup_{t\in\delta(s)}Conn(t)$,
statement (4) implies that $D^{\prime}\cap N_{\beta}(s)=\emptyset$. Let $D$ be
a component of $\beta\setminus N_{\beta}[s]$ such that $D^{\prime}\subseteq
D$; then $|D|>\frac{|\beta|}{2}$, as required. This proves that $s$ is
unbalanced and completes the proof of Lemma 4.3. ∎

As we mentioned in Section 1, handling balanced vertices was somewhat
technical in [2]; it required constructing an artificial auxiliary graph.
Using leanness provides a much more natural framework to deal with this
obstacle.

A separation of a graph $G$ is a triple $(Y,X,Z)$ of pairwise disjoint subsets
of $V(G)$ with $X\cup Y\cup Z=V(G)$ such that $Y$ is anticomplete to $Z$. As
in earlier papers in this series, we associate a certain unique star
separation to every vertex of $S\cap\chi(t_{0})$. For $v\in S\cap\chi(t_{0})$,
let $B(v)$ be the unique component of $\beta\setminus N[v]$ with
$|B(v)|>\frac{|\beta|}{2}$, let $C(v)=N(B(v))\cup\\{v\\}$, and finally, let
$A(v)=\beta\setminus(B(v)\cup C(v))$. Then $(A(v),C(v),B(v))$ is the canonical
star separation of $\beta$ corresponding to $v$. We show:

######  Lemma 4.4.

The vertex $v$ is not a hub of $\beta\setminus A(v)$.

###### Proof.

Suppose that $(H,v)$ is a proper wheel in $\beta\setminus A(v)$. Then
$H\subseteq N[B(v)]$, contrary to Theorem 3.1. This proves Lemma 4.4. ∎

Let $\mathcal{O}$ be a linear order on $S\cap\chi(t_{0})$. Following [2], we
say that two unbalanced vertices of $S\cap\chi(t_{0})$ are star twins if
$B(u)=B(v)$, $C(u)\setminus\\{u\\}=C(v)\setminus\\{v\\}$, and
$A(u)\cup\\{u\\}=A(v)\cup\\{v\\}$. (Note that every two of these conditions
imply the third.)

Let $\leq_{A}$ be a relation on $S\cap\chi(t_{0})$ defined as follows:

$\hskip 71.13188ptx\leq_{A}y\ \ \ \text{ if}\ \ \ \begin{cases}x=y,\text{
or}\\\ \text{$x$ and $y$ are star twins and $\mathcal{O}(x)<\mathcal{O}(y)$,
or}\\\ \text{$x$ and $y$ are not star twins and }y\in A(x).\\\ \end{cases}$

Note that if $x\leq_{A}y$, then either $x=y$, or $y\in A(x).$ We need the
following result from [2]:

######  Lemma 4.5 (Abrishami, Chudnovsky, Hajebi, Spirkl [2]).

The relation $\leq_{A}$ is a partial order on $S\cap\chi(t_{0})$.

In view of Lemma 4.5, let $\operatorname{Core}(S^{\prime})$ be the set of all
$\leq_{A}$-minimal elements of $S\cap\chi(t_{0})$. Define

$\beta^{A}(S^{\prime})=\bigcap_{v\in\operatorname{Core}(S^{\prime})}(B(v)\cup
C(v)).$

The following was also proved in [2]:

######  Lemma 4.6 (Abrishami, Chudnovsky, Hajebi, Spirkl [2]).

Let $u,v\in\operatorname{Core}(S^{\prime})$. Then $A(u)\cap C(v)=C(u)\cap
A(v)=\emptyset$.

Next, we need an analogue of a result of [2], summarizing the behavior of
$\beta^{A}(S^{\prime})$.

######  Theorem 4.7.

The following hold:

  1. (1)

For every $v\in\operatorname{Core}(S^{\prime})$, we have
$C(v)\subseteq\beta^{A}(S^{\prime})$.

  2. (2)

$|C(v)\cap\chi(t_{0})|\leq 2m(m-1)$ for every
$v\in\operatorname{Core}(S^{\prime})$.

  3. (3)

For every component $D$ of $\beta\setminus\beta^{A}(S^{\prime})$, there exists
$v\in\operatorname{Core}(S^{\prime})$ such that $D\subseteq A(v)$. Further, if
$D$ is a component of $\beta\setminus\beta^{A}(S^{\prime})$ and
$v\in\operatorname{Core}(S^{\prime})$ such that $D\subseteq A(v)$, then
$N_{\beta}(D)\subseteq C(v)$.

  4. (4)

$S^{\prime}\cap\operatorname{Hub}(\beta^{A}(S^{\prime}))=\emptyset$.

###### Proof.

(1) is immediate from Lemma 4.6, and (2) follows from Lemma 4.3.

Next we prove (3). Let $D$ be a component of
$\beta\setminus\beta^{A}(S^{\prime})$. Since
$\beta\setminus\beta^{A}(S^{\prime})=\bigcup_{v\in\operatorname{Core}(S^{\prime})}A(v)$,
there exists $v\in\operatorname{Core}(S^{\prime})$ such that $D\cap
A(v)\neq\emptyset$. If $D\setminus A(v)\neq\emptyset$, then, since $D$ is
connected, it follows that $D\cap N(A(v))\neq\emptyset$; but then $D\cap
C(v)\neq\emptyset$, contrary to (1). Since
$N_{\beta}(D)\subseteq\beta^{A}(S^{\prime})$ and $N(D)\subseteq A(v)\cup
C(v)$, it follows that $N_{\beta}(D)\subseteq C(v)$. This proves (3).

To prove (4), let $u\in
S^{\prime}\cap\operatorname{Hub}(\beta^{A}(S^{\prime}))$. By Theorem 4.2(3),
we have that $u\in\chi(t_{0})$. Since $\beta^{A}(S^{\prime})\subseteq\beta$,
we deduce that $u\not\in S_{bad}$. By Lemma 4.4, it follows that
$\beta^{A}(S^{\prime})\not\subseteq B(u)\cup C(u)$, and therefore
$u\not\in\operatorname{Core}(S^{\prime})$. But then $u\in A(v)$ for some
$v\in\operatorname{Core}(S^{\prime})$, and so $u\not\in\beta^{A}(S^{\prime})$,
a contradiction. This proves (4) and completes the proof of Theorem 4.7. ∎

In the course of the proof of Theorem 1.4, we will inductively obtain a bound
on $\operatorname{tw}(\beta^{A}(S))$. Next we explain how to transform a tree
decomposition of $\beta^{A}(S^{\prime})$ into a tree decomposition of $\beta$.

Let $D_{1},\dots,D_{s}$ be the components of
$\beta\setminus\beta^{A}(S^{\prime})$. For $i\in\\{1,\dots,s\\}$, let
$r(D_{i})$ be the $\mathcal{O}$-minimal vertex of
$\operatorname{Core}(S^{\prime})$ such that $D_{i}\subseteq A(v)$ (such $v$
exists by Theorem 4.7(3)). Write $\beta_{0}=\chi(t_{0})$.

Let $(T_{0},\chi_{0})$ be a tree decomposition of $\beta^{A}(S^{\prime})$, and
for $i\in\\{1,\dots,s\\}$ let $(T_{i},\chi_{i})$ be a tree decomposition of
$D_{i}$. Let $T_{\beta}$ be the tree obtained from the union of
$T_{0},T_{1},\dots,T_{s}$ as follows. Let $i\in\\{1,\dots,s\\}$. Choose $t\in
T_{0}$ such that $r(D_{i})\in\chi_{0}(t)$ and add an edge from $t$ to an
arbitrarily chosen vertex of $T_{i}$. For $u\in T_{\beta}$, let
$\chi_{\beta}(u)$ be defined as follows.

  * •

If $u\in V(T_{0})$, let

$\chi_{\beta}(u)=\chi_{0}(u)\cup\bigcup_{v\in\operatorname{Core}(S^{\prime})\cap\chi_{0}(u)}C(v).$

  * •

If $u\in V(T_{i})$ for $i\in\\{1,\dots,s\\}$, let

$\chi_{\beta}(u)=\chi_{i}(u)\cup C(r(D_{i})).$

######  Theorem 4.8.

With the notation as above, $(T_{\beta},\chi_{\beta})$ is a tree decomposition
of $\beta$. Moreover,

  * •

for every $t\in T_{0}$,

$|\chi_{\beta}(t)\cap\beta_{0}|\leq|\chi_{0}(t)|+2m(m-1)(|\chi_{0}(t)\cap\operatorname{Core}(S^{\prime})|),$

and

  * •

for every $i\in\\{1,\dots,s\\}$ and $t\in T_{i}$,

$|\chi_{\beta}(t)\cap\beta_{0}|\leq|\chi_{i}(t)|+2m(m-1).$

###### Proof.

The fact that $(T_{\beta},\chi_{\beta})$ is a tree decomposition of $\beta$
follows from Theorem 6.6 of [2]. Recall that by Lemma 4.3, $|(C(v)\setminus
v)\cap\beta_{0}|<2m(m-1)$ for every $s\in\operatorname{Core}(S^{\prime})$. Now
the theorem follows directly from the definition of
$(T_{\beta},\chi_{\beta})$. ∎

We finish this section with a theorem that allows us to transform a tree
decomposition of $\beta$ into a tree decomposition of $G$.

Write $N_{T}(t_{0})=\\{t_{1},\dots,t_{r}\\}$, and let
$D_{i}^{\prime}=G_{t_{0}\rightarrow t_{i}}\setminus\chi(t_{0})$ for
$i\in\\{1,\dots,r\\}.$

Let $(T_{0}^{\prime},\chi_{0}^{\prime})$ be a tree decomposition of $\beta$,
and for $i\in\\{1,\dots,r\\}$ let $(T_{i}^{\prime},\chi_{i}^{\prime})$ be a
tree decomposition of $D_{i}^{\prime}$. Let $U$ be the tree obtained from the
union of $T_{0}^{\prime},T_{1}^{\prime},\dots,T_{r}^{\prime}$ as follows. Let
$i\in\\{1,\dots,r\\}$. Choose $t\in T_{0}^{\prime}$ such that
$\chi_{0}^{\prime}(t)\cap(Conn(t_{i})\setminus\chi(t_{0}))\neq\emptyset$ and
add an edge from $t$ to an arbitrarily chosen vertex of $T_{i}^{\prime}$.

For $u\in U$, let $\psi(u)$ be defined as follows.

  * •

If $u\in V(T_{0}^{\prime})$, let

$\psi(u)=S_{bad}\cup(\chi_{0}^{\prime}(u)\cap\beta_{0})\cup\bigcup_{t_{i}\text{
s.t.
}\chi_{0}^{\prime}(u)\cap(Conn(t_{i})\setminus\chi(t_{0}))\neq\emptyset}(\beta_{0}\cap\chi(t_{i})).$

  * •

If $u\in V(T_{i}^{\prime})$ for $i\in\\{1,\dots,r\\}$, let

$\psi(u)=S_{bad}\cup\chi_{i}^{\prime}(u)\cup(\beta_{0}\cap\chi(t_{i})).$

######  Theorem 4.9.

With the notation as above, $(U,\psi)$ is a tree decomposition of $G$.

###### Proof.

Since $U$ is obtained by adding a single edge from $T_{0}^{\prime}$ to each of
the trees $T_{1}^{\prime},\dots,T_{r}^{\prime}$, it follows that $U$ is a
tree. Clearly, every vertex of $G$ is in $\psi(v)$ for some $v\in V(U)$. Next
we check that for every edge $xy$ of $G$, there exists $v\in V(U)$ such that
$x,y\in\psi(v)$. This is clear if $x,y\in\chi(t_{0})$ or if $x,y\in
D_{i}^{\prime}$ for some $i$; thus we may assume that $x\in\chi(t_{0})$ and
$y\in D_{1}^{\prime}$, say. Since $(T,\chi)$ is a tree decomposition of $G$,
it follows that $x\in\chi(t_{0})\cap\chi(t_{1})$. Let $v\in V(T_{1}^{\prime})$
such that $y\in\chi_{1}^{\prime}(v)\subseteq\psi(v)$; then $x,y\in\psi(v)$ as
required.

Let $x\in V(G)$. For $i\in\\{0,1,\dots,r\\}$, define $F_{i}(x)=\\{v\in
V(T_{i}^{\prime})\text{ such that }x\in\psi(v)\\}$. Let
$F(x)=\bigcup_{i=0}^{r}F_{i}(x)$. We need to show that for every $x\in V(G)$,
the induced subgraph $U[F(x)]$ is connected. This is true if $x\in S_{bad}$,
since then $F(x)=V(U)$. Therefore, we now assume that $x\not\in S_{bad}$. If
$x\not\in\beta_{0}$, then $F_{0}(x)=\emptyset$, and there exists a unique $i$
such that $x\in D_{i}^{\prime}$; therefore $F(x)=F_{i}(x)$, and $U[F(x)]$ is
connected because $T_{i}^{\prime}[F_{i}(x)]$ is connected. Thus we may assume
that $x\in\beta_{0}$. Let $I\subseteq\\{1,\dots,r\\}$ be the set of all $i$
such that $x\in\chi(t_{0})\cap\chi(t_{i})$. It follows that
$F_{i}(x)=\emptyset$ for all $i\in\\{1,\dots,r\\}\setminus I$, and
$F_{i}(x)=V(T_{i}^{\prime})$ for all $i\in I$.

First we show that for every $i\in I$, there is an edge between
$T_{i}^{\prime}[F_{i}(x)]=T_{i}^{\prime}$ and $T_{0}^{\prime}[F_{0}(x)]$. Let
$i\in I$; and let $v\in T_{0}^{\prime}$ be such that $v$ is adjacent to a
vertex of $T_{i}^{\prime}$. Then
$(Conn(t_{i})\setminus\chi(t_{0}))\cap\chi_{0}^{\prime}(v)\neq\emptyset$;
consequently $\chi(t_{0})\cap\chi(t_{i})\subseteq\psi(v)$, and therefore,
$x\in\psi(v)$. Thus there is an edge between $T_{i}^{\prime}[F_{i}(x)]$ and
$T_{0}^{\prime}[F_{0}(x)]$, as required.

Now to show that $U[F(x)]$ is connected, it is enough to prove that
$T_{0}^{\prime}[F_{0}(x)]$ is connected. Write
$\chi_{0}^{\prime-1}(x):=\\{v\in T^{\prime}_{0}:x\in\chi_{0}^{\prime}(v)\\}$
and observe that

$F_{0}(x)=\chi_{0}^{\prime-1}(x)\cup\bigcup_{t\in
I}\chi_{0}^{\prime-1}(Conn(t)\setminus\chi(t_{0})).$

Since by Theorem 4.2(2), we have that
$\\{x\\}\cup(Conn(t)\setminus\chi(t_{0}))$ is connected, it follows from basic
properties of a tree decomposition that
$T_{0}^{\prime}[\chi_{0}^{\prime-1}(\\{x\\}\cup(Conn(t)\setminus\chi(t_{0})))]$
is connected. Since $\chi_{0}^{\prime-1}(\\{x\\})\neq\emptyset$, it follows
that the union $T_{0}^{\prime}\left[\bigcup_{t\in
I}\chi_{0}^{\prime-1}(\\{x\\}\cup(Conn(t)\setminus\chi(t_{0})))\right]$ is
connected. We deduce that $T_{0}^{\prime}[F_{0}(x)]$ is connected, as
required. This proves Theorem 4.9.

∎

##  5\. Connectifiers revisited

We start by recalling a well known theorem of Erdős and Szekeres [13].

######  Theorem 5.1 (Erdős and Szekeres [13]).

Let $x_{1},\dots,x_{n^{2}+1}$ be a sequence of distinct reals. Then there
exists either an increasing or a decreasing $(n+1)$-sub-sequence.

We will also need the following easy lemma, whose proof we include for
completeness.

######  Lemma 5.2.

Let $k$ be an integer and let $D$ be a directed graph in which every vertex
has at most $k$ outneighbors. Let $D^{-}$ be the underlying undirected graph
of $D$. Then there exists $X\subseteq V(D)$ with $|X|\geq\frac{|V(D)|}{2k+1}$
such that $X$ is a stable set of $D^{-}$.

###### Proof.

Every induced subgraph $H$ of $D^{-}$ has at most $k|V(H)|$ edges, and
therefore contains a vertex of degree at most $2k$. This shows that $D^{-}$ is
$2k$-degenerate, and therefore $(2k+1)$-colorable. So $D^{-}$ has a stable set
of size at least $|V(D)|/(2k+1)$. This proves Lemma 5.2. ∎

A vertex $v$ in a graph $G$ is said to be a branch vertex if $v$ has degree
more than two. By a caterpillar we mean a tree $C$ with maximum degree three
such that there exists a path $P$ of $C$ where all branch vertices of $C$
belong to $P$. We call a maximal such path $P$ the spine of $P$. (Our
definition of a caterpillar is non-standard for two reasons: a caterpillar is
often allowed to be of arbitrary maximum degree, and a spine often contains
all vertices of degree more than one.) By a subdivided star we mean a graph
isomorphic to a subdivision of the complete bipartite graph $K_{1,\delta}$ for
some $\delta\geq 3$. In other words, a subdivided star is a tree with exactly
one branch vertex, which we call its root. For a graph $H$, a vertex $v$ of
$H$ is said to be simplicial if $N_{H}(v)$ is a clique. We denote by
$\mathcal{Z}(H)$ the set of all simplicial vertices of $H$. Note that for
every tree $T$, $\mathcal{Z}(T)$ is the set of all leaves of $T$. An edge $e$
of a tree $T$ is said to be a leaf-edge of $T$ if $e$ is incident with a leaf
of $T$. It follows that if $H$ is the line graph of a tree $T$, then
$\mathcal{Z}(H)$ is the set of all vertices in $H$ corresponding to the leaf-
edges of $T$. The following is proved in [4] based on (and refining) a result
from [11].

######  Theorem 5.3 (Abrishami, Alecu, Chudnovsky, Hajebi, Spirkl [4]).

For every integer $h\geq 1$, there exists an integer $\mu=\mu(h)\geq 1$ with
the following property. Let $G$ be a connected graph with no clique of
cardinality $h$ and let $S\subseteq G$ such that $|S|\geq\mu$. Then either
some path in $G$ contains $h$ vertices of $S$, or there is an induced subgraph
$H$ of $G$ with $|H\cap S|=h$ for which one of the following holds.

  * •

$H$ is either a caterpillar or the line graph of a caterpillar with $H\cap
S=\mathcal{Z}(H)$.

  * •

$H$ is a subdivided star with root $r$ such that $\mathcal{Z}(H)\subseteq
H\cap S\subseteq\mathcal{Z}(H)\cup\\{r\\}$.

Let $H$ be a graph that is either a path, or a caterpillar, or the line graph
of a caterpillar, or a subdivided star with root $r$. We define an induced
subgraph of $H$, denoted by $P(H)$, which we will use throughout the paper. If
$H$ is a path let $P(H)=H$. If $H$ is a caterpillar, let $P(H)$ be the spine
of $H$. If $H$ is the line graph of a caterpillar $C$, let $P(H)$ be the path
of $H$ consisting of the vertices of $H$ that correspond to the edges of the
spine of $C$. If $H$ is a subdivided claw with root $r$, let $P(H)=\\{r\\}$.
The legs of $H$ are the components of $H\setminus P$. Our first goal is to
prove the following variant of Theorem 5.3:

######  Theorem 5.4.

For every integer $h^{\prime}\geq 1$, there exists an integer
$\nu=\nu(h^{\prime})\geq 1$ with the following property. Let $G$ be a
connected graph with no clique of cardinality $h^{\prime}$. Let
$S^{\prime}\subseteq G$ such that $|S^{\prime}|\geq\nu$, $G\setminus
S^{\prime}$ is connected and every vertex of $S^{\prime}$ has a neighbor in
$G\setminus S^{\prime}$. Then there is a set $\tilde{S}\subseteq S^{\prime}$
with $|\tilde{S}|=h^{\prime}$ and an induced subgraph $H^{\prime}$ of
$G\setminus S^{\prime}$ for which one of the following holds.

  * •

$H^{\prime}$ is a path and every vertex of $\tilde{S}$ has a neighbor in
$H^{\prime}$; or

  * •

$H^{\prime}$ is a caterpillar, or the line graph of a caterpillar, or a
subdivided star. Moreover, every vertex of $\tilde{S}$ has a unique neighbor
in $H^{\prime}$ and $H^{\prime}\cap N(\tilde{S})=\mathcal{Z}(H^{\prime})$.

###### Proof.

Write $G^{\prime}:=G\setminus S^{\prime}$, let $h=1+h^{\prime}+2h^{\prime 2}$,
and let $\nu=h^{\prime}\mu(h)$, where $\mu$ is as in Theorem 5.3. Assume that
the first bullet point above does not hold, that is:

(3) _For every path $Q$ of $G^{\prime}$, $|N(Q)\cap S^{\prime}|\leq
h^{\prime}-1$._

Now choose, for every $s\in S^{\prime}$, a neighbor $n(s)$ of $s$ in
$G^{\prime}$, and let $S:=\\{n(s):s\in S^{\prime}\\}$. By (5),
$|n^{-1}(v)|\leq h^{\prime}-1$ for all $v\in G^{\prime}$ (and in particular
for all $v\in S$), and so $|S|\geq|S^{\prime}|/h^{\prime}=\mu(h)$. Let
$S^{\prime\prime}\subseteq S^{\prime}$ be minimal such that $S=\\{n(s):s\in
S^{\prime\prime}\\}$. It follows that $n$ is a bijection between
$S^{\prime\prime}$ and $S$.

We now apply Theorem 5.3 to $G^{\prime},S$ and $h$. By (5), the path outcome
of the theorem does not happen, so there is an induced subgraph $H$ of
$G^{\prime}$ with $|H\cap S|=h$, for which one of the following holds:

  * •

$H$ is either a caterpillar or the line graph of a caterpillar with $H\cap
S=\mathcal{Z}(H)$.

  * •

$H$ is a subdivided star with root $r$ such that $\mathcal{Z}(H)\subseteq
H\cap S\subseteq\mathcal{Z}(H)\cup\\{r\\}$.

Let $P:=P(H)$, and let $A:=S^{\prime\prime}\cap n^{-1}(\mathcal{Z}(H)\setminus
P)$; in other words, $A$ consists of the vertices of $S^{\prime\prime}$ whose
selected neighbors are simplicial vertices of $H$ other than the endpoint(s)
of $P$. In particular, $|A|\geq h-2=2h^{\prime 2}+h^{\prime}-1$. Moreover, for
each $v\in A$, $n(v)$ belongs to a unique leg of $H$, which yields a bijective
correspondence between $A$ and the set of legs of $H$ (henceforth, if $n(v)\in
D$ for a vertex $v\in A$ and a leg $D$ of $H$, we will say that $v$
corresponds to $D$, and vice-versa).

Let $A^{\prime\prime}\subseteq A$ be the set of vertices of $A$ anticomplete
to $P$. We note that, by (5), $|A^{\prime\prime}|\geq|A|-(h^{\prime}-1)\geq
2h^{\prime 2}$. Let $H^{\prime\prime}$ be obtained from $H$ by removing all
legs corresponding to vertices in $A\setminus A^{\prime\prime}$. In
particular, we note that $H^{\prime\prime}$ is still a caterpillar, line graph
of a caterpillar, or star, according to what $H$ was, and that the vertices of
$A^{\prime\prime}$ correspond bijectively to the legs of $H^{\prime\prime}$.

Define now a directed graph $F$ as follows. $V(F)$ is the set of legs of
$H^{\prime\prime}$, and we have an arc from $D_{1}\in F$ to $D_{2}\in F$ if
the vertex $s_{2}$ corresponding to $D_{2}$ has a neighbor in $D_{1}$. By (5),
every vertex of $F$ has at most $h^{\prime}-1$ outneighbours, and so by Lemma
5.2, the underlying undirected graph of $F$ contains a stable set $T$ of size
$\frac{|V(F)|}{2(h^{\prime}-1)+1}\geq\frac{2h^{\prime 2}}{2h^{\prime}-1}\geq
h^{\prime}$. Let $\tilde{S}$ be the set corresponding to the legs in $T$, and
let $H^{\prime}$ be obtained from $H^{\prime\prime}$ by deleting the legs not
in $T$. It is routine to check that $H^{\prime}$ and $\tilde{S}$ satisfy the
second outcome of Theorem 5.4. ∎

Next we introduce more terminology. Let $G$ be a graph, let
$P=p_{1}\hbox{-}\dots\hbox{-}p_{n}$ be a path of $G$ and let
$X=\\{x_{1},\dots,x_{k}\\}\subseteq G\setminus P$. We say that $(P,X)$ is an
alignment if $N_{P}(x_{1})=\\{p_{1}\\}$, $N_{P}(x_{k})=\\{p_{n}\\}$, every
vertex of $X$ has a neighbor in $P$, and there exist
$1<j_{2}<\dots<j_{k-1}<j_{k}=n$ such that $N_{P}(x_{i})\subseteq
p_{j_{i}}\hbox{-}P\hbox{-}p_{j_{i+1}-1}$ for $i\in\\{2,\dots,k-1\\}$. We also
say that $x_{1},\dots,x_{k}$ is the order on $X$ given by the alignment
$(P,X)$. An alignment $(P,X)$ is wide if each of $x_{2},\dots,x_{k-1}$ has two
non-adjacent neighbors in $P$, spiky if each of $x_{2},\dots,x_{k-1}$ has a
unique neighbor in $P$ and triangular if each of $x_{2},\dots,x_{k-1}$ has
exactly two neighbors in $P$ and they are adjacent. An alignment is consistent
if it is wide, spiky or triangular. Next, let $H$ be a caterpillar or the line
graph of a caterpillar and let $S$ be a set of vertices disjoint from $H$ such
that every vertex of $S$ has a unique neighbor in $H$ and $H\cap
N(S)=\mathcal{Z}(S)$. Let $X$ be the set of vertices of $H\setminus P(H)$ that
have neighbors in $P(H)$. Then the neighbors of elements of $X$ appear in
$P(H)$ in order (in fact, $(X,Q)$ is an alignment for some subpath $Q$ of
$P(H))$; let $x_{1},\dots,x_{k}$ be the corresponding order on $X$. Now, order
the vertices of $S$ as $s_{0},s_{1},\dots,s_{k},s_{k+1}$ where $s_{i}$ has a
neighbor in the leg of $H$ containing $x_{i}$ for $i\in\\{1,\dots,k\\}$, and
$s_{0},s_{k+1}$ are the ends of $P(H)$ in this order. We say that
$s_{0},s_{1},\dots,s_{k},s_{k+1}$ is the order on $S$ given by $(H,S)$.

Next, let $H$ be an induced subgraph of $G$ that is a caterpillar, or the line
graph of a caterpillar, or a subdivided star and let $X\subseteq G\setminus H$
be such that every vertex of $X$ has a unique neighbor in $H$ and $H\cap
N(X)=\mathcal{Z}(H)$. We say that $(H,X)$ is a consistent connectifier and it
is spiky, triangular, or stellar respectively.

Our next goal is, starting with a graph $G\in\mathcal{C}_{t}$ and a stable set
$X\subseteq V(G)$, to produce certain consistent connectifiers. We start with
a lemma.

######  Lemma 5.5.

Let $G\in\mathcal{C}$ and assume that $V(G)=H_{1}\cup H_{2}\cup X$ where $X$
is a stable set with $|X|\geq 3$ and $X\cap\operatorname{Hub}(G)=\emptyset$.
Suppose that for $i\in\\{1,2\\}$, the pair $(H_{i},X)$ is a consistent
alignment, or a consistent connectifier. Assume also that if neither of
$(H_{1},X),(H_{2},X)$ is stellar, then the orders given on $X$ by $(H_{1},X)$
and by $(H_{2},X)$ are the same. Then (possibly switching the roles of $H_{1}$
and $H_{2}$), we have that:

  * •

$(H_{1},X)$ is a triangular alignment or a triangular connectifier; and

  * •

$(H_{2},X)$ is a spiky connectifier, a stellar connectifier, a spiky alignment
or a wide alignment.

Moreover, if $(H_{1},X)$ is a triangular alignment, then $(H_{2},X)$ is not a
wide alignment.

###### Proof.

If at least one $(H_{i},X)\subseteq\\{(H_{1},X),(H_{2},X)\\}$ is not a stellar
connectifier, we let $x_{1},\dots,x_{k}$ be the order given on $X$ by
$(H_{i},X)$. If both of $(H_{i},X)$ are stellar connectifiers, we let
$x_{1},\dots,x_{k}$ be an arbitrary order on $X$. Let $H$ be the unique hole
contained in $H_{1}\cup H_{2}\cup\\{x_{1},x_{k}\\}$. For $j\in\\{1,2\\}$ and
$i\in\\{1,\dots,k\\}$, if $H_{j}$ is a connectifier, let $D_{i}^{j}$ be the
leg of $H_{j}$ containing a neighbor of $x_{i}$; and if $H_{j}$ is an
alignment let $D_{i}^{j}=\emptyset$.

Suppose first that $(H_{1},X)$ is a triangular alignment or a triangular
connectifier. If $(H_{2},X)$ is a triangular alignment or a triangular
connectifier, then for every $i\in\\{2,\dots,k-1\\}$, the graph $H\cup
D_{i}^{1}\cup D_{i}^{2}\cup\\{x_{i}\\}$ is either a prism or an even wheel
with center $x_{i}$, a contradiction. This proves that $(H_{2},X)$ is a
stellar connectifier, or a spiky connectifier, or a spiky alignment, or a wide
alignment. We may assume that $(H_{1},X)$ is a triangular alignment and
$(H_{2},X)$ is a wide alignment, for otherwise the theorem holds. But now for
every $x\in X\setminus\\{x_{1},x_{k}\\}$, $(H,x)$ is a proper wheel, a
contradiction.

Thus we may assume that for $i\in\\{1,2\\}$, the pair $(H_{i},X)$ is a a
stellar connectifier, or a spiky connectifier, or a spiky alignment, or a wide
alignment. Now for every $x_{i}\in X\setminus\\{x_{1},x_{k}\\}$, the graph
$H\cup D_{i}^{1}\cup D_{i}^{2}\cup\\{x_{i}\\}$ is either a theta or a proper
wheel with center $x$, a contradiction. This proves Lemma 5.5. ∎

We now prove the main result of this section, which is a refinement of Theorem
5.4 for graphs in $\mathcal{C}$.

######  Theorem 5.6.

For every integer $x\geq 1$, there exists an integer $\tau=\tau(x)\geq 1$ with
the following property. Let $G\in\mathcal{C}_{x}$ and assume that
$V(G)=D_{1}\cup D_{2}\cup Y$ where

  * •

$Y$ is a stable set with $|Y|=\tau$,

  * •

$D_{1}$ and $D_{2}$ are components of $G\setminus Y$, and

  * •

$N(D_{1})=N(D_{2})=Y$.

Assume that $Y\cap\operatorname{Hub}(G)=\emptyset$. Then there exist
$X\subseteq Y$ with $|X|=x$, $H_{1}\subseteq D_{1}$ and $H_{2}\subseteq D_{2}$
(possibly with the roles of $D_{1}$ and $D_{2}$ reversed) such that

  * •

$(H_{1},X)$ is a triangular connectifier or a triangular alignment;

  * •

$(H_{2},X)$ is a stellar connectifier, or a spiky connectifier, or a spiky
alignment or a wide alignment; and

  * •

if $(H_{1},X)$ is a triangular alignment, then $(H_{2},X)$ is not a wide
alignment.

Moreover, if neither of $(H_{1},X),(H_{2},X)$ is a stellar connectifier, then
the orders given on $X$ by $(H_{1},X)$ and by $(H_{2},X)$ are the same.

###### Proof.

Let $z=(27)^{2}\cdot 36x^{4}$ and let $\tau(x)=\nu(\nu(z))$, where $\nu$ is as
in Theorem 5.4. Applying Theorem 5.4 twice, we obtain a set $Z\subseteq Y$
with $|Z|=z$ and $H_{i}\subseteq D_{i}$ such that either

  * •

$H_{i}$ is a path and every vertex of $Z$ has a neighbor in $H_{i}$; or

  * •

$(H_{i},X)$ is a consistent connectifier

for every $i\in\\{1,2\\}$.

(4) _Let $i\in\\{1,2\\}$ and $y\in\mathbb{N}$. If $H_{i}$ is a path and every
vertex of $Z$ has a neighbor in $H_{i}$, then either some vertex of $H_{i}$
has $y$ neighbors in $Z$, or there exists $Z^{\prime}\subseteq Z$ with
$|Z^{\prime}|\geq\frac{|Z|}{27y}$ and a subpath $H_{i}^{\prime}$ of $H_{i}$
such that $(H_{i},Z^{\prime})$ is a consistent alignment._

Let $H_{i}=h_{1}\hbox{-}\dots\hbox{-}h_{k}$. We may assume that $H_{i}$ is
chosen minimal satisfying Theorem 5.4, and so there exist $z_{1},z_{k}\in Z$
such that $N_{H_{i}}(z_{j})=\\{h_{j}\\}$ for $j\in\\{1,k\\}$.

We may assume that $|N_{Z}(h)|<y$ for every $h\in H_{i}$. Let $Z_{1}$ be the
set of vertices in $Z$ with exactly one neighbor in $H_{i}$. Then, if
$|Z_{1}|\geq|Z|/3$, it follows that $Z_{1}$ contains a set $Z^{\prime}$ with
$|Z^{\prime}|\geq|Z_{1}|/y\geq|Z|/(3y)$ such that no two vertices in
$Z^{\prime}$ have a common neighbor in $H_{i}$. We may assume that
$z_{1},z_{k}\in Z^{\prime}$. Therefore, $(H_{i},Z^{\prime})$ is a spiky
alignment.

Next, let $Z_{2}$ be the set of vertices in $z\in Z$ such that either
$z\in\\{z_{1},z_{k}\\}$ or has exactly two neighbors in $H_{i}$, and they are
adjacent. Now, if $|Z_{2}|\geq|Z|/3$, by choosing $Z^{\prime}$ greedily, it
follows that $Z_{2}$ contains a subset $Z^{\prime}$ with the following
specifications:

  * •

$z_{1},z_{k}\in Z^{\prime}$;

  * •

$|Z^{\prime}|\geq|Z_{2}|/(2y)\geq|Z|/(6y)$; and

  * •

no two vertices in $Z^{\prime}$ have a common neighbor in $H_{i}$.

But then $(H_{i},Z^{\prime})$ is a triangular alignment, as desired.

Let $Z_{3}=\\{z_{1},z_{k}\\}\cup(Z\setminus(Z_{1}\cup Z_{2}))$. From the
previous two paragraphs, we may assume that $|Z_{3}|\geq|Z|/3$. Let $R$ be a
path from $z_{1}$ to $z_{k}$ with $R^{*}\subseteq H_{3-i}$, and let $H$ be the
hole $z_{1}\hbox{-}H_{i}\hbox{-}z_{k}\hbox{-}R\hbox{-}z_{1}$. If some $z\in
Z\setminus\\{z_{1},z_{k}\\}$ has at least four neighbors in $H_{i}$, then
$(H,z)$ is a proper wheel in $G$, a contradiction. This proves that
$|N_{H_{i}}(z)|\leq 3$ for every $z\in Z$.

Let $z\in Z$. Define $Bad(z)=N_{H_{i}}[N_{H_{i}}(z)]$. Since
$|N_{H_{i}}(z)|\leq 3$ and $H_{i}$ is a path, it follows that $|Bad(z)|\leq
9$. Since $N_{Z}(h)<y$ for every $h\in H_{i}$, we can greedily choose
$Z^{\prime}\subseteq Z$ with
$|Z^{\prime}|\geq\frac{|Z_{3}|}{9y}\geq\frac{|Z|}{27y}$, $z_{1},z_{k}\in
Z^{\prime}$ and such that if $z,z^{\prime}\in Z^{\prime}$, then $z^{\prime}$
is anticomplete to $Bad(z)$.

We claim that $(H_{i},Z^{\prime})$ is an alignment. Suppose not; then there
exist $i<j<k$ such that $h_{i},h_{k}\in N(z)$ and $h_{j}\in N(z^{\prime})$ for
$z,z^{\prime}\in Z^{\prime}$ with $z\neq z^{\prime}$. We may assume that
$i,j,k$ are chosen with $|k-i|$ minimum. It follows that $z$ has no neighbor
in $\\{h_{i+1},\dots,h_{k-1}\\}$. We consider three cases:

  * •

If $z^{\prime}$ has a neighbor $h_{l}$ with $l>k$, then we define
$P_{1}=z$-$h_{i}$-$P$-$h_{j}$-$z^{\prime}$ and
$P_{2}=z$-$h_{k}$-$P$-$h_{l}$-$z^{\prime}$.

  * •

If $z^{\prime}$ has a neighbor $h_{l}$ with $l<i$, then we define
$P_{1}=z$-$h_{i}$-$P$-$h_{l}$-$z^{\prime}$ and
$P_{2}=z$-$h_{k}$-$P$-$h_{j}$-$z^{\prime}$.

  * •

Otherwise, all neighbors of $z^{\prime}$ are in $\\{h_{i+1},\dots,h_{k-1}\\}$.
Let $h_{j}$ and $h_{l}$ be the first and last neighbor of $z^{\prime}$ in
$h_{i+1}$-$\dots$-$h_{k-1}$, respectively. Then, since $z^{\prime}\in Z_{3}$,
it follows that $|l-j|>1$. We define
$P_{1}=z$-$h_{i}$-$P$-$h_{j}$-$z^{\prime}$ and
$P_{2}=z$-$h_{k}$-$P$-$h_{l}$-$z^{\prime}$.

Now we get a theta with ends $z,z^{\prime}$ and paths $P_{1}$, $P_{2}$ and a
third path with interior in $H_{3-i}$, a contradiction. This proves that
$(H_{i},Z^{\prime})$ is an alignment. Since $Z^{\prime}\subseteq Z_{3}$, it
follows that $(H_{i},Z^{\prime})$ is a wide alignment. This proves (5).

(5) _There is a subset $\hat{Z}\subseteq Z$ with $|\hat{Z}|\geq x$, and a path
$\hat{H_{i}}\subseteq H_{i}$ for $i=1,2$ such that $(\hat{H_{i}},\hat{Z})$ is
a consistent alignment or a connectifier. Moreover, if neither of
$(\hat{H_{1}},\hat{Z)},(\hat{H_{2}},\hat{Z})$ is a stellar connectifier, then
the order given on $\hat{Z}$ by $(\hat{H_{1}},\hat{Z})$ and
$(\hat{H_{2}},\hat{Z})$ is the same._

Suppose first that some $h\in H_{1}$ has at least $6x$ neighbors in $Z$. Let
$\hat{H_{1}}=\\{h\\}$, and let $\hat{Z}\subseteq Z\cap N(h)$ with
$|\hat{Z}|=6x$. If $(H_{2},Z)$ is a connectifier, then setting
$\hat{H_{2}}=H_{2}$, we have that (5) holds. So we may assume that $H_{2}$ is
a path and every vertex of $Z$ has a neighbor in $H_{2}$. Let $\hat{H_{2}}$ be
a minimal subpath of $H_{2}$ such that every $z\in\hat{Z}$ has a neighbor in
$\hat{H_{2}}$. Then $H_{2}=h_{1}\hbox{-}\dots\hbox{-}h_{k}$ and there exist
$z_{1},z_{k}\in\hat{Z}$ such that $N_{\hat{H_{2}}}(z_{i})=\\{h_{i}\\}$ for
$i\in\\{1,k\\}$. Since for every $z\in\hat{Z}\setminus\\{z_{1},z_{k}\\}$, the
graph $H_{2}\cup\\{z_{1},z_{k},z,h\\}$ is not a theta and not a proper wheel
with center $z$, it follows that every $z\in\hat{Z}\setminus\\{z_{1},z_{k}\\}$
has exactly two neighbors in $H_{2}$ and they are adjacent. Moreover, no
vertex $x$ of $H_{2}$ has three or more neighbors in $\hat{Z}$, for otherwise
$\\{x,h\\}\cup(N(x)\cap\hat{Z})$ contains a $K_{2,3}$. Now, by choosing
$Z^{\prime}\subseteq\hat{Z}$ greedily, we find a set $Z^{\prime}$ with the
following specifications:

  * •

$z_{1},z_{k}\in Z^{\prime}$;

  * •

$|Z^{\prime}|\geq\hat{Z}/6$; and

  * •

no two vertices in $Z^{\prime}$ have a common neighbor in $H_{2}$.

But then $(H_{1},Z^{\prime})$ is a triangular alignment, and (5) holds.
Therefore, each vertex $h\in H_{1}$ has at most $6x$ neighbors in $Z$; and by
symmetry, it follows that each vertex $h\in H_{2}$ has at most $6x$ neighbors
in $Z$.

In view of this, applying (5) with $y=6x$ (possibly twice), we conclude that
there exists $Z^{\prime}\subseteq Z$ with $|Z^{\prime}|\geq x^{2}$ and
subgraphs $H_{i}^{\prime}\subseteq H_{i}$ such that
$(H_{i}^{\prime},Z^{\prime})$ is a consistent alignment or a consistent
connectifier. If none of them is a stellar connectifier, for $i\in\\{1,2\\}$,
let $\pi_{i}$ be the order given on $Z^{\prime}$ by $(H_{i},Z^{\prime})$. By
Theorem 5.1 there exists $\hat{Z}\subseteq Z^{\prime}$ such that (possibly
reversing $H_{i}$) the orders $\pi_{i}$ restricted to $\hat{Z}$ are the same,
as required. This proves (5).

Now Theorem 5.6 follows from Lemma 5.5. ∎

##  6\. Bounding the number of non-hubs

In this section, we show that a bag of a structured tree decomposition of a
graph $G\in\mathcal{C}_{tt}$ contains a small number of vertices of
$G\setminus\operatorname{Hub}(G)$. This is the only place in the paper where
the assumption that $G\in\mathcal{C}_{tt}$ (rather than $G\in\mathcal{C}_{t}$)
is used.

######  Theorem 6.1.

Let $G\in\mathcal{C}$ and let $(T,\chi)$ be a structured tree decomposition of
$G$. Let $v\in T$ and $Y\subseteq\chi(v)$ be a stable set. Then there exist
components $D_{1},\dots,D_{k}$ of $G\setminus\chi(v)$ such that
$Y\subseteq\bigcup_{i=1}^{k}N(D_{i})$ and $k\leq 4$.

###### Proof.

Let $D_{1}$ be a component of $G\setminus\chi(v)$ such that $N(D_{1})\cap Y$
is maximal. We may assume there exists $x_{1}\in Y\setminus N(D_{1})$. Since
$(T,\chi)$ is structured and since $x_{1}$ is not complete to
$\chi(v)\setminus\\{x_{1}\\}$, by Theorem 2.3 there exists a component $D_{2}$
of $G\setminus\chi(v)$ such that $x_{1}\in N(D_{2})$; choose $D_{2}$ with
$N(D_{2})\cap Y\cap N(D_{1})$ is maximal. By the maximality of $N(D_{1})\cap
Y$, there exists $x_{2}\in(Y\cap N(D_{1}))\setminus N(D_{2})$. Since
$(T,\chi)$ is structured, Theorem 2.3 implies that there exists a component
$D_{3}$ of $G\setminus\chi(v)$ such that $x_{1},x_{2}\in N(D_{3})$. By the
choice of $D_{2}$, there exists $x_{3}\in N(D_{1})\cap N(D_{2})\cap Y$ such
that $x_{3}\not\in N(D_{3})$. For $\\{i,j,k\\}=\\{1,2,3\\}$, let $P_{ij}$ be a
path from $x_{i}$ to $x_{j}$ with interior in $D_{k}$.

Let $\mathcal{D}$ be the set of all components $D$ of $G\setminus\chi(v)$ that
such that $|N(D)\cap\\{x_{1},x_{2},x_{3}\\}|>1$. Then
$D_{1},D_{2},D_{3}\in\mathcal{D}$.

(6) _We have that $|\mathcal{D}\setminus\\{D_{1},D_{2},D_{3}\\}|\leq 1$._

Suppose first that there is a component
$D\in\mathcal{D}\setminus\\{D_{1},D_{2},D_{3}\\}$ with
$N(D)\cap\\{x_{1},x_{2},x_{3}\\}=\\{x_{1},x_{2}\\}$. Then, we get a theta with
ends $x_{1},x_{2}$ and paths $x_{1}$-$P_{12}$-$x_{2}$,
$x_{1}$-$P_{13}$-$x_{3}$-$P_{23}$-$x_{2}$ as well as a third path with
interior in $D$ (using that $x_{3}\not\in N(D)$). This is a contradiction, and
proves that $N(D)=\\{x_{1},x_{2},x_{3}\\}$.

Now suppose that $D,D^{\prime}\in\mathcal{D}\setminus\\{D_{1},D_{2},D_{3}\\}$
with $D\neq D^{\prime}$. Then we get a theta with ends $x_{2},x_{3}$ and paths
with interiors in $D_{1},D,D^{\prime}$, respectively, a contradiction. This
proves (6).

Thus $|\mathcal{D}|\leq 4$. We may assume that there is a vertex $x\in Y$ such
that $x\not\in\bigcup_{D\in\mathcal{D}}N(D)$. Since $(T,\chi)$ is structured,
Theorem 2.3 implies that there exist paths $P_{1},P_{2}$ where $P_{i}$ is from
$x$ to $x_{i}$, and $P_{i}^{*}\cap\chi(v)=\emptyset$. It follows that each
$P_{i}^{*}$ is contained in a component $F_{i}$ of $G\setminus\chi(v)$. Since
$F_{i}\not\in\mathcal{D}$, it follows that $F_{1}\neq F_{2}$,
$x_{2},x_{3}\not\in N(F_{1})$, and $x_{1},x_{3}\not\in N(F_{2})$. Now we get a
theta with ends $x_{1},x_{2}$ and paths
$x_{1}\hbox{-}P_{13}\hbox{-}x_{3}\hbox{-}P_{23}\hbox{-}x_{2}$,
$x_{1}\hbox{-}P_{12}\hbox{-}x_{2}$ and
$x_{1}\hbox{-}P_{1}\hbox{-}x\hbox{-}P_{2}\hbox{-}x_{2}$, a contradiction. This
proves Theorem 6.1. ∎

Next we show:

######  Theorem 6.2.

Let $G\in\mathcal{C}_{tt}$, let $S$ be a minimal separator of $G$, and let
$Y\subseteq S\setminus\operatorname{Hub}(G)$ be stable. Let $\tau=\tau(t)$ be
as in Theorem 5.6. Then $|Y|\leq\tau$.

###### Proof.

Suppose $|Y|\geq\tau$. Let $D_{1},D_{2}$ be distinct full components for $X$.
Apply Theorem 5.6 to $D_{1}\cup D_{2}\cup Y$, and let $H_{1},H_{2},X$ be as in
the conclusion of 5.6. Then a routine case analysis (whose details we leave to
the reader) shows that $H_{1}\cup H_{2}\cup X$ contains a generalized
$t$-pyramid in $G$, a contradiction. This proves Theorem 6.2. ∎

We can now prove the main result of this section.

######  Theorem 6.3.

Let $G\in\mathcal{C}_{tt}$, let $(T,\chi)$ be a structured tree decomposition
of $G$, and let $v\in T$. Let
$Y\subseteq\chi(v)\setminus\operatorname{Hub}(G)$ be stable. Let
$\tau=\tau(t)$ be as in Theorem 5.6. Then $|Y|\leq 4\tau$.

###### Proof.

Suppose $|Y|>4\tau$. By Theorem 6.1, there exists a component $D$ of
$G\setminus\chi(v)$ such that $|N(D)\cap Y|>\tau$. By Theorem 2.4, $N(D)\cap
Y$ is a minimal separator of $G$, contrary to Theorem 6.2. This proves Theorem
6.3. ∎

##  7\. Putting everything together

For the remainder of the paper, all logarithms are taken in base 2. We start
with the following theorem from [2]:

######  Theorem 7.1 (Abrishami, Chudnovsky, Hajebi, Spirkl [2]).

Let $t\in\mathbb{N}$, and let $G$ be (theta, $K_{t}$)-free with $|V(G)|=n$.
There exist an integer $d=d(t)$ be and a partition $(S_{1},\dots,S_{k})$ of
$V(G)$ with the following properties:

  1. (1)

$k\leq\frac{d}{4}\log n$.

  2. (2)

$S_{i}$ is a stable set for every $i\in\\{1,\dots,k\\}$.

  3. (3)

For every $i\in\\{1,\dots,k\\}$ and $v\in S_{i}$ we have
$\deg_{G\setminus\bigcup_{j<i}S_{j}}(v)\leq d$.

Let $G\in\mathcal{C}_{tt}$ be a graph. A hub-partition of $G$ is a partition
$S_{1},\dots,S_{k}$ of $\operatorname{Hub}(G)$ as in Theorem 7.1; we call $k$
the order of the partition. We call the hub-dimension of $G$ (denoting it by
$\operatorname{hdim}(G)$) the smallest $k$ such that $G$ as a hub-partition of
order $k$.

For the remainder of this section, let us fix $t\in\mathbb{N}$. Let $d=d(t)$
as in Theorem 7.1. Let $C_{t}=\gamma(t)+1$ with $\gamma(t)$ as in Theorem 3.7.
Let $k_{t}=k(t)$ be as in Theorem 3.6. Let $m=k_{t}+2d$. Let $\Psi=4\tau(t)$
where $\tau(t)$ is as in Theorem 5.6. Let $\Delta=(2m-1)m+C_{t}$.

The following is a strengthening of Theorem 1.4, which we prove by induction
on $\operatorname{hdim}(G)$. By Theorem 7.1,
$\operatorname{hdim}(G)\leq\frac{d}{4}\log n$ for every
$G\in\mathcal{C}_{tt}$, so Theorem 7.2 immediately implies Theorem 1.4.

######  Theorem 7.2.

Let $G\in\mathcal{C}_{tt}$ with $|V(G)|=n$. Then $\operatorname{tw}(G)\leq
C_{t}+\Delta\Psi(\log n+\operatorname{hdim}(G))$.

###### Proof.

The proof is by induction on $\operatorname{hdim}(G)$, and for a fixed value
of $\operatorname{hdim}$, by induction on $n$. If $hdim(G)=0$, then by Theorem
3.7, we have that $\operatorname{tw}(G)\leq C_{t}$ and Theorem 7.2 holds as
required. Thus we may assume $\operatorname{hdim}(G)>0$. A special case of
Lemma 3.1 from [8] shows that clique cutsets do not affect treewidth; thus we
may assume that $G$ does not admit a clique cutset.

(7) _If $G$ has a balanced separator of size at most $m$, then the theorem
holds._

Let $X$ be a balanced separator of $G$ of size at most $m$. Let
$D_{1},\dots,D_{s}$ be the components of $G\setminus X$. Since
$|D_{i}|\leq\frac{n}{2}$ for every $i\in\\{1,\dots,s\\}$, it follows from our
induction on $n$ that $\operatorname{tw}(D_{i})\leq C_{t}+\Delta\Psi(\log
n+\operatorname{hdim}(G)-1)$. Then, by Lemma 2.15, the treewidth of $G$ is at
most

$\displaystyle\ \ \ \ \max_{i\in\\{1,\dots,s\\}}\operatorname{tw}(D_{i})+|X|$
$\displaystyle\leq C_{t}+\Delta\Psi(\log n+\operatorname{hdim}(G)-1)+m$
$\displaystyle\leq C_{t}+\Delta\Psi(\log n+\operatorname{hdim}(G)),$

where we use that $\Delta\geq m$. This proves (7).

In view of (7), we may assume that $G$ does not admit a balanced separator of
size at most $m$, and so the results of Section 4 apply.

Let $S_{1},\dots,S_{k}$ be a hub-partition of $G$ with
$k=\operatorname{hdim}(G)$. We now use the terminology from Section 4. If
follows from the definition of $S_{1}$ that every vertex in $S_{1}$ is
$d$-safe. Let $(T,\chi)$ be an $m$-atomic tree decomposition of $G$. Let
$t_{0}$ be a center for $T$, and let $\beta=\beta(S_{1})$ be as in Section 4.
Write $\beta_{0}=\chi(t_{0})$. Our first goal is to prove:

(8) _There is a tree decomposition $(T_{\beta},\chi_{\beta})$ of $\beta$ of
such that for every $t\in T_{\beta}$, we have that
$|\chi_{\beta}(t)\cap\beta_{0}|\leq C_{t}+\Delta\Psi(\log
n+k-1)+(\Delta-m)\Psi$._

We start with:

(9) _If $\beta$ has a balanced separator of size at most $2m(m-1)+C_{t}$, then
(7) holds._

To prove (7), we let $X$ be a balanced separator of size at most
$2m(m-1)+C_{t}=\Delta-m$ of $\beta$. Let $D_{1},\dots,D_{s}$ be the components
of $\beta\setminus X$. Since $|D_{i}|\leq\frac{|\beta|}{2}\leq\frac{n}{2}$ for
every $i\in\\{1,\dots,s\\}$, it follows from our induction on $n$ that
$\operatorname{tw}(D_{i})\leq C_{t}+\Delta\Psi(\log
n+\operatorname{hdim}(G)-1)$. Therefore, by Lemma 2.15 applied to $\beta$ and
$X$, we conclude that:

$\displaystyle\operatorname{tw}(\beta)$
$\displaystyle\leq\max_{i\in\\{1,\dots,s\\}}\operatorname{tw}(D_{i})+|X|$
$\displaystyle\leq
C_{t}+\Delta\Psi(\log|\beta|+\operatorname{hdim}(G)-1)+\Delta-m$
$\displaystyle\leq C_{t}+\Delta\Psi(\log
n+\operatorname{hdim}(G)-1)+(\Delta-m)\Psi.$

This proves (7).

Now we may assume that $\beta$ does not have a balanced separator of size at
most $2m(m-1)+C_{t}$. Therefore $\beta^{A}(S_{1})$ is defined, as in Section
4. By Theorem 4.7(4), we have that
$S_{1}\cap\operatorname{Hub}(\beta^{A}(S_{1}))=\emptyset$ and $S_{2}\cap
Hub(\beta^{A}(S_{1})),\dots,S_{k}\cap Hub(\beta^{A}(S_{1}))$ is a hub-
partition of $\beta^{A}(S_{1})$. It follows that
$\operatorname{hdim}(\beta^{A}(S_{1}))\leq k-1$.

Let $D_{1},\dots D_{s}$ be the components of $\beta\setminus\beta^{A}(S_{1})$.
By Theorem 4.7(3), we have that $|D_{i}|\leq\frac{n}{2}$ for every
$i\in\\{1,\dots,s\\}$. Moreover, by induction on $k$, we obtain that

$\operatorname{tw}(\beta^{A}(S_{1}))\leq C_{t}+\Delta\Psi(\log n+k-1).$

Our induction on $n$ further implies that

$\operatorname{tw}(D_{i})\leq C_{t}+\Delta\Psi(\log n+k-1).$

By Theorem 2.6, the graph $\beta^{A}(S_{1})$ admits a structured tree
decomposition $(T_{0},\chi_{0})$ of width
$\operatorname{tw}(\beta^{A}(S_{1}))$. For every $i\in\\{1,\dots,s\\}$, let
$(T_{i},\chi_{i})$ be a tree decomposition of $D_{i}$ of width
$\operatorname{tw}(D_{i})$. Let $(T_{\beta},\chi_{\beta})$ be a tree
decomposition of $\beta$ obtained as in Theorem 4.8. We claim:

(10) _For every $i\in\\{0,\dots,s\\}$ and for every $t\in T_{i}$, we have that
$|(\chi_{\beta}(t)\setminus\chi_{i}(t))\cap\beta_{0}|\leq 2m(m-1)\Psi$._

Let $i\in\\{1,\dots,s\\}$ and let $t\in T_{i}$. It follows immediately from
Theorem 4.8 that $|(\chi_{\beta}(t)\setminus\chi_{i}(t))\cap\beta_{0}|\leq
2m(m-1)$. Now let $t\in T_{0}$. Since
$S_{1}\cap\operatorname{Hub}(\beta^{A}(S_{1}))=\emptyset$, we deduce from
Theorem 6.3 applied to $\beta^{A}(S_{1})$ that that
$|\chi_{0}(t)\cap\operatorname{Core}(S_{1})|\leq\Psi$. Now again it follows
from Theorem 4.8 that
$|(\chi_{\beta}(t)\setminus\chi_{0}(t))\cap\beta_{0}|\leq 2m(m-1)\Psi$. This
proves (7).

Now (7) follows immediately from (7), using that $\Delta-m=2m(m-1)+C_{t}\geq
2m(m-1)$.

Next we use Theorem 4.9 to turn $(T_{\beta},\chi_{\beta})$ into a tree
decomposition of $G$ of the required width. Let
$D_{1}^{\prime},\dots,D_{r}^{\prime}$ be the components of
$G\setminus\beta_{0}$. In view of Theorem 2.6 and (7), we let
$(T_{0}^{\prime},\chi_{0}^{\prime})$ be a structured tree decomposition of
$\beta$ such that for every $t\in T_{0}^{\prime}$, we have that
$|\chi_{0}^{\prime}(t)\cap\beta_{0}|\leq C_{t}+\Delta\Psi(\log
n+k-1)+(\Delta-m)\Psi$.

Let $i\in\\{1,\dots,r\\}$. Since $t_{0}$ is a center of $T$, it follows that
$|D_{i}^{\prime}|\leq\frac{n}{2}$ for every $i\in\\{1,\dots,r\\}$. By
induction on $n$, we have that

$\operatorname{tw}(D_{i}^{\prime})\leq C_{t}+\Delta\Psi(\log n+k-1).$

Let $(T_{i}^{\prime},\chi_{i}^{\prime})$ be a tree decomposition of
$D_{i}^{\prime}$ of width $\operatorname{tw}(D_{i}^{\prime})$. Let $(U,\psi)$
be a tree decomposition of $G$ obtained as in Theorem 4.9. Recall that for
$u\in U$, $\psi(u)$ is defined as follows.

  * •

If $u\in V(T_{0}^{\prime})$, let

$\psi(u)=(S_{1})_{bad}\cup(\chi_{0}^{\prime}(u)\cap\beta_{0})\cup\bigcup_{t_{i}\text{
s.t.
}\chi_{0}^{\prime}(u)\cap(Conn(t_{i})\setminus\chi(t_{0}))\neq\emptyset}(\beta_{0}\cap\chi(t_{i})).$

  * •

If $u\in V(T_{i}^{\prime})$ for $i\in\\{1,\dots,r\\}$, let

$\psi(u)=(S_{1})_{bad}\cup\chi_{i}^{\prime}(u)\cup(\beta_{0}\cap\chi(t_{i})).$

We claim that

$\operatorname{width}(U,\psi)\leq C_{t}+\Delta\Psi(\log n+k).$

To prove this claim, we let $u\in V(U)$; we will establish an upper bound on
$|\psi(u)|$. By Lemma 4.1, we have $|(S_{1})_{bad}|\leq 1$. Now let
$i\in\\{0,\dots,r\\}$ be such that $u\in T_{i}^{\prime}$.

Suppose first that $i>0$. Since $|\beta_{0}\cap\chi(t_{i})|<m$ (because
$(T,\chi)$ is $m$-atomic and therefore $m$-lean by Theorem 2.8), it follows
that

$|\psi(u)|\leq
1+|\chi_{i}^{\prime}(u)|+(m-1)\leq\operatorname{tw}(D_{i}^{\prime})+m\leq
C_{t}+\Delta\Psi(\log n+k),$

using that $m\leq\Delta$, as required.

Thus we may assume that $i=0$. By Theorem 4.2(3), we have that
$(\chi_{0}^{\prime}(u)\setminus\beta_{0})\cap\operatorname{Hub}(\beta)=\emptyset$.
Since for distinct $t_{1},t_{2}\in N_{T}(t_{0})$, the set
$Conn(t_{1})\setminus\beta_{0}$ is disjoint from and anticomplete to the set
$Conn(t_{2})\setminus\beta_{0}$, applying Theorem 6.3 implies that

$|\\{t_{i}:\chi_{0}^{\prime}(u)\cap(Conn(t_{i})\setminus\beta_{0})\neq\emptyset\\}|\leq\Psi.$

Since by (7), we have $|\chi_{0}^{\prime}(u)\cap\beta_{0}|\leq
C_{t}+\Delta\Psi(\log n+k-1)+\Psi(\Delta-m)$, and since
$|\beta_{0}\cap\chi(t_{i})|<m$ for every $i$, we deduce that

$|\psi(u)|\leq 1+C_{t}+\Delta\Psi(\log n+k-1)+(\Delta-1)\Psi\leq
C_{t}+\Delta\Psi(\log n+k),$

as required. This completes the proof of 7.2. ∎

##  8\. Algorithmic consequences

We now repeat the main points of the last section of [2] to explain the
algorithmic significance of Theorem 1.4. We need the following theorem from
[2]:

######  Theorem 8.1 (Abrishami, Chudnovsky, Hajebi, Spirkl [2]).

Let P be a problem which admits an algorithm running in time
$\mathcal{O}(2^{\mathcal{O}(k)}|V(G)|)$ on graphs $G$ with a given tree
decomposition of width at most $k$. Also, let $\mathcal{G}$ be a class of
graphs for which there exists a constant $c=c(\mathcal{G})$ such that
$\operatorname{tw}(G)\leq c\log(|V(G)|)$ for all $G\in\mathcal{G}$. Then P is
polynomial-time solvable in $\mathcal{G}$.

In view of Theorem 1.4 and Theorem 8.1, we conclude the following.

######  Theorem 8.2.

Let $t\geq 1$ be fixed and P be a problem which admits an algorithm running in
time $\mathcal{O}(2^{\mathcal{O}(k)}|V(G)|)$ on graphs $G$ with a given tree
decomposition of width at most $k$. Then P is polynomial-time solvable in
$\mathcal{C}_{tt}$. In particular, Stable Set, Vertex Cover, Dominating Set
and $r$-Coloring (with fixed $r$) are all polynomial-time solvable in
$\mathcal{C}_{tt}$.

Let us now discuss another important problem, and that is Coloring. It is
well-known (and also follows immediately from Theorem 7.1), that for every $t$
there exists a number $d(t)$ such that all graphs in $\mathcal{C}_{t}$ have
chromatic number at most $d(t)$. Also, for each fixed $r$, by Theorem 8.2,
$r$-Coloring is polynomial-time solvable in $\mathcal{C}_{tt}$. Now by solving
$r$-Coloring for every $r\in\\{1,\dots,d(t)\\}$, we obtain a polynomial-time
algorithm for Coloring in $\mathcal{C}_{tt}$.

##  9\. Acknowledgments

We are grateful to Rose McCarty for many helpful discussions. We thank
Reinhard Diestel for being an invaluable source of information about tree
decompositions, and for his generosity with his time. We thank Irena Penev and
Kristina Vušković for telling us about important algorithmic problems whose
complexity was open for the class of even-hole free graphs.

## References

  * [1] T. Abrishami, M. Chudnovsky, and K. Vušković, “Induced subgraphs and tree decompositions I. Even-hole-free graphs of bounded degree.” J. Comb. Theory Ser. B, 157 (2022), 144–175.
  * [2] T. Abrishami, M. Chudnovsky, S. Hajebi and S. Spirkl “Induced subgraphs and tree decompositions III. Three paths configurations and logarithmic tree-width”. Advances in Combinatorics (2022).
  * [3] T. Abrishami, M. Chudnovsky, S. Hajebi and S. Spirkl “Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs” to appear in Electronic Journal of Combinatorics
  * [4] T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi and S. Spirkl “Induced subgraphs and tree decompositions VII. Basic obstructions in $H$-free graphs.” arXiv.org/abs/2212.02737 (2022)
  * [5] T. Abrishami, B. Alecu, M. Chudnovsky, S. Hajebi and S. Spirkl “Induced subgraphs and tree decompositions VIII. Excluding a forest in (theta, prism)-free graphs.” arXiv.org/abs/2301.02138 (2023)
  * [6] B. Alecu, M. Chudnovsky, S. Hajebi and S. Spirkl “Induced subgraphs and tree decompositions XI. Local structure for even-hole-free graphs of large treewidth.” manuscript
  * [7] P. Bellenbaum and R. Diestel, “Two short proofs concerning tree decompositions”, Combinatorics, Probability and Computing, 11 (2002) , 541–547
  * [8] H. Bodlaender and A. Koster. “Safe separators for treewidth.” Discrete Mathematics 306, 3 (2006), 337–350.
  * [9] V. Bouchitté, and I. Todinca. “Treewidth and minimal fill-in: Grouping the minimal separators.” SIAM Journal on Computing 31 (2001), 212–232.
  * [10] J. Carmesin, R. Diestel, M. Hamann, and F. Hundertmark. “$k$-Blocks: a connectivity invariant for graphs.” _SIAM Journal on Discrete Mathematics_ , 28(4), (2014) 1876–1891.
  * [11] J. Davies, “Vertex-minor-closed classes are $\chi$-bounded.” Combinatorica 42 (2022), 1049-1079.
  * [12] R. Diestel. Graph Theory. Springer-Verlag, Electronic Edition, (2005).
  * [13] P. Erdős and G. Szekeres. “A combinatorial problem in geometry.” Compositio Math 2 (1935), 463–470.
  * [14] D. Kühn and D. Osthus. “Induced subgraphs in $K_{s,s}$-free graphs of large average degree”, Combinatorica 24 (2004), 287–304.
  * [15] K. Menger, "Zur allgemeinen Kurventheorie". Fund. Math. 10 (1927) 96 – 115.
  * [16] N. Robertson and P.D. Seymour. “Graph minors. II. Algorithmic aspects of tree-width.” Journal of Algorithms 7(3) (1986): 309–322.
  * [17] A. Scott, private communication
  * [18] N.L.D. Sintiari and N. Trotignon. “(Theta, triangle)-free and (even-hole, $K_{4}$)-free graphs. Part 1: Layered wheels”, J. Graph Theory 97 (4) (2021), 475-509.
  * [19] K. Vušković, “Even-hole-free graphs: A survey.” Applicable Analysis and Discrete Mathematics, (2010), 219–240.
  * [20] D. Weißauer, “On the block number of graphs.” _SIAM J. Disc. Math._ 33, 1 (2019): 346–357.