Technische Universität Darmstadt<EMAIL_ADDRESS>darmstadt.dehttps://orcid.org/0000-0001-9191-1712The research leading to these
results has received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (EngageS:
grant agreement No. 820148).Technische Universität Darmstadt, Germany
rassmann@mathematik.tu-darmstadt.dehttps://orcid.org/0000-0003-1685-410X Irene
Heinrich and Simon Raßmann Theory of computation Fixed parameter tractability
Mathematics of computing Graph algorithms Mathematics of computing Paths and
connectivity problems IPEC 2023 IPEC 23

# Twin-width of graphs with tree-structured decompositions

Irene Heinrich  Simon Raßmann

###### Abstract

The twin-width of a graph measures its distance to co-graphs and generalizes
classical width concepts such as tree-width or rank-width. Since its
introduction in 2020 [13, 12], a mass of new results has appeared relating
twin width to group theory, model theory, combinatorial optimization, and
structural graph theory.

We take a detailed look at the interplay between the twin-width of a graph and
the twin-width of its components under tree-structured decompositions: We
prove that the twin-width of a graph is at most twice its strong tree-width,
contrasting nicely with the result of [7, 6], which states that twin-width can
be exponential in tree-width. Further, we employ the fundamental concept from
structural graph theory of decomposing a graph into highly connected
components, in order to obtain optimal linear bounds on the twin-width of a
graph given the widths of its biconnected components. For triconnected
components we obtain a linear upper bound if we add red edges to the
components indicating the splits which led to the components. Extending this
approach to quasi-4-connectivity, we obtain a quadratic upper bound. Finally,
we investigate how the adhesion of a tree decomposition influences the twin-
width of the decomposed graph.

###### keywords:

twin-width, quasi-4 connected components, strong tree-width

###### category:

##  1 Introduction

Twin-width is a new graph parameter introduced in [13, 12]. Since its
introduction it has gained considerable attention. The _twin-width_ 111We
refer to the preliminaries of this paper (subsections _graphs and trigraphs_
as well as _twin-width_) for an equivalent definition of twin-width which is
based on merging vertices instead of vertex subsets. of a graph $G$, denoted
by $\operatorname{tww}(G)$, is the minimum width over all contraction
sequences of $G$ and a _contraction sequence_ of $G$ is roughly defined as
follows: we start with a discrete partition of the vertex set of $G$ into $n$
singletons where $n$ is the order of $G$. Now we perform a sequence of $n-1$
merges, where in each step of the sequence precisely two parts are merged
causing the partition to become coarser, until eventually, we end up with just
one part – the vertex set of $G$. Two parts of a partition of $V(G)$ are
_homogeneously connected_ if either all or none of the possible cross edges
between the two parts are present in $G$. The red degree of a part is the
number of other parts to which it is not homogeneously connected. Finally, the
width of a contraction sequence is the maximum red degree amongst all parts of
partitions arising when performing the sequence.

In [13, 12] the authors show that twin-width generalizes other width
parameters such as rank-width, and, hence also clique-width and tree-width.
Furthermore, given a graph $H$, the class of $H$-minor free graphs has bounded
twin-width and FO-model checking is FPT on classes of bounded twin-width, see
[13, 12]. Many combinatorial problems which are NP-hard in general allow for
improved algorithms if the twin-width of the input graph is bounded from above
and the graph is given together with a width-minimal contraction sequence [9,
8].

#### Motivation.

To decompose a graph into smaller components and estimate a certain parameter
of the original graph from the parameters of its components is an
indispensable approach of structural graph theory, which serves in taming
branch-and-bound trees as well as for theoretical considerations because it
allows for stronger assumptions (i.e., high connectivity) on the considered
graphs. There are various ways to decompose a graph, e.g., bi-, tri-, or
quasi-4-connected components, tree decompositions of small adhesion (the
maximum cardinality of the intersection of to adjacent bags), modular
decomposition, or decomposition into the factors of a graph product.

So far there is no detailed analysis of the relation between the twin-width of
a graph and the twin-width of its biconnected, triconnected, or
quasi-4-connected components. The only result towards ($k$-)connected
components is the basic observation that the twin-width of a graph is
obviously the maximum over the twin-width over its ($1$-connected) components.
While there already exists a strong analysis of the interplay of tree-width
and twin-width (cf. [18, 19]), it is still open how twin-width behaves with
respect to the adhesion of a given tree decomposition, which can be
significantly smaller than the tree-width of a graph (as an example, consider
a graph whose biconnected components are large cliques – the adhesion is 1
whereas the tree-width is the maximum clique size). Further, there exist many
variants of tree-width, for example, strong tree-width [22, 16] for which the
interplay with twin-width has not yet been discussed in the literature.

#### Our results.

We prove the following bound on the twin-width of a graph:

######  Theorem 1.1.

If $G$ is a graph of strong tree-width $k$, then

$\operatorname{tww}(G)\leq\frac{3}{2}k+1+\frac{1}{2}(\sqrt{k+\ln
k}+\sqrt{k}+2\ln k).$

This is a strong contrast to the result of [7, 6] that twin-width can be
exponential in tree-width. We further provide a class of graphs which
asymptotically satisfies that the twin-width equals the strong tree-width.
Further, we investigate how to bound the twin-width of a graph in terms of the
twin-width of its highly connected components starting with biconnected
components.

######  Theorem 1.2.

If $G$ is a graph with biconnected components $C_{1},C_{2}\dots,C_{\ell}$,
then

$\max_{i\in[\ell]}\operatorname{tww}(C_{i})\leq\operatorname{tww}(G)\leq\max_{i\in[\ell]}\operatorname{tww}(C_{i})+2.$

Next, we consider decompositions into triconnected components:

######  Theorem 1.3.

Let $C_{1},C_{2},\dots,C_{\ell}$ be the triconnected components of a
2-connected graph $G$. For $i\in[\ell]$ we construct a trigraph
$\overline{C}_{i}$ from $C_{i}$ as follows: all virtual edges222That is, the
pairs of vertices along which $G$ was split to obtain the triconnected
components. of $C_{i}$ are colored red and all other edges remain black. If
$C_{i}$ contains parallel edges, then we remove all but one of the parallel
edges such that the remaining edge is red whenever one of the parallel edges
was red. Then

$\operatorname{tww}(G)\leq\max\left(8\max_{i\in[\ell]}\operatorname{tww}(\overline{C}_{i})+6,18\right).$

Similarly clean decompositions into $k$-connected graphs with $k>3$ cannot
exist [14, 15]; but we move on one more step and consider the twin-width of a
graph with respect to its quasi-4 connected components, introduced by [14,
15].

######  Theorem 1.4.

Let $C_{1},C_{2},\dots,C_{\ell}$ be the quasi-4-connected components of a
3-connected graph $G$.

  1. 1.

For $i\in[\ell]$ we construct a trigraph $\widehat{C}_{i}$ by adding for every
3-separator $S$ in $C_{i}$ along which $G$ was split a vertex $v_{S}$ which we
connect via red edges to all vertices in $S$. Then

$\operatorname{tww}(G)\leq\max\left(8\max_{i\in[\ell]}\operatorname{tww}(\widehat{C}_{i})+14,70\right).$

  2. 2.

For $i\in[\ell]$, we construct a trigraph $\overline{C}_{i}$ by coloring all
edges in 3-separators in $C_{i}$ along which $G$ was split red. Then

$\operatorname{tww}(G)\leq\max\left(4\max_{i\in[\ell]}\left(\operatorname{tww}(\overline{C}_{i})^{2}+\operatorname{tww}(\overline{C}_{i})\right)+14,70\right).$

For the general case of tree decompositions of bounded adhesion, we get the
following:

######  Theorem 1.5.

For every $k\in\mathbb{N}$ there exist explicit constants $D_{k}$ and
$D_{k}^{\prime}$ such that for every graph $G$ with a tree decomposition of
adhesion $k$ and parts $P_{1},P_{2},\dots,P_{\ell}$, the following statements
are satisfied:

  1. 1.

For each $P_{i}$, we construct a trigraph $\widehat{P}_{i}$ by adding for each
adhesion set $S$ in $P_{i}$ a new vertex $v_{S}$ which we connect via red
edges to all vertices in $S$. Then

$\operatorname{tww}(G)\leq
2^{k}\max_{i\in[\ell]}\operatorname{tww}(\widehat{P}_{i})+D_{k}.$

  2. 2.

Assume $k\geq 3$. For each $P_{i}$, we construct the torso $\overline{P}_{i}$
by completing every adhesion set in $P_{i}$ to a red clique. Then

$\operatorname{tww}(G)\leq\frac{2^{k}}{(k-1)!}\max_{i\in[\ell]}\operatorname{tww}(\overline{P}_{i})^{k-1}+D_{k}^{\prime}.$

Finally, we refine the result of [18, 19], where the authors bound the twin-
width of a graph given its tree-width.

######  Theorem 1.6.

Let $G$ be a graph with a tree decomposition of width $w$ and adhesion $k$.
Then

$\operatorname{tww}(G)\leq 3\cdot 2^{k-1}+\max(w-k-2,0).$

#### Bounding the red degree of decomposition trees.

The underlying structure of all the decompositions that we consider in this
paper is a tree. We generalize the optimal contraction sequence (cf. [3, 2])
for trees which works as follows: choose a root for the tree. If possible,
choose two sibling leaves and contract them (which implies a red edge from the
new vertex to its parent). Whenever a parent is joined to two of its leaf-
children via red edges, these two children are merged. This ensures that the
red degree of any parent throughout the whole sequence never exceeds 2. If
there are no sibling leaves, then choose a leaf of highest distance to the
root and contract it with its parent. This yields a red edge between the new
merged vertex and the former grandparent. Repeat this until we end up with a
singleton. We preserve this idea in our proofs to ensure that at no point in
time three distinct bag-siblings contribute to the red degree of the vertices
in their parent bag.

#### Further related work.

A standard reference on tree-width is [5]. For the basics on graph
connectivity and decomposition we refer text books on graph theory such as
[23]. The twin-width of a graph given the twin-width of its modular
decomposition factors (and in particular, also the twin-width given the width
of the factors of a lexicographical product) already has been investigated in
[11, 10]. In contrast to the linear-time solvable tree-width decision problem
[4] (for a fixed $k$: is the tree-width of the input graph at most $k$?),
deciding whether the twin-width of a graph is at most 4 is already NP-complete
[3, 2]. The twin-width of a graph in terms of its biconnected components has
already been considered in [20], where the author obtains a slightly weaker
upper bound than Theorem 1.2.

#### Organization of the paper.

We provide the preliminaries in Section 2. Our results on strong tree-width
can be found in Section 3. In Section 4 we prove new bounds on the twin-width
of a graph given the twin-widths of its highly connected components, and, we
generalize our approach to graphs which allow for a tree-decomposition of
small adhesion.

##  2 Preliminaries

For a natural number $n$, we denote by $[n]$ the $n$-element set
$\\{1,\dots,n\\}$. For a set $A$, we write $\mathcal{P}(A)$ for the power set
of $A$. For a natural number $k\leq|A|$, we write $\binom{A}{k}$ for the set
of $k$-element subsets of $A$.

#### Graphs and trigraphs.

All graphs in this paper are finite, undirected and contain no loops. For a
graph $G$, we denote its vertex set by $V(G)$ and its edge set by $E(G)$. We
write $|G|\coloneqq|V(G)|$ for the order of $G$.

A _trigraph_ is an undirected, edge-colored graph $G$ with disjoint sets
$E(G)$ of _black edges_ and $R(G)$ of _red edges_. We can interpret every
graph as a trigraph by setting $R(G)=\emptyset$. For a vertex subset $A$ of a
trigraph $G$, we denote by $G[A]$ the _subgraph induced on $A$_ and by $G-A$
the subgraph induced on $V(G)\setminus A$. For a vertex $v\in V(G)$, we also
write $G-v$ instead of $G-\\{v\\}$. If $G$ is a graph, then the _degree_ of a
vertex $v\in V(G)$ is denoted by $d_{G}(v)$ (or $d(v)$ if $G$ is clear from
context). For trigraphs, we write $\operatorname{red-deg}_{G}(v)$ for the _red
degree_ of $v$, i.e., the degree of $v$ in the graph $(V(G),R(G))$. We write
$\Delta(G)$ or $\Delta_{{\text{red}}}(G)$ for the maximum (red) degree of a
(tri-)graph $G$.

A _multigraph_ is a graph where we allow multiple edges between each pair of
vertices.

#### Twin-width.

Let $G$ be a trigraph and $x,y\in V(G)$ two distinct, not necessarily adjacent
vertices of $G$. We _contract $x$ and $y$_ by merging the two vertices to a
common vertex $z$, leaving all edges not incident to $x$ or $y$ unchanged,
connecting $z$ via a black edge to all common black neighbors of $x$ and $y$,
and via a red edge to all red neighbors of $x$ or $y$ and to all vertices
which are connected to precisely one of $x$ and $y$. We denote the resulting
trigraph by $G/{xy}$. A _partial contraction sequence_ of $G$ is a sequence of
trigraphs $(G_{i})_{i\in[k]}$ where $G_{1}=G$ and $G_{i+1}$ can be obtained
from $G_{i}$ by contracting two distinct vertices $x_{i},y_{i}\in V(G_{i})$.
By abuse of notation, we also call the sequence $(x_{i}y_{i})_{i<|G|}$ of
contraction pairs a partial contraction sequence. The width of a partial
contraction sequence is the maximal red degree of all graphs
$G_{1},\dots,G_{k}$. If the width of a sequence is at most $d$, we call it a
_$d$ -contraction sequence_. A _(complete) contraction sequence_ is a partial
contraction sequence whose final trigraph is the singleton graph on one
vertex. The minimum width over all complete contraction sequences of $G$ is
called the _twin-width_ of $G$ and is denoted by $\operatorname{tww}(G)$. We
often identify a vertex $v\in V(G)$ with the vertices in the graphs $G_{i}$
that $v$ gets contracted to and sets of vertices with the sets of vertices
they get contracted to.

Twin-width has many nice structural properties. For example, it is monotone
with respect to induced subgraphs: for every induced subgraph $H\subseteq G$
it holds that $\operatorname{tww}(H)\leq\operatorname{tww}(G)$. Moreover, the
twin-width of a disconnected graph is just the maximum twin-width of its
connected components.

#### Tree decompositions and tree-width.

Let $G$ be a graph. A _tree decomposition_ of $G$ is a pair
$\mathcal{T}=(T,\\{B_{i}\colon i\in V(T)\\})$ consisting of a tree $T$ and a
family $(B_{i})_{i\in V(T)}$ of subsets of $V(G)$, called _bags_ satisfying
the following conditions

  1. 1.

every vertex of $G$ is contained in some bag,

  2. 2.

for every vertex $v\in V(G)$, the set of tree vertices $i\in V(T)$ such that
$v\in B_{i}$ forms a subtree of $T$,

  3. 3.

for every edge $e\in E(G)$, there exists some bag which contains both
endpoints of $e$.

The subgraphs $G[B_{i}]$ are called the _parts_ of the tree decomposition. The
width of a tree-decomposition is $\max_{i\in V(T)}|B_{i}|-1$ and the minimum
width over all tree decompositions of $G$ is the _tree-width_ of $G$ and is
denoted by $\operatorname{tw}(G)$.

For an edge $ij\in E(T)$, the sets $B_{i}\cap B_{j}$ are the _adhesion sets_
or _separators_ of $\mathcal{T}$ and the maximal size of an adhesion set is
the _adhesion_ of $\mathcal{T}$. The graphs obtained from a part $G[B_{i}]$ by
completing all adhesion sets $B_{i}\cap B_{j}$ to cliques is called the
_torso_ of $G[B_{i}]$.

#### Strong tree-width.

Strong tree-width, which is also called tree-partition width, is a graph
parameter independently introduced by [22] and [16]. A _strong tree
decomposition_ of a graph $G$ is a tuple $(T,\\{B_{i}\colon i\in V(T)\\})$
where $T$ is a tree and $\\{B_{i}\colon i\in V(T)\\}$ is a set of pairwise
disjoint subsets of $V(G)$, one for each node of $T$ such that

  1. 1.

$V(G)=\bigcup_{i\in V(T)}B_{i}$ and

  2. 2.

for every edge $uv$ of $G$ there either exists a node $i\in V(T)$ such that
$\\{u,v\\}\subseteq B_{i}$ or there exist two adjacent nodes $i$ and $j$ in
$T$ with $u\in B_{i}$ and $v\in B_{j}$.

The sets $B_{i}$ are called _bags_ and $\max_{i\in V(T)}|B_{i}|$ is the
_width_ of the decomposition. The minimum width over all strong tree
decompositions of $G$ is the _strong tree-width_ $\operatorname{stw}(G)$ of
$G$.

The strong tree-width of a graph is bounded in its tree-width via
$\operatorname{tw}(G)\leq 2\operatorname{stw}(G)-1$, see [24]. In the other
direction, there is no bound: the strong-tree width of a graph is unbounded in
its tree-width [24]. However, it holds that $\operatorname{stw}(G)\in
O(\Delta(G)\cdot\operatorname{tw}(G))$, see [24]. Thus, for graphs of bounded
degree, the two width notions are linearly equivalent.

######  Remark 2.1.

In general, the strong tree-width is unbounded in the twin-width of a graph.
For example, consider a complete graph on $2n$ vertices. A width-minimal
strong tree decomposition of this graph has two bags, each containing $n$
vertices. However the twin-width of a complete graph is 0.

#### Highly connected components

A _cut vertex_ of a graph $G$ is a vertex $v\in V(G)$ such that $G-v$ contains
more connected components that $G$. A maximal connected subgraph of $G$ that
has no cut vertex is a _biconnected components_ of $G$. The _block-cut-tree_
of $G$ is a bipartite graph where one part is the set of biconnected
components of $G$ and the other part is the set of cut vertices of $G$ and a
biconnected component is joined to a cut vertex precisely if the vertex is
contained in the component. This graph is a forest, and even a tree if $G$ is
connected [23]. In terms of tree decomposition this can be rephrased as
follows: For every connected graph $G$ there exists a tree decomposition
$\mathcal{T}$ of $G$ such that $\mathcal{T}$ has adhesion at most $1$, and
every part is either $2$-connected or a complete graph of order $2$. Moreover,
the set of bags of this tree decomposition is isomorphism-invariant.

With respect to separators of order 2, the following result holds (see [17]):
For every $2$-connected graph, there exists a tree decomposition $\mathcal{T}$
of $G$ such that $\mathcal{T}$ has adhesion at most $2$, and the torso of
every bag is either $3$-connected, a cycle, or a complete graph of order $2$.
Moreover, the set of bags of this tree decomposition is isomorphism-invariant.

The _triconnected components of $G$_ are multigraphs constructed from the
torsos of this tree decomposition. In this work, these multigraphs are not
important and we also call the torsos themselves _triconnected components_.

A similarly clean decomposition into $4$-connected components arranged in a
tree-like fashion does not exist [14, 15]. This motivated Grohe to introduce
the notion of quasi-4-connectivity [14, 15]: A graph $G$ is
_quasi-4-connected_ if it is $3$-connected and all $3$-separators split off at
most a single vertex. That is, for every separator $S$ of size $3$, the graph
$G-S$ splits into exactly two connected components, at least one of which
consists of a single vertex. The prime example of quasi-4-connected graphs
which are not 4-connected are hexagonal grids. Also for quasi-4-connectivity
there is a tree-like decomposition into components:

######  Theorem 2.2 ([14, 15]).

For every $3$-connected graph $G$, there exists a tree decomposition
$\mathcal{T}$ of $G$ such that $\mathcal{T}$ has adhesion at most $3$, and the
torso of every bag is either quasi-4-connected or of size at most $4$.

The torsos of this tree decomposition are called _quasi-4-connected components
of $G$_.

##  3 Twin-width of graphs of bounded strong tree-width

See 1.1

######  Proof 3.1.

For a graph $H$ and a vertex subset $U\subseteq V(H)$ a partial contraction
sequence $s$ of $H$ is a _$U$ -contraction sequence_ if only vertices of $U$
are involved in the contractions in $s$ and $s$ is of length $|U|$, that is,
performing all contractions of $s$ yields a partition of $V(H)$ where $U$
forms one part and the rest of the parts are singletons. We denote the minimum
width over all $U$-contraction sequences of $H$ by
$\operatorname{tww}_{U}(H)$.

Let $\mathcal{T}=(T,\\{B_{i}\colon i\in V(T)\\})$ be a strong tree
decomposition of $G$ of width $k$. Fix $r\in V(T)$ and consider $T$ to be a
rooted tree with root $r$ from now on. If a bag $B_{i}$ contains only one
vertex $v$, then we set $v_{i}\coloneqq v$. We label all nodes $i$ of $T$ with
$|B_{i}|=1$ as _merged_. All other nodes of $T$ are labeled as _unmerged_. A
node $p$ of $T$ is a _leaf-parent_ if all of its children are leaves. If
$B_{i}$ is a bag of $\mathcal{T}$, then _contracting $B_{i}$_ means to apply a
width-minimal $B_{i}$-contraction sequence and then relabel $i$ as _merged_.
After a contraction of two vertices $u$ and $v$ to a new vertex $x$ we
_update_ the strong tree decomposition $\mathcal{T}$, that is, if $u$ and $v$
were contained in the same bag, then we simply replace $u$ and $v$ by $x$. If,
otherwise, $u$ and $v$ are contained in adjacent bags, then we remove $u$ and
$v$ from its bags and insert $x$ to the bag which is closer to the root. If
this causes an empty bag, we remove the bag as well as the corresponding tree-
vertex. Observe that updating preserves the strong tree-width.

1while  _$|V(T)|\geq 2$_ do

2 Choose a leaf $\ell$ which maximizes the distance to $r$

3 if  _the parent $p$ of $\ell$ has two merged children $\ell_{1},\ell_{2}$,_
then

4 contract $v_{\ell_{1}}$ with $v_{\ell_{2}}$,

5 update $\mathcal{T}$

6 if  _$\ell$ is the only child of its parent $p$ and $\ell$ is merged,_ then

7 contract $B_{p}$ and denote the resulting vertex $b_{p}$,

8 contract $b_{p}$ with $v_{\ell}$,

9 update $\mathcal{T}$

10 if  _amongst $\ell$ and its siblings there is an unmerged leaf
$\ell^{\prime}$ and at most one merged leaf, _ then

11 contract $B_{\ell^{\prime}}$,

12 update $\mathcal{T}$

13

Apply a width-minimal contraction sequence to the remaining graph.

Algorithm 1 Contract($G$, $\mathcal{T}=(T,\\{B_{i},i\in V(T)\\})$)

We claim that the algorithm Contract merges $G$ into a single vertex via a
contraction sequence of the required width.

First, we check that that the algorithm terminates. Observe that the root $r$
is not part of any of the contractions in the while-loop. In particular, as
long as the loop is executed, there exists at least one leaf-parent. In every
iteration of the loop at least one of the if-conditions is satisfied and
hence, $|V(G)|$ shrinks with every iteration, which proves that the algorithm
terminates with a singleton graph, that is, it provides a contraction
sequence.

It remains to bound the width of the sequence. For $a\in\mathbb{N}$ we set

$f(a)\coloneqq(a+\sqrt{a+\ln a}+\sqrt{a}+2\ln a)/2.$

We will exploit the result of [18, 19] that an $a$-vertex graph has twin-width
at most $f(a)$.

Let $(G_{i})_{i\leq|G|}$ be the contraction obtained by the algorithm. Fix
$i\in[|G|]$ and $v\in G_{i}$ and let $\mathcal{T}_{i}=(T_{i},\mathcal{B}_{i})$
be the strong tree decomposition corresponding to $G_{i}$ and $B_{j}$ the bag
containing $v$ in $\mathcal{T}$.

If $j$ is neither a leaf, nor in a leaf-parent, nor the parent of a leaf-
parent in $T_{i}$, then $\operatorname{red-deg}(v)=0$.

Assume that $j$ is a leaf of $T_{i}$, then all red edges incident to $v$ are
either internal edges of $B_{j}$ or joining $v$ with a vertex of $B_{p}$ where
$p$ is the parent of $j$ in $T_{i}$. Since $\operatorname{stw}(G)\leq k$ there
are at most $k$ red edges of the latter form. Internal red edges of a bag may
only arise during a the contraction of this leaf-bag in Line 1. Since the
corresponding partial contraction sequence is chosen to be width-minimal and
by the bound of [18, 19] we obtain that $\operatorname{red-deg}_{G_{i}}(v)\leq
k+f(k)$.

Now assume that $j$ is a leaf-parent in $T_{i}$. If the bag $B_{j}$ of
$\mathcal{T}_{i}$ was already contained in $\mathcal{T}$, then there are no
internal red edges in $B_{j}$ and the only red edges incident to $v$ are
incident to the vertices of precisely one leaf-bag, or, to the vertices of
precisely two leaf-bags one of which is merged. In each of the two cases, the
red degree of $v$ in $G_{i}$ is bounded by $k+1$. Otherwise $B_{j}$ is
obtained during the contraction in Line 1. In this case, $j$ has precisely one
child $\ell$ in $T_{i}$ and $\ell$ is merged. Hence, $j$ has at most
$k+f(k)+1$ red neighbors.

Finally, assume that $j$ is neither a leaf nor a leaf-parent but parent of a
leaf-parent in $T_{i}$. Let $j_{1},\dots,j_{h}$ be the children of $j$ in
$T_{i}$. Observe that there are at most two children of $j$, say, $j_{1}$ and
$j_{2}$ such that $v$ is joined to vertices of the corresponding bags and
there are no internal red edges in $B_{j}$. The only red edges incident to $v$
are arsing during the contraction of $B_{j_{1}}$ or $B_{j_{2}}$ in Line 1.
Since first, one of the two children is contracted to one vertex before any
contraction in the other bag happens, the red degree of $v$ is bounded by
$k+1$.

######  Lemma 3.2.

There exists a family of graphs $(H_{n})_{n\in\mathbb{N}}$ such that
$\lim_{n\to\infty}\frac{\operatorname{tww}(H_{n})}{\operatorname{stw}(H_{n})}\geq
1$.

######  Proof 3.3.

For each $n\in\mathbb{N}$ let $H_{n}$ be the $n$-th Paley graph. Fix
$n\in\mathbb{N}$. It is known that
$\operatorname{tww}(H_{n})=\frac{|V(H_{n})|-1}{2}$, see [18, 19]. By
distributing the vertices of $H_{n}$ to two bags, one of cardinality
$\frac{|V(H_{n})|+1}{2}$, the other one of cardinality
$\frac{|V(H_{n})|-1}{2}$, we obtain a strong tree decomposition of $H_{n}$ of
width $\frac{|V(H_{n})|+1}{2}$.

##  4 Twin-width of graphs with small separators

###  4.1 Biconnected components

We start our investigation of graphs of small adhesion by proving a bound on
the twin-width of graphs in terms of the twin-width of their biconnected
components. This proof contains many of the ideas we will generalize later to
deal with tri- and quasi-4-connected components as well as general graphs with
a tree decomposition of bounded adhesion.

The main obstacle to constructing contraction sequences of a graph from
contraction sequences of its biconnected components is that naively
contracting one component might increase the red degree of the incident cut
vertices in the neighboring components arbitrarily. Thus, we need to find
contraction sequences of the biconnected components not involving the incident
cut vertices.

Let $G$ be a trigraph and $\mathcal{P}$ be a partition of $G$. Denote by
$G/\mathcal{P}$ the trigraph obtained from $G$ by contracting each part of
$\mathcal{P}$ into a single vertex. For a vertex $v\in V(G)$ we denote by
$\mathcal{P}(v)$ the part of $\mathcal{P}$ that contains $v$. If
$\mathcal{P}(v)\neq\\{v\\}$, then we obtain a refined partition
$\mathcal{P}_{v}$ by replacing $\mathcal{P}(v)$ in $\mathcal{P}$ by the two
parts $\mathcal{P}(v)$ and $\\{v\\}$. Otherwise, we set
$\mathcal{P}_{v}=\mathcal{P}$. Since $G/\mathcal{P}$ can be obtained from
$G/\mathcal{P}_{v}$ by at most one contraction, and one contraction of a
trigraph reduces the maximum red degree by at most $1$ we have

$\Delta_{\text{red}}(G/\mathcal{P}_{v})\leq\Delta_{\text{red}}(G/\mathcal{P})+1.$
(1)

######  Lemma 4.1.

For every trigraph $G$ and every vertex $v\in V(G)$,

$\operatorname{tww}_{V(G-v)}(G)\leq\operatorname{tww}(G)+1.$

######  Proof 4.2.

Let $(\mathcal{P}^{(i)})_{i\in[|G|]}$ be a sequence of partitions
corresponding to a width-minimal contraction sequence of $G$. Further, let $j$
be the maximal index with $\\{v\\}\in\mathcal{P}^{(j)}$. Then
$(\mathcal{P}^{(i)})_{i\in[j]}$ is a partial
$\operatorname{tww}(G)$-contraction sequence which does not involve $v$, and
by (1) the sequence $(\mathcal{P}^{(i)}_{v})_{i\in[|G|]\setminus[j+1]}$ is a
partial $(\operatorname{tww}(G)+1)$-contraction sequence which contracts the
resulting trigraph until $v$ and one further vertex remain. Combining these
two sequences yields the claim.

See 1.2

######  Proof 4.3.

The lower bound follows from the fact that all biconnected components are
induced subgraphs of $G$ together with the monotonicity of twin-width.

For the upper bound we may assume that $G$ is connected since the twin-width
of a disconnected graph is the maximum twin-width of its connected components
[13, 12]. Consider the block-cut-tree of $G$, i.e., the tree $T$ whose vertex
set is the union of the biconnected components of $G$ and the cut vertices of
$G$, where every cut vertex joined to precisely those biconnected components
containing it. In particular, the biconnected components and the cut vertices
form a bipartition of $T$.

We choose a cut vertex $r$ as a root of $T$. For every biconnected components
$C\in V(T)$, we let $v_{C}$ be the parent of $C$ in $T$.

To make our argument simpler, let $\widehat{G}$ be the graph obtained from $G$
by joining a new vertex $r_{v}$ to every vertex $v\in V(G)$ via a red edge.
Similarly, for a biconnected component $C$, we let $\widehat{C}$ be the graph
obtained from $C$ by attaching a new vertex $r_{v}$ to every vertex $v$ of
$C$. For each cut vertex $c$, we let $\widehat{G}_{c}$ be the graph induced by
$\widehat{G}$ on the union of all blocks in the subtree $T_{c}$ of $T$ rooted
at $c$ together with all vertices $r_{v}$ adjacent to these blocks.

We show that
$\operatorname{tww}(\widehat{G})\leq\max_{i\in[\ell]}\operatorname{tww}(C_{i})+2$.
The claim then follows since $G$ is an induced subgraph of $\widehat{G}$.

######  Claim 1.

For every biconnected component $C$ of $G$,

$\operatorname{tww}_{V(\widehat{C}-v_{C})}(\widehat{C})\leq\operatorname{tww}(C)+2.$

######  Proof 4.4 (Proof of the Claim.).

By applying Lemma 4.1 to $C$ and $v_{C}$, we find a $V(C-v_{C})$-contraction
sequence $S$ of $C$ of width at most $\operatorname{tww}(C)+1$. We show how
this contraction sequence can be adapted to also contract the vertices $r_{v}$
for all cut vertices $v$ incident to $C$. Indeed, before every contraction
$vw$ of $S$, we insert the contraction of $r_{v}$ and $r_{w}$. This keeps the
invariant that we never contract a vertex from $C$ with a vertex $r_{v}$, and
further, every vertex of $C$ is incident to at most one vertex $r_{v}$ (or a
contraction of those vertices). Moreover, the red degree among the vertices
$r_{v}$ also stays bounded by $2$. The entire partial contraction sequence
constructed so far thus has width at most $\operatorname{tww}(C)+2$.

After applying this sequence, we end up with at most four vertices: $v_{C}$,
$r_{v_{C}}$, the contraction of $C-v_{C}$ and the contraction of all vertices
$r_{v}$ for vertices $v\neq v_{C}$. As $r_{v_{C}}$ is only connected to
$v_{C}$ and the contraction of all other vertices $r_{v}$ is not connected to
$v_{C}$, these four vertices form a path of length four. Thus, the contraction
sequence can be completed with trigraphs of width at most $2$.‘

Now, consider again the whole graph $\widehat{G}$ and choose a leaf block $C$
of $T$. We can apply the partial contraction sequence given by the previous
claim to $\hat{C}$ in $\hat{G}$. Because we never contract $v_{C}$ with any
other vertex, this does not create red edges anywhere besides inside
$\hat{C}$. Thus, it is still a partial $(\operatorname{tww}(C)+2)$-contraction
sequence of $\widehat{G}$. Moreover, the resulting trigraph is isomorphic to
$\widehat{G}-V(\widehat{C}-v_{C})$, i.e., the graph obtained from
$\widehat{G}$ by just removing the biconnected component $C$ (but leaving the
cut vertex $v_{C}$). By iterating this, we can remove all biconnected
components one after the other using width at most
$\max_{i\in[\ell]}\operatorname{tww}(C_{i})+2$. Finally, we end up with just
two vertices: The root cut vertex $r$, together with its red neighbor $r_{r}$,
which we can simply contract.

Note that the bounds in Theorem 1.2 are sharp even on the class of trees: the
biconnected components of a tree are just its edges which have twin-width $0$.
As there are trees both of twin-width $0$ and of twin-width $2$, both the
upper and the lower bound can be obtained.

######  Corollary 4.5.

Let $\mathcal{C}$ be a graph class closed under taking biconnected components.
Then $\mathcal{C}$ has bounded twin-width if and only if the subclass of
$2$-connected graphs in $\mathcal{C}$ has.

######  Proof 4.6.

Since every biconnected component is either $2$-connected or a bridge, we can
bound the twin-width of every graph via the maximum twin-width of a
$2$-connected biconnected component.

Moreover, Theorem 1.2 also reduces the algorithmic problem of computing or
approximating the twin-width of a graph to within some factor to the
corresponding problem on 2-connected graphs.

######  Remark 4.7.

Note that in contrast to the case of connected components, where the twin-
width of a graph is determined by the twin-widths of its components, the twin-
width of a connected graph is not determined by the multiset of its
biconnected components. As an example, consider a tree of twin-width $2$ and a
star with the same number of edges of twin-width $0$. Then both graphs have
the same biconnected components, but different twin-width.

###  4.2 Apices and contractions respecting subsets

To deal with adhesion sets of size at least $2$, it no longer suffices to find
contraction sequences of the parts that just don’t contract vertices in the
adhesion sets. Indeed, as those vertices can appear parts corresponding to a
subtree of unbounded depth, this could create an unbounded number of red edges
incident to vertices in adhesion sets. Instead, we want contraction sequences
that create no red edges incident to any vertices of adhesion sets.

For a trigraph $G$ and a set of vertices $A\subseteq V(G)$ of red degree $0$,
we say that a partial sequence of $d$-contractions
$G=G_{0},G_{1},\dots,G_{\ell}$ _respects $A$_ if $G_{i}[A]=G[A]$ and
$\operatorname{red-deg}_{G_{i}}(a)=0$ for all $i\leq\ell$ and $a\in A$. Thus,
for every contraction $xy$ in the sequence, we have $x,y\notin A$ and
$N(x)\cap A=N(y)\cap A$, which implies that the vertices in $A$ are not
incident to any red edges all along the sequence.

A _complete $d$-contraction sequence respecting $A$_ is a sequence of
$d$-contractions that respects $A$ of maximal length, i.e., one whose
resulting trigraph $G_{\ell}$ does not allow a further contraction respecting
$A$. This is equivalent to no two vertices in $V(G_{\ell})\setminus A$ having
the same neighborhood in $A$. In particular, a complete contraction sequence
respecting $A$ leaves at most $2^{|A|}$ vertices besides $A$.

We write $\operatorname{tww}(G,A)$ for the minimal $d$ such that there exists
a complete $d$-contraction sequence respecting $A$. For a single vertex $v\in
V(G)$, we also write $\operatorname{tww}(G,v)$ for
$\operatorname{tww}(G,\\{v\\})$. Note that
$\operatorname{tww}(G)=\operatorname{tww}(G,\emptyset)$.

It was proven in [13, 12, Theorem 2] that adding a single apex to a graph of
twin-width $d$ raises the twin-width to at most $2d+2$. The proof given there
readily works in our setting without any modifications.

######  Theorem 4.8.

Let $G$ be a trigraph, $v\in V(G)$ a vertex not incident to any red edges and
$A\subseteq V(G)\setminus\\{v\\}$ a set of vertices. Then

$\operatorname{tww}(G,A\cup\\{v\\})\leq 2\operatorname{tww}(G-v,A)+2.$

######  Corollary 4.9.

Let $G$ be a trigraph and $A\subseteq V(G)$ a subset of vertices with
$\operatorname{red-deg}(a)=0$ for all vertices $a\in A$. Then

$\operatorname{tww}(G,A)\leq 2^{|A|}\operatorname{tww}(G)+2^{|A|+1}-2.$

######  Proof 4.10.

We proceed by induction on $|A|$. For $|A|=0$, the claim is immediate. Thus,
write $A=A_{0}\mathbin{\dot{\cup}}\\{a\\}$ and assume the claim is true for
$A_{0}$. Theorem 4.8 and the induction hypothesis yield

$\displaystyle\operatorname{tww}(G,A)=\operatorname{tww}(G,A_{0}\cup\\{a\\})$
$\displaystyle\leq 2\operatorname{tww}(G-a,A_{0})-2$ $\displaystyle\leq
2\left(2^{|A_{0}|}\operatorname{tww}(G-A)+2^{|A_{0}|+1}-2\right)-2$
$\displaystyle=2^{|A|}\operatorname{tww}(G-A)+2^{|A|+1}-2$ $\displaystyle\leq
2^{|A|}\operatorname{tww}(G)+2^{|A|+1}-2.$

###  4.3 Tree decompositions of small adhesion

We are now ready to generalize the linear bound on the twin-width of a graph
in terms of its biconnected components to allow for larger separators of
bounded size. This is most easily expressed in terms of tree decompositions of
bounded adhesion.

In all of the following two sections, let $G$ be a graph,
$\mathcal{T}=((T,r),\\{B_{t}\colon t\in V(T)\\})$ a rooted tree decomposition
with adhesion $k\geq 1$.

For a vertex $t\in V(T)$, we write $P_{t}\coloneqq G[B_{t}]$ for the part
associated to $t$. For a vertex $t\in V(T)$ with parent $s\in V(T)$ we write
$S_{t}\coloneqq B_{t}\cap B_{s}$ and call $S_{t}$ the _parent separator_ of
$P_{t}$ or a _child separator_ of $P_{s}$. Moreover, we set
$S_{r}\coloneqq\emptyset$ to be the _root separator_. For a tree vertex $t\in
V(T)$, we write $T_{t}$ for the subtree of $T$ with root $t$, $G_{t}\coloneqq
G[\bigcup_{s\in V(T_{t})}B_{s}]$ for the corresponding subgraph and
$\mathcal{T}_{t}$ for the corresponding tree decomposition of $G_{t}$.

We can assume w.l.o.g. that every two vertices $s,t\in V(T)$ with
$S_{s}=S_{t}$ are siblings. Indeed, if they are not, let $s^{\prime}$ be a
highest vertex in the tree with parent separator $S_{s}$ and construct another
tree decomposition by attaching all vertices $t$ with $S_{t}=S_{s}$ directly
to the parent of $s^{\prime}$ instead of their old parent. By repeating this
procedure if necessary, we obtain the required property.

For a vertex $t\in T$ with children $c_{1},\dots,c_{\ell}$, we set
$N_{c_{i}}\coloneqq\\{N(v)\cap S_{c_{i}}\colon v\in V(G_{c_{i}})\setminus
S_{c_{i}}\\}$ to be the set of (possibly empty) neighborhoods that vertices in
$G_{c_{i}}-S_{c_{i}}$ have in the separator $S_{c_{i}}$ (and thus in $P_{t}$).
We now define a trigraph $\widetilde{P}_{t}$ with vertex set

$V(\widetilde{P}_{t})\coloneqq
V(P_{t})\mathbin{\dot{\cup}}\\{s^{c_{i}}_{M}\colon i\in[\ell],M\in
N_{c_{i}}\\}.$

We will often abuse notation and also denote the set $\\{s^{c_{i}}_{M}\colon
M\in N_{c_{i}}\\}$ by $N_{c_{i}}$.

We define the edge set of $\widetilde{P}_{t}$ such that

  1. 1.

$\widetilde{P}_{t}[V(P_{t})]=P_{t}$,

  2. 2.

$\widetilde{P}_{t}[N_{c_{i}}]$ is a red clique for every $i$,

  3. 3.

$s^{c_{i}}_{M}$ is connected via black edges to all vertices in $M$,

and there are no further red or black edges. Note that in $\widetilde{P}_{t}$,
there are no red edges incident to any vertices in $P_{t}$ and thus in
particular not to any vertices in $S_{t}$. A drawing of the gadget attached to
$S_{c_{i}}$ in $\widetilde{P}_{t}$ in comparison with the simpler gadgets we
will reduce to later can be seen in Figure 1.

$P_{t}$$\widetilde{P}_{t}$$\widehat{P}_{t}$$\overline{P}_{t}$ Figure 1: A
separator $S_{t^{\prime}}$ on three (square) vertices together with the three
versions of gadgets we attach to it. Dashed edges represent either edges or
non-edges. In $\widetilde{P}_{t}$, we add a red clique consisting of one
vertex for every neighborhood of vertices in $G_{t^{\prime}}-S_{t^{\prime}}$
in $S_{t^{\prime}}$. In $\widehat{P}_{t}$, we only add a single vertex with
red edges to all vertices in $S_{t^{\prime}}$. In $\overline{P}_{t}$, we add
no new vertices but complete all child separators to red cliques.

######  Lemma 4.11.

Let $G$ and $\mathcal{T}$ be as above. For every $t\in V(T)$, it holds that

$\operatorname{tww}(G_{t},S_{t})\leq\max_{s\in
V(T_{t})}\operatorname{tww}(\widetilde{P}_{s},S_{s}).$

In particular, $\operatorname{tww}(G)\leq\max\limits_{s\in
V(T)}\operatorname{tww}(\widetilde{P}_{s},S_{s})\leq 2^{k}\max\limits_{s\in
V(T)}\operatorname{tww}(\widetilde{P}_{s})+2^{k+1}-2$.

######  Proof 4.12.

We proceed by induction on the height of $t$ in the tree $T$. If $t$ is a
leaf, then $G_{t}=P_{t}=\widetilde{P}_{t}$ and we can use a contraction
sequence of $\widetilde{P}_{t}$ respecting $S_{t}$.

Thus, assume that $t$ is not a leaf and assume the claim is true for all
vertices of $T$ below $t$. Let $c_{1},\dots,c_{\ell}$ be the children of $t$
in $T$. By the induction hypothesis,

$\operatorname{tww}(G_{c_{i}},S_{c_{i}})\leq\max_{s\in
V(T_{c_{i}})}\operatorname{tww}(\widetilde{P}_{s},S_{s})\leq\max_{s\in
V(T_{t})}\operatorname{tww}(\widetilde{P}_{s},S_{s}).$

Thus, we find complete contraction sequences of all $G_{c_{i}}$ respecting
$S_{c_{i}}$ within the required width bounds. Because the graphs $G_{c_{i}}$
and $G_{c_{j}}$ for distinct $i$ and $j$ only intersect in $S_{c_{i}}\cap
S_{c_{j}}$, which are not contracted, we do not create red edges between the
different graphs $G_{c_{i}}$ nor between these graphs and their parent
separators. Thus, we can combine these contraction sequences without exceeding
our width bounds. This results in the graph $\widetilde{P}_{t}$, where
possibly some red edges are still black. We can thus in a final step apply a
contraction sequence of $\widetilde{P}_{t}$ respecting $S_{t}$.

The second claim follows by applying the first claim to $t=r$ and then
applying Corollary 4.9.

If $\mathcal{T}$ has bounded width, we can proceed as in [18, 19, Lemma 3.1]
to bound the twin-width of the graphs $\widetilde{P}_{t}$ and thus the twin-
width of $G$:

######  Lemma 4.13.

Let $G$ and $\mathcal{T}$ be as above and additionally assume that
$\mathcal{T}$ has width at most $w$. For every $t\in V(T)$, it holds that

$\operatorname{tww}(\widetilde{P}_{t},S_{t})\leq 3\cdot
2^{k-1}+\max(w-k-2,0).$

######  Proof 4.14.

We first note that the red degree of $\widetilde{P}$ itself is bounded by
$2^{k}-1$.

Now, let $c_{1},\dots,c_{\ell}$ be the (possibly empty) list of children of
$t$ in $T$. We first find a contraction sequence of
$\bigcup_{i=1}^{\ell}N_{c_{i}}$ respecting $S_{t}$. For this, we argue by
induction that $\bigcup_{i=1}^{j-1}N_{c_{i}}$ can be contracted while
preserving the required width. This claim is trivial for $j=1$. Hence assume
we have already contracted $\bigcup_{i=1}^{j-1}N_{c_{i}}$ to a set $B_{j-1}$
of size at most $2^{|S_{P}|}$. The vertices of $B_{j-1}$ may be connected via
red edges to vertices in $B_{j-1}$ itself and in $P_{t}\setminus S_{t}$. Thus,
the red degree of vertices in $B_{j-1}$ is bounded by

$|B_{j-1}|-1+|P_{t}|-|S_{t}|\leq 2^{|S_{t}|}+|P_{t}|-|S_{t}|-1\leq
2^{k}+w-k-1,$

while the red degree of vertices in $P_{t}\setminus S_{t}$ is bounded by
$|B_{j}|\leq 2^{|S_{t}|}\leq 2^{k}$.

Now, we first apply a maximal contraction sequence of $N_{c_{j}}$ respecting
$S_{t}$ resulting in a quotient $\bar{N}_{c_{j}}$. Because of our assumption
on the tree decomposition $\mathcal{T}$, we know that $S_{t}\neq S_{c_{j}}$
for all $j\in[\ell]$. In particular, this implies that $|S_{c_{j}}\cap
S_{t}|<k$. and thus $|\bar{N}_{c_{j}}|\leq 2^{k-1}$. During this contraction
sequence, there can appear red edges between the contracted vertices of
$N_{c_{j}}$ and vertices in $P_{t}\setminus S_{t}$. The vertices of
$N_{c_{j}}$ thus have red degree bounded by $|N_{c_{j}}|-1+|P_{t}|-|S_{t}|\leq
2^{k}+w-k-1$. Every red neighbor of vertices in $P_{t}\setminus S_{t}$ in a
quotient of $N_{c_{j}}$ must be the contraction of at least two vertices of
$N_{c_{j}}$. Thus, the red degree of these vertices is bounded by

$|B_{j-1}|+|N_{c_{j}}|/2\leq 2^{k}+2^{k-1}=3\cdot 2^{k-1}.$

Next, we contract vertices from $B_{j-1}$ and $\bar{N}_{c_{j}}$ which have
equal neighborhoods in $S_{t}$. As our bounds already allow every vertex in
$P_{t}\setminus S_{t}$ to be connected via red edges to all of
$B_{j-1}\cup\bar{N}_{c_{j}}$, it suffices to argue that this keeps the red
degree of vertices in $B_{j-1}\cup\bar{N}_{c_{j}}$ within our bounds. But this
set has size at most $3\cdot 2^{k-1}$. Hence, after one contraction, the red
degree is bounded by

$|B_{j-1}|+|\bar{N}_{c_{j}}|-2+|P_{t}|-|S_{t}|\leq 3\cdot 2^{k-1}+w-k-2.$

We have now successfully contracted $N_{c_{j}}$ into $B_{j-1}$ while keeping
the red degree bounded by

$\max(2^{k}+w-k-1,2^{k},3\cdot 2^{k-1},3\cdot 2^{k-1}+w-k-2)=3\cdot
2^{k-1}+\max(w-k-2,0).$

By repeating this procedure for all $j\in[\ell]$, we find a contraction
sequence of $\bigcup_{i=1}^{\ell}N_{c_{i}}$ respecting $S_{t}$ within this
width. The resulting graph thus consists of $S_{t}$, the vertices of
$P_{t}\setminus S_{t}$ and the vertices from $B_{\ell}$. In total, these are
at most $2^{|S_{t}|}+|P_{t}|-|S_{t}|\leq 2^{k}+w-k$ vertices besides those in
$S_{t}$. These can further be contracted while keeping the red degree bounded
by

$2^{k}+w-k-1\leq 3\cdot 2^{k-1}+w-k-2.$

In total, our contraction sequence thus has width at most $3\cdot
2^{k-1}+\max(w-k-2,0),$ proving the claim.

By combining Lemma 4.13 with Lemma 4.11, we obtain a general bound on the
twin-width of graphs admitting a tree decomposition of bounded width and
adhesion: See 1.6

This upper bounds sharpens the bound given in [18, 19] by making explicit the
dependence on the adhesion of the tree decomposition. Our bound shows that,
while the twin-width in general can be exponential in the tree-width [7, 6],
the exponential dependence comes from the adhesion of the tree decomposition
and not from the width itself.

Moreover, our bound is asymptotically sharp. As already mentioned, it is known
that there are graphs whose twin-width is exponential in the adhesion of some
tree decomposition [7, 6]. By adding into some bag a Paley graph whose twin-
width is linear in its size [1], we also achieve asymptotic sharpness in the
linear width term.

###  4.4 Simplifying the parts

Before we apply this general lemma to the special case of the tree of bi-,
tri- or quasi-4-connected components, we show that we can simplify the gadgets
attached in the graphs $\widetilde{P}$ to all separators while raising the
twin-width by at most a constant factor.

In a first step, we replace the sets $N_{c_{i}}$ from the definition of the
parts $\widetilde{P}_{t}$ by a single common red neighbor for every separator.
For every vertex $t\in V(T)$ with children $c_{1},\dots,c_{\ell}$, we define
the trigraph $\widehat{P}_{t}$ as follows: we set
$\mathcal{S}(t)\coloneqq\\{S_{c_{i}}\colon i\in[\ell],S_{c_{i}}\not\subsetneq
S_{c_{j}}\text{ for all }j\in[\ell]\\}$ to be the set of subset-maximal child
separators of $P_{t}$. Now, we take a collection of fresh vertices
$V_{S}\coloneqq\\{v_{S}\colon S\in\mathcal{S}(t)\\}$ and set

$V(\widehat{P}_{t})\coloneqq V(P_{t})\mathbin{\dot{\cup}}V_{S}.$

The subgraph induced by $\widehat{P}_{t}$ on $V(P_{t})$ is just $P_{t}$
itself. The vertex $v_{S}$ is connected via red edges to all vertices in $S$
and has no further neighbors. A drawing of the gadget attached to $S_{c_{i}}$
in $\widehat{P}_{t}$ can be found in Figure 1.

######  Lemma 4.15.

Let $G$ and $\mathcal{T}$ be as before. Then for every $t\in V(T)$, it holds
that

$\operatorname{tww}(\widetilde{P}_{t},S_{t})\leq\max(2^{k}\operatorname{tww}(\widehat{P}_{t})+2^{k+1}-2,4^{k}+2^{k}-2).$

In particular, $\operatorname{tww}(G)\leq\max(2^{k}\max_{t\in
V(T)}\operatorname{tww}(\widehat{P}_{t})+2^{k+1}-2,4^{k}+2^{k}-2).$

######  Proof 4.16.

Consider a separator $S\in\mathcal{S}(t)$ in the graph $\widetilde{P}$ and
assume $t$ has more than one child $c$ with $S_{c}\subseteq S$. If $c$ and
$c^{\prime}$ are such children, we can contract vertices from $N_{c}$ and
$N_{c^{\prime}}$ with the same neighborhood in $S$ as long as these exist. By
doing this for all children whose parent separator is contained in $S$, we can
reduce to the case that there is only a single such child using a contraction
sequence of width at most $2^{k+1}-2$. Thus, in the following assume that
$S_{c}\not\subseteq S_{c^{\prime}}$ for every two distinct children $c$ and
$c^{\prime}$ of $t$.

By Corollary 4.9, it holds that
$\operatorname{tww}(\widetilde{P}_{t},S_{t})\leq
2^{k}\operatorname{tww}(\widetilde{P}_{t})+2^{k+1}-2$. Thus, we want to bound
$\operatorname{tww}(\widetilde{P}_{t})$.

For this, let $c_{1},\dots,c_{\ell}$ be the children of $t$ and choose a
vertex $x_{i}\in N_{c_{i}}$ for every $i\in[\ell]$. We show that we can
contract all vertices of $N_{c_{i}}$ into $x_{i}$ one after the other in such
a way that the red degree of $x_{i}$ stays bounded by $2^{k}-1$ while we do
not create red edges between vertices of $P$ and vertices of $N_{c_{i}}$
besides $x_{i}$.

Indeed, let $S_{c_{i}}=\\{s_{1},\dots,s_{k^{\prime}}\\}$. If $k^{\prime}<k$,
then we can contract the vertices of $N_{c_{i}}$ into $x_{i}$ in an arbitrary
way while keeping the red degree bounded by $2^{k^{\prime}}+k^{\prime}\leq
2^{k}-1$. Hence, assume $k^{\prime}=k$. Now, let $M\coloneqq N(x_{i})\cap
S_{c_{i}}$ be the neighborhood of $x_{i}$ in the separator $S_{c_{i}}$ and
define $M_{j}\coloneqq M\mathbin{\triangle}\\{s_{1},\dots,s_{j}\\}$. For all
$j\in[k]$, there exists at most one vertex $y_{j}\coloneqq
s^{c_{i}}_{M_{j}}\in N_{c_{i}}$ such that $N(y_{j})\cap S_{c_{i}}=M_{j}$. We
first show that we can contract the vertices $y_{1},\dots,y_{k}$ into $x_{i}$
one after the other without exceeding our bound of $2^{k}-1$. For this, we
note that after having contracted $y_{1},\dots,y_{j}$ into $x_{i}$, the
remaining red neighbors of $x_{i}$ are among
$\\{s_{1},\dots,s_{j}\\}\cup(N_{c_{i}}\setminus\\{x_{i},y_{1},\dots,y_{j}\\})$.
Now, whether or not $y_{j}$ exists, the exclusion of $y_{j}$ removes one of
the possible $2^{|S_{c_{i}}|}$ many vertices in $N_{c_{i}}$. Thus, $x_{i}$ has
at most $(2^{k}-1)$-many red neighbors.

After having merged $y_{1},\dots,y_{j}$ into $x_{i}$, this possible
neighborhood includes all the vertices in $S_{c_{i}}$. Thus, we can now
contract the remaining vertices of $N_{c_{i}}$ in an arbitrary way without
exceeding the bound of $2^{k}-1$ on the red degree of $x_{i}$.

By applying this procedure for all $i\in[\ell]$, we find a contraction
sequence which contracts $\widetilde{P}_{t}$ to $\widehat{P}_{t}$ using width
at most $2^{k}-1$. Thus, we have

$\operatorname{tww}(\widetilde{P}_{t})\leq\max(2^{k}-1,\operatorname{tww}(\widehat{P}_{t})).$

In total, we thus have

$\displaystyle\operatorname{tww}(\widetilde{P}_{t},S_{t})$
$\displaystyle\leq\max\left(2^{k+1}-2,2^{k}\operatorname{tww}(\widetilde{P}_{t})+2^{k+1}-2\right)$
$\displaystyle\leq\max\left(2^{k+1}-2,2^{k}\max(2^{k}-1,\operatorname{tww}(\widehat{P}_{t}))+2^{k+1}-2\right)$
$\displaystyle=\max(2^{k+1}-2,4^{k}+2^{k}-2,2^{k}\operatorname{tww}(\widehat{P}_{t})+2^{k-1}-2)$
$\displaystyle=\max(4^{k}+2^{k}-2,2^{k}\operatorname{tww}(\widehat{P}_{t})+2^{k-1}-2)$

The second claim follows from Lemma 4.11 together with the observation that
$\operatorname{tww}(G)=\operatorname{tww}(G,S_{r})$ for the root separator
$S_{r}=\emptyset$ of $\mathcal{T}$.

Next, we want to define a version $\overline{P}_{t}$ of the parts which does
not need extra vertices in $P_{t}$ but instead marks the separators via red
cliques. Indeed, let $\overline{P}_{t}$ be the trigraph obtained from $P_{t}$
by completing each of the sets $S\in\mathcal{S}_{t}$ to a red clique. Thus,
the underlying graphs of the trigraphs $\overline{P}_{t}$ are just the
_torsos_ of the tree decomposition. We thus call the graphs $\overline{P}_{t}$
the _red torsos_ of the tree decomposition $\mathcal{T}$.

In order to obtain a bound on the twin-width of $G$ in terms of the twin-width
of the torsos $\overline{P}_{t}$, we need one combinatorial lemma, which is a
variant of Sperner’s theorem [21].

######  Lemma 4.17.

Let $\mathcal{F}\subseteq\mathcal{P}([n])$ be a family of subsets of $[n]$
such that every set has size at most $k$ and no set is contained in another.

  1. 1.

If $k\leq\lfloor n/2\rfloor$, then $|\mathcal{F}|\leq\binom{n}{k}$.

  2. 2.

If $k>\lfloor n/2\rfloor$, then $|\mathcal{F}|\leq\binom{n}{\lfloor
n/2\rfloor}\leq\binom{2k-1}{k}$.

######  Proof 4.18.

By the LYM-inequality [21], it holds that

$\sum_{A\in\mathcal{F}}\frac{1}{\binom{n}{|A|}}\leq 1.$

Furthermore, we also know that

$\sum_{A\in\mathcal{F}}\frac{1}{\binom{n}{|A|}}\geq|\mathcal{F}|\cdot\frac{1}{\max_{i\leq
k}\binom{n}{i}}=\begin{cases}\frac{|\mathcal{F}|}{\binom{n}{k}}&\text{if
}k\leq\lfloor n/2\rfloor,\\\ \frac{|\mathcal{F}|}{\binom{n}{\lfloor
n/2\rfloor}}&\text{if }k>\lfloor n/2\rfloor.\\\ \end{cases}$

Combining these two inequalities yields everything but the very last
inequality of the claim. This inequality follows from the fact that when
$k>\lfloor n/2\rfloor$, then we also have $k>n/2$ and thus $n\leq 2k-1$.

######  Corollary 4.19.

Let $H$ be a graph, $\mathcal{F}\subseteq\mathcal{P}(V(H))$ and $k\geq 2$ such
that

  1. 1.

every set in $\mathcal{F}$ contains at most $k$ vertices,

  2. 2.

no two sets in $\mathcal{F}$ are contained in each other, and

  3. 3.

for each $A\in\mathcal{F}$, the graph $G[A]$ is a clique.

Then every $x\in V(H)$ is contained in at most
$\max\left(\binom{\Delta(H)}{k-1},\binom{2k-3}{k-1}\right)$ sets of
$\mathcal{F}$.

######  Proof 4.20.

Consider a vertex $x\in V(H)$. If $\\{x\\}\in\mathcal{F}$, then $x$ cannot be
contained in any further sets of $\mathcal{F}$. and is thus only contained in
$1\leq\binom{2k-3}{k-1}$ sets.

Thus, assume that $\\{x\\}\notin\mathcal{F}$ and consider the family
$\mathcal{F}_{-x}\coloneqq\\{A\setminus\\{x\\}\colon A\in\mathcal{F},x\in
A\\}$, whose cardinality is the number we want to bound. All sets in
$\mathcal{F}_{-x}$ are subsets of $N_{H}(x)$, have size at most $k-1$ and do
not contain any other set in $\mathcal{F}_{-x}$. Thus, Lemma 4.17 yields that

$|\mathcal{F}_{-x}|\leq\max\left(\binom{|N_{H}(x)|}{k-1},\binom{2k-3}{k-1}\right)\leq\max\left(\binom{\Delta(H)}{k-1},\binom{2k-3}{k-1}\right).$

######  Lemma 4.21.

For every $t\in V(T)$, it holds that

$\operatorname{tww}(\widehat{P}_{t})\leq\max\left(k+1,\operatorname{tww}(\overline{P}_{t})+\binom{\operatorname{tww}(\overline{P}_{t})}{k-1},\operatorname{tww}(\overline{P}_{t})+\binom{2k-3}{k-1}\right).$

In particular,

$\displaystyle\operatorname{tww}(G)\leq\max\left(\begin{array}[]{l}2^{k}\max_{t\in
V(T)}\left(\operatorname{tww}(\overline{P}_{t})+\binom{\operatorname{tww}(\overline{P}_{t})}{k-1}\right)+2^{k+1}-2,\\\
2^{k}\max_{t\in
V(T)}\operatorname{tww}(\overline{P}_{t})+2^{k}\binom{2k-3}{k-1}+2^{k+1}-2,\\\
4^{k}+2^{k}-2\end{array}\right)$

######  Proof 4.22.

For $k=1$ the claim is true. Thus, we assume in the following that $k\geq 2$.
Let $(x_{i}y_{i})_{i<|\overline{P}_{t}|}$ be a minimal contraction sequence of
$\overline{P}_{t}$, which we can also interpret as a contraction sequence of
$P_{t}$. We want to construct from the sequence
$(x_{i}y_{i})_{i<|\overline{P}_{t}|}$ a contraction sequence of
$\widehat{P}_{t}$, which can be found in Algorithm 2.

1for  _$i <|\widehat{P}_{t}|$_ do

2 while  _there exist distinct vertices $v_{S}$ and $v_{S^{\prime}}$ in the
quotient of $V_{S}$ such that $N(v_{S})/{x_{i}y_{i}}\subseteq
N(v_{S^{\prime}})/{x_{i}y_{i}}$ _ do

3 contract $v_{S}$ and $v_{S^{\prime}}$

4 contract $x_{i}$ and $y_{i}$

contract the remaining two vertices

Algorithm 2 Contract($\widehat{P}_{t}$, $(x_{i}y_{i})_{i<|\overline{P}_{t}|})$

To see that this contraction sequence does indeed contract $\widehat{P}_{t}$
to a single vertex, note that after having exited the for-loop, we have
applied all contractions $x_{i}y_{i}$, which means that $P_{t}$ was contracted
to a single vertex. But then each two vertices $v_{S}$ and $v_{S^{\prime}}$ in
the quotient of $V_{S}$ have identical neighborhood in $V(P_{t})$, which means
that they were contracted before.

Now, in order to bound the width of this sequence, we first argue that we
preserve the loop-invariant that at the beginning of Line 2, no two vertices
$v_{S}$ and $v_{S^{\prime}}$ have neighborhoods that contain each other. In
the uncontracted graph $\widehat{P}_{t}$, this is true by construction, as we
only added a vertex $v_{S}$ for every subset-maximal child separator $S$. If
the invariant is true at the start of the $i$-th iteration, then the process
in the while-loop precisely ensures that the property is also true at the
start of the $(i+1)$-th iteration.

Next, we argue that the red-degree of all vertices $v_{S}$ is bounded by $k$
at the beginning of each iteration and bounded by $k+1$ during the whole
sequence. Moreover, at the start of each iteration, the neighborhood of each
vertex $v_{S}$ is a red clique. Again, this is true by construction in the
uncontracted graph $\widehat{P}_{t}$. If this invariant is true at the
beginning of the $i$-th iteration, we show that it is also true at the
beginning of the $(i+1)$-th iteration. For this, we note that whenever we
contract a vertex $v_{S}$ into a vertex $v_{S^{\prime}}$ because
$N_{v_{S}}/{x_{i}y_{i}}\subseteq N_{v_{S^{\prime}}}/{x_{i}y_{i}}$, then both
neighborhoods contain either $x_{i}$ or $y_{i}$ (or both) and both $x_{i}$ and
$y_{i}$ are contained in one of the two neighborhoods. Thus, the neighborhood
of the contracted vertex contains both $x_{i}$ and $y_{i}$ and its size is
bounded by $|N_{v_{S^{\prime}}}\cup\\{x_{i},y_{i}\\}|\leq k+1$. Moreover, when
contracting the vertices $x_{i}$ and $y_{i}$ in
$N_{v_{S^{\prime}}}\cup\\{x_{i},y_{i}\\}$, then we get a red clique.

It remains to bound the red degree of the vertices in (the quotients of)
$P_{t}$. For this, we note that during the while-loop of Algorithm 2, the red
degree of vertices in $P_{t}$ can only decrease. Thus, it suffices to bound
the red degree at the start of each iteration. The red neighbors of vertices
in $P_{t}$ come in two sorts: red neighbors in $P_{t}$ itself, stemming from
the contraction sequence $(x_{i}y_{i})_{i<|\overline{P}_{t}|}$, and red
neighbors among the vertices in $V_{S}$.

The red degree that a vertex $x$ in $P_{t}$ can obtain within $P_{t}$ is
bounded by the width of the sequence $(x_{i}y_{i})_{i<|\overline{P}_{t}|}$
which is $\operatorname{tww}(\overline{P}_{t})$. To bound the red degree that
a vertex $x$ in $P_{t}$ can get from vertices in $V_{S}$, let $Q_{i}$ be the
partially contracted graph that we have at the start of the $i$-th iteration
and set $\mathcal{F}_{i}\coloneqq\\{N_{Q}(v_{S})\colon v_{S}\in V_{S}\\}$. By
Corollary 4.19, the number of red neighbors of $x$ among the vertices $v_{S}$
is bounded by

$\max\left(\binom{\Delta_{{\text{red}}}(Q_{i})}{k-1},\binom{2k-3}{k-1}\right)\leq\max\left(\binom{\operatorname{tww}(\overline{P}_{t})}{k-1},\binom{2k-3}{k-1}\right).$

Combining these bounds, we get that the red degree of the contraction sequence
of $\widehat{P}_{t}$ is bounded by

$\max\left(k+1,\operatorname{tww}(\overline{P}_{t})+\binom{\operatorname{tww}(\overline{P}_{t})}{k-1},\operatorname{tww}(\overline{P}_{t})+\binom{2k-3}{k-1}\right).$

The second claim follows by inserting this bound into the bound in Lemma 4.15.

Combining Lemma 4.15 and Lemma 4.21, we get the following two asymptotic
bounds on the twin-width of a graph admitting a tree decomposition of small
adhesion.

######  Theorem 1.5.

For every $k\in\mathbb{N}$ there exist explicit constants $D_{k}$ and
$D_{k}^{\prime}$ such that for every graph $G$ with a tree decomposition of
adhesion $k$ and parts $P_{1},P_{2},\dots,P_{\ell}$, the following statements
are satisfied:

  1. 1.

$\displaystyle\operatorname{tww}(G)\leq
2^{k}\max_{i\in[\ell]}\operatorname{tww}(\widehat{P}_{i})+D_{k}$,

  2. 2.

if $k\geq 3$, then
$\displaystyle\operatorname{tww}(G)\leq\frac{2^{k}}{(k-1)!}\max_{i\in[\ell]}\operatorname{tww}(\overline{P}_{i})^{k-1}+D_{k}^{\prime}$.

###  4.5 Tri- and quasi-4-connected components

We now want to apply these general results on the interplay between twin-width
and tree decompositions of small adhesion to obtain bounds on the twin-width
of graphs in terms of the twin-width of their tri- and quasi-4-connected
components.

######  Theorem 1.3.

Let $C_{1},C_{2},\dots,C_{\ell}$ be the triconnected components of a
2-connected graph $G$. If we write $\overline{C}_{i}$ for the red torsos of
the triconnected components $C_{i}$, then

$\operatorname{tww}(G)\leq\max\left(8\max_{i\in[\ell]}\operatorname{tww}(\overline{C}_{i})+6,18\right).$

######  Proof 1.3.

This follows from Lemma 4.21 applied to the tree of triconnected components of
$G$ together with the observation that for $k=2$, the second term in the
maximum in Lemma 4.21 is always bounded by the maximum of the first and third
term.

Note that in Theorem 1.3 we cannot hope for a lower bound similar to the lower
bound in Theorem 1.2 without dropping the virtual edges. Indeed, consider a
$3$-connected graph $G$ of large twin-width (e.g. Paley graphs or Rook’s
graphs). By [3, 2], a $(2\lceil\log(|G|)\rceil-1)$-subdivision $H$ of $G$ has
twin-width at most $4$, but its triconnected components are $G$ and multiple
long cycles. Thus, there exist graphs of twin-width at most $4$ with
triconnected components of arbitrarily large twin-width.

Moreover, the red virtual edges in each separator can also not be replaced by
black edges.

######  Lemma 4.24.

There exists a family of graphs $(G_{n})_{n\in\mathbb{N}}$ with unbounded
twin-width such that the twin-width of the class of triconnected components of
$G_{n}$ with black virtual edges is bounded.

######  Proof 4.25.

Let $G_{n}$ be the graph obtained from a clique $K_{n}$ by subdividing every
edge once. The triconnected components of this graph are the $K_{n}$ and a
$K_{3}$ for every edge of the $K_{n}$, which all have twin-width $0$.

In order to show that the twin-width of the family $(G_{n})_{n\in\mathbb{N}}$
is unbounded, we show that for every $d\geq 2$ and $n\geq(d+1)\binom{d}{2}+1$,
we have $\operatorname{tww}(G_{n})>d$. For this, consider any $d$-contraction
sequence of $G_{n}$ for $n\geq(d+1)^{2}+2$ and let $\mathcal{P}$ be the
partition of $V(G_{n})$ right before the first contraction in the sequence
that does not contract two subdivision vertices. We show that every partition
class $P\in\mathcal{P}$ has size at most $\binom{d}{2}$. As no subdivision
vertices were contracted so far, we only need to consider classes of
subdivision vertices. Thus, let $P=\\{v_{e_{1}},\dots,v_{e_{\ell}}\\}$ be such
a class, where $e_{1},\dots,e_{\ell}\in\binom{V(K_{n})}{2}$ are edges of the
original $K_{n}$. If the edges $e_{i}$ all have a common endpoint, then $P$
has red edges to all $\ell$ other endpoints of these edges, meaning that
$\ell\leq d\leq\binom{d}{2}$. Otherwise, $P$ has red edges to all endpoints of
all $e_{i}$. If $\ell>\binom{d}{2}$, these have to be more that $d$, which is
a contraction. Thus, $|P|=\ell\leq\binom{d}{2}$.

Now, let $xy$ be the next contraction in the sequence. If neither $x$ nor $y$
is a subdivision vertex, then $G_{n}$ contains precisely $2(n-2)$-many
vertices which are connected to either $x$ or $y$ but not both. In the
contracted graph, the contraction would thus create at least
$\frac{2(n-2)}{\binom{d}{2}}\geq d+1$ red edges incident to the contracted
vertex. If, on the other hand, either $x$ or $y$ is a subdivision vertex but
the other is not, then $x$ and $y$ have no common neighbors. But as non-
subdivision vertices have degree $n-1$ in $G_{n}$, contracting these two would
create at least $\frac{n-1}{\binom{d}{2}}\geq d+2$ red edges incident to the
contracted vertex. Thus, no further contraction keeps the red degree of the
sequence bounded by $d$, which implies $\operatorname{tww}(G_{n})>d$.

In the case of separators of size $3$, we get two bounds on the twin-width of
a graph in terms of its quasi-4-connected components: one linear bound in
terms of the subgraphs induced on the quasi-4-connected components together
with a common red neighbor for every $3$-separator along which the graph was
split, and one quadratic bound in terms of the (red) torsos of the
quasi-4-connected components.

######  Theorem 1.4.

Let $C_{1},C_{2},\dots,C_{\ell}$ be the quasi-4-connected components of a
3-connected graph $G$.

  1. 1.

For $i\in[\ell]$ we construct a trigraph $\widehat{C}_{i}$ by adding for every
3-separator $S$ in $C_{i}$ along which $G$ was split a vertex $v_{S}$ which we
connect via red edges to all vertices in $S$. Then

$\operatorname{tww}(G)\leq\max\left(8\max_{i\in[\ell]}\operatorname{tww}(\widehat{C}_{i})+14,70\right).$

  2. 2.

For $i\in[\ell]$, denote by $\overline{C}_{i}$ the _red torso_ of the
quasi-4-connected component $C_{i}$. Then

$\operatorname{tww}(G)\leq\max\left(4\max_{i\in[\ell]}\left(\operatorname{tww}(\overline{C}_{i})^{2}+\operatorname{tww}(\overline{C}_{i})\right)+14,70\right).$

######  Proof 1.4.

The two claims follow from Lemma 4.15 and Lemma 4.21 applied to the tree of
quasi-4-connected components of $G$ [14, 15] together with the observation
that also for $k=3$, the second term in the maximum in Lemma 4.21 is always
bounded by the maximum of the first and third term.

##  5 Conclusion and further research

We proved that
$\operatorname{tww}(G)\leq\frac{3}{2}k+1+\frac{1}{2}(\sqrt{k+\ln
k}+\sqrt{k}+2\ln k)$ if $G$ is a graph of strong tree-width at most $k$
(Theorem 1.1). Moreover, we demonstrated that asymptotically the twin-width of
a Paley graph agrees with its strong tree-width (Lemma 3.2).

We provided a detailed analysis of the relation between the twin-width of a
graph and the twin-width of its highly connected components. Concerning
2-connected graphs, there is a tight linear upper bound on the twin-width of a
graph given the twin-width of its biconnected components (Theorem 1.2). There
is a linear upper bound for a slightly modified version of triconnected
components (Theorem 1.3). By further providing a quadratic upper bound on the
twin-width of graph given the twin-widths of its modified quasi-4-connected
components (Theorem 1.4) we took one important step further to complete the
picture of the interplay of the twin-width of a graph with the twin-width of
its highly connected components. As a natural generalization of the above
decompositions we considered graphs allowing for a tree decomposition of small
adhesion (Theorem 1.5 and Theorem 1.6).

It seems worthwhile to integrate our new bounds for practical twin-width
computations, for example, with a branch-and-bound approach.

## References

  * [1] Jungho Ahn, Kevin Hendrey, Donggyu Kim, and Sang-il Oum.  Bounds for the Twin-Width of Graphs.  SIAM Journal on Discrete Mathematics, 36(3):2352–2366, 2022.  doi:10.1137/21M1452834.
  * [2] Pierre Bergé, Édouard Bonnet, and Hugues Déprés.  Deciding twin-width at most 4 is np-complete.  CoRR, abs/2112.08953, 2021.  URL: https://arxiv.org/abs/2112.08953, arXiv:2112.08953.
  * [3] Pierre Bergé, Édouard Bonnet, and Hugues Déprés.  Deciding Twin-Width at Most 4 Is NP-Complete.  In Mikołaj Bojańczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), volume 229 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1–18:20, Dagstuhl, Germany, 2022\. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2022/16359, doi:10.4230/LIPIcs.ICALP.2022.18.
  * [4] Hans L. Bodlaender.  A linear-time algorithm for finding tree-decompositions of small treewidth.  SIAM J. Comput., 25(6):1305–1317, 1996.  URL: https://doi.org/10.1137/S0097539793251219, doi:10.1137/S0097539793251219.
  * [5] Hans L. Bodlaender.  A partial _k_ -arboretum of graphs with bounded treewidth.  Theor. Comput. Sci., 209(1-2):1–45, 1998.  URL: https://doi.org/10.1016/S0304-3975(97)00228-4, doi:10.1016/S0304-3975(97)00228-4.
  * [6] Édouard Bonnet and Hugues Déprés.  Twin-width can be exponential in treewidth.  CoRR, abs/2204.07670, 2022.  URL: https://doi.org/10.48550/arXiv.2204.07670, arXiv:2204.07670, doi:10.48550/arXiv.2204.07670.
  * [7] Édouard Bonnet and Hugues Déprés.  Twin-width can be exponential in treewidth.  J. Comb. Theory, Ser. B, 161:1–14, 2023.  URL: https://doi.org/10.1016/j.jctb.2023.01.003, doi:10.1016/j.jctb.2023.01.003.
  * [8] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width III: max independent set and coloring.  CoRR, abs/2007.14161, 2020.  URL: https://arxiv.org/abs/2007.14161, arXiv:2007.14161.
  * [9] Édouard Bonnet, Colin Geniet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width III: max independent set, min dominating set, and coloring.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, 48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference), volume 198 of LIPIcs, pages 35:1–35:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.35, doi:10.4230/LIPIcs.ICALP.2021.35.
  * [10] Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, and Stéphan Thomassé.  Twin-width VI: the lens of contraction sequences.  CoRR, abs/2111.00282, 2021.  URL: https://arxiv.org/abs/2111.00282, arXiv:2111.00282.
  * [11] Édouard Bonnet, Eun Jung Kim, Amadeus Reinald, and Stéphan Thomassé.  Twin-width VI: the lens of contraction sequences.  In Joseph (Seffi) Naor and Niv Buchbinder, editors, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, VA, USA, January 9 - 12, 2022, pages 1036–1056. SIAM, 2022.  URL: https://doi.org/10.1137/1.9781611977073.45, doi:10.1137/1.9781611977073.45.
  * [12] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  CoRR, abs/2004.14789, 2020.  URL: https://arxiv.org/abs/2004.14789, arXiv:2004.14789.
  * [13] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: tractable FO model checking.  J. ACM, 69(1):3:1–3:46, 2022.  URL: https://doi.org/10.1145/3486655, doi:10.1145/3486655.
  * [14] Martin Grohe.  Quasi-4-connected components.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 8:1–8:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016.  URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.8, doi:10.4230/LIPIcs.ICALP.2016.8.
  * [15] Martin Grohe.  Quasi-4-connected components.  CoRR, abs/1602.04505, 2016.  URL: http://arxiv.org/abs/1602.04505, arXiv:1602.04505.
  * [16] R. Halin.  Tree-partitions of infinite graphs.  97(1):203–217.  doi:10.1016/0012-365X(91)90436-6.
  * [17] John E. Hopcroft and Robert Endre Tarjan.  Dividing a graph into triconnected components.  SIAM J. Comput., 2:135–158, 1973.
  * [18] Hugo Jacob and Marcin Pilipczuk.  Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs.  In Michael A. Bekos and Michael Kaufmann, editors, Graph-Theoretic Concepts in Computer Science - 48th International Workshop, WG 2022, Tübingen, Germany, June 22-24, 2022, Revised Selected Papers, volume 13453 of Lecture Notes in Computer Science, pages 287–299. Springer, 2022.  URL: https://doi.org/10.1007/978-3-031-15914-5_21, doi:10.1007/978-3-031-15914-5\\_21.
  * [19] Hugo Jacob and Marcin Pilipczuk.  Bounding twin-width for bounded-treewidth graphs, planar graphs, and bipartite graphs.  CoRR, abs/2201.09749, 2022.  URL: https://arxiv.org/abs/2201.09749, arXiv:2201.09749.
  * [20] Gonne Kretschmer.  Calculating twin-width of graphs, 2023.
  * [21] D. Lubell.  A short proof of sperner’s lemma.  Journal of Combinatorial Theory, 1(2):299, 1966.  doi:10.1016/S0021-9800(66)80035-2.
  * [22] D. Seese.  Tree-partite graphs and the complexity of algorithms.  In Lothar Budach, editor, Fundamentals of Computation Theory, Lecture Notes in Computer Science, pages 412–421. Springer.  doi:10.1007/BFb0028825.
  * [23] Douglas Brent West et al.  Introduction to graph theory, volume 2.  Prentice hall Upper Saddle River, 2001.
  * [24] David R. Wood.  On tree-partition-width.  30(5):1245–1253.  doi:10.1016/j.ejc.2008.11.010.