# Bounded twin-width graphs are polynomially $\chi$-bounded

Romain Bourneuf  École Normale Supérieure de Lyon, LIP, F-69342, LYON Cedex
07, France.  Stéphan Thomassé  Univ Lyon, EnsL, UCBL, CNRS, LIP, F-69342, LYON
Cedex 07, France.

###### Abstract

We show that every graph with twin-width $t$ has chromatic number
$O(\omega^{k_{t}})$ for some integer $k_{t}$, where $\omega$ denotes the
clique number. This extends a quasi-polynomial bound from Pilipczuk and
Sokołowski and generalizes a result for bounded clique-width graphs by Bonamy
and Pilipczuk. The proof uses the main ideas of the quasi-polynomial approach,
with a different treatment of the decomposition tree. In particular, we
identify two types of extensions of a class of graphs: the delayed-extension
(which preserves polynomial $\chi$-boundedness) and the right-extension (which
preserves polynomial $\chi$-boundedness under bounded twin-width condition).
Our main result is that every bounded twin-width graph is a delayed extension
of simpler classes of graphs, each expressed as a bounded union of right
extensions of lower twin-width graphs.

##  1 Introduction

One of the first questions regarding the chromatic number $\chi(G)$ of a graph
$G$ is how it compares to the clique number $\omega(G)$. Indeed, while
$\omega(G)\leq\chi(G)$, early constructions by Blanche Descartes, Zykov and
Mycielski show that there are triangle-free graphs with arbitrarily large
$\chi$. This question was also one of the key-motivations for the introduction
of the probabilistic method by Erdős, to get randomized constructions of
graphs with large girth and large chromatic number.

###  1.1 Polynomial $\chi$-bounded classes

A hereditary class $\cal C$ of graphs (or just _class_ in this paper, i.e.
closed under induced subgraphs) is _$\chi$ -bounded_ if there exists a
function $f$ such that $\chi(G)\leq f(\omega(G))$ for every $G\in\cal C$. For
instance, the celebrated class of _perfect graphs_ is the (hereditary) class
of graphs such that $f(x)=x$. When $f$ can be chosen as a polynomial, the
class $\cal C$ is _polynomially $\chi$-bounded_. Let us also say that $\cal C$
is _$k$ -initially $\chi$-bounded_ if $f(i)$ exists for all $i\leq k$. Very
recently, Carbonero, Hompe, Moore and Spirkl [5] showed that for all $k$,
there are classes which are $k$-initially $\chi$-bounded but not
$\chi$-bounded. Notably, there are classes which are $\chi$-bounded but not
polynomially $\chi$-bounded, see Briański, Davies and Walczak [4]. The field
is developing at a very fast pace: for a recent survey, see Scott and Seymour
[13].

Polynomial $\chi$-boundedness is one of the tamest behaviours a class can
have. The simplest case is the case of perfect graphs, which can be defined by
forbidden induced subgraphs (odd holes and antiholes) as well as they enjoy
some structural results based on some elementary decompositions. This leads to
three main directions of research: Which forbidden induced subgraphs give
polynomial $\chi$-boundedness? Which structural parameters give polynomial
$\chi$-boundedness? Which operations preserve $\chi$-boundedness? These three
questions are intimately connected. The most natural example of polynomially
$\chi$-bounded class, cographs, are altogether $P_{4}$-free graphs, have
clique-width at most 2 and are the closure under substitutions of graphs of
size at most 2.

From the forbidden induced subgraph perspective, the Perfect Graph Theorem,
proved by Chudnovsky, Robertson, Seymour and Thomas [7] is definitely the
masterpiece of the field. One of the most influential questions in the domain
was proposed by Gyárfás and Sumner: is the class of graphs excluding some
fixed induced tree $\chi$-bounded? This is true for paths, but the
$\chi$-bounding function is not known to be polynomial. Scott, Seymour and
Spirkl [15] showed that sparse graphs excluding a tree are polynomially
$\chi$-bounded. Liu, Schroeder, Wang and Yu showed it for $t$-broom free
graphs [10]. Davies and McCarty [8] proved that circle graphs are polynomially
$\chi$-bounded.

From the point of view of operations preserving (polynomial)
$\chi$-boundedness, the landscape is less developed. Even deciding if modules
can be safely contracted requires a careful argument. To this end, Chudnovsky,
Penev, Scott, and Trotignon [6] showed that if a class is polynomially
$\chi$-bounded, its closure under substitutions is also polynomially
$\chi$-bounded. They also raised the problem of simultaneously authorizing two
closures: Do substitutions and small cuts preserve $\chi$-boundedness? To our
knowledge, this question is still open. Dvořák and Král’ also showed in [9]
that closure by bounded rank cuts also preserves $\chi$-boundedness. For this,
they introduced a new tree-decomposition which is reminiscent of our delayed
decomposition tree.

###  1.2 Twin-width

With the exception of VC-dimension, classes of graphs with bounded complexity
parameter are usually $\chi$-bounded. This is the case for bounded tree-width,
as it implies bounded degeneracy, but also the case for rank-width, as shown
in [9]. Building on this result, Bonamy and Pilipczuk [1] showed that graphs
with bounded clique-width are polynomially $\chi$-bounded.

Twin-width was introduced by in [3] as a new structural complexity measure,
capturing at the same time minor-closed classes, strict classes of
permutations and bounded clique-width classes. It was shown in [2] that graphs
with bounded twin-width are $\chi$-bounded. In the same paper, a polynomial
bound was posed as an open problem, which would extend the polynomial
$\chi$-boundedness of graphs with bounded clique-width [1].

A natural step when trying to achieve polynomial bounds is to first look for
quasi-polynomial ones, that is of order $n^{\log^{c}n}$. For instance,
$P_{5}$-free graphs are quasi-polynomially $\chi$ bounded, see [14]. Reaching
quasi-polynomiality often requires the right tools and definitions, and adding
a little bit more of structure can sometimes save the logarithmic term. This
paper is no exception, as the fundamental idea (a reduction to lower twin-
width), was already proposed by Pilipczuk and Sokołowski [12]. Their twin-
width reduction is based on a clever definition, $d$-almost mixed minors,
which are particularly well-behaved for induced subgraphs.

Their idea is to use the fact that twin-width is functionally equivalent to
finding a particular vertex ordering $v_{1},\dots,v_{n}$ for which the
adjacency matrix cannot be partitioned into $k\times k$ mixed blocks, see [3].
Here mixed means that there are at least two distinct rows and two distinct
columns. However, this definition is too constrained and they relaxed it by
lifting the condition for the diagonal blocks ($k$-almost mixed minors). The
difficult technical part of their approach is to partition $G$ into some
restrictions $G[v_{i},\dots,v_{j}]$ which do not “contain” a $k-1$-almost
mixed minor, in order to apply induction. The “containment” notion is a very
clever mix of edge-partition and vertex-quotient. This is the central
reduction of their argument.

Our proof also uses this reduction and inserts it inside a different analysis
of the decomposition tree.

###  1.3 Overview of the proof

The first step is to consider a decomposition tree analogous to the
substitution tree used for modules. The idea is simple: we first start with
the partition

$\\{\\{v_{1},\ldots,v_{\lceil n/2\rceil}\\},\\{v_{\lceil
n/2\rceil+1},\ldots,v_{n}\\}\\}$

and we greedily continue to partition every part $B$ into modules with respect
to the outside of $B$. If we reach a real module, we cut it in half and
iterate. We now have a decomposition tree $T_{d}$ whose leaves are vertices.

The next step is to observe that we can structure $T_{d}$ (i.e. associate a
graph $g(x)$ to every internal node $x$) so that the information $(T,g)$ is
enough to retrieve $G$. This is our _delayed decomposition_. The key-fact is
that if the class of graphs $g(x)$ is polynomially $\chi$-bounded, one can
derive polynomial $\chi$-boundedness for $G$. This does not involve twin-width
and is a general decomposition method: delayed extensions preserve
(polynomial) $\chi$-boundedness.

When $G$ is $k$-almost-mixed free, we can argue as in [12] that all $g(x)$ are
“simpler”. Here again, we encapsulate the argument into a general framework,
_right extensions_ , for which we prove that they preserve $\chi$-boundedness
for all graphs, and polynomial $\chi$-boundedness for bounded twin-width
graphs.

To sum up our approach: we show that $d$-almost mixed free graphs are delayed
extensions of (vertex and edge unions of) right extensions of $d-1$-almost
mixed free graphs and bounded $\chi$ graphs.

###  1.4 Future directions

In this paper, we stress the roles of two main operations: delayed extensions
and right extensions, which apply to general graphs. Whether they can be used
for other classical problems on $\chi$-boundedness is left for future
research.

The fact that delayed extensions preserve polynomial $\chi$-boundedness
directly results from the stability of polynomial $\chi$-boundedness by
substitution. Since we crucially need it, we take a closer look at the proof
from [6]. We slightly simplify the argument and get a better bound, again by
tweaking the decomposition tree, but the whole argument is still surprisingly
non trivial.

We also describe a new operation, the mixed extension, which appears naturally
in a proof of the $\chi$-boundedness of bounded twin-width classes. A mixed
subgraph of an ordered graph $G$ is obtained by only keeping the edges between
mixed pairs of intervals, for some vertex-partition of $G$ into intervals.
When $G$ has bounded twin-width (and the order is $d$-mixed free), every mixed
subgraph has bounded chromatic number (using degeneracy via Marcus-Tardos). We
show more generally that if the class $\cal C^{\prime}$ of mixed subgraphs of
a class $\cal C$ is $\chi$-bounded, then $\cal C$ is also $\chi$-bounded.
Thus, mixed extensions preserve $\chi$-boundedness.

##  2 First operation: Delayed extension

Given a positive integer $s$, we denote by $[s]$ the set $\\{1,2,\ldots,s\\}$.
If $G$ is a graph, $\chi(G)$ denotes its chromatic number and $\omega(G)$ its
clique number. When $X$ is a subset of vertices, we denote by $G[X]$ the graph
induced by $G$ on $X$. We recall that $X\subseteq V(G)$ is a _module_ of $G$
if for every $y\in V(G)\setminus X$ we have all edges between $y$ and $X$, or
no edge between $y$ and $X$.

We first show that every graph $G$ on vertex set $v_{1},\ldots,v_{n}$ has a
canonical decomposition tree $T_{d}$, called _delayed decomposition tree_. Its
leaves are the vertices of $G$, and every internal node $x$ of $T_{d}$ is
labelled by a graph $G_{x}$ defined on the grandchildren of $x$. It is the
analogue of the usual decomposition tree for modules, where every $G_{x}$ is
defined on children instead of grandchildren (hence the ”delayed”).

The tree $T_{d}$ is defined via a sequence of refining partitions
$P_{0},P_{1},\dots,P_{k}$ of the vertex set $V$ of $G$ starting with the root
vertex $P_{0}=\\{V\\}$ and ending on
$P_{k}=\\{\\{v_{1}\\},\ldots,\\{v_{n}\\}\\}$, the partition into singletons
corresponding to the vertices. We now describe how to construct the refinement
$P_{i+1}$ of $P_{i}=\\{B_{1},\ldots,B_{m}\\}$, that is how a part $B_{j}$ is
further refined. In this process, all parts will consist of consecutive
vertices in the ordering $v_{1},\ldots,v_{n}$.

For this, we define a partition $P(I)$ of an arbitrary interval of consecutive
vertices $I=\\{v_{i},\dots,v_{j}\\}$.

  * •

If $i=j$, it is not refined.

  * •

If $I$ is a module, we divide it into two parts
$\\{v_{i},\dots,v_{\lfloor(i+j)/2\rfloor}\\}$ and
$\\{v_{\lfloor(i+j)/2\rfloor+1},\dots,v_{j}\\}$.

  * •

If $I$ is not a module, we partition it into maximal subsets $S$ of
consecutive vertices such that $S$ is a module in $G[(V\setminus I)\cup S]$.
We call these parts _local modules_. In other words $v_{s},v_{s+1}\in I$ are
in the same local module of $I$ if and only if they have the same neighbours
in $V\setminus I$.

To form the refinement $P_{i+1}$ of $P_{i}=\\{B_{1},\ldots,B_{m}\\}$, we just
refine every $B_{j}$ into $P(B_{j})$. Observe that since $P_{0}=\\{V\\}$ is a
module, we have $P_{1}=\\{\\{v_{1},\ldots,v_{\lceil n/2\rceil}\\},\\{v_{\lceil
n/2\rceil+1},\ldots,v_{n}\\}\\}$. We stop the process when $P_{k}=P_{k-1}$,
which happens when all parts are singletons. For technical reasons (made
clearer in the next definition) we keep the two identical partitions into
singletons $P_{k-1},P_{k}$ instead of simply stopping at step $k-1$. The
partition of a module into two (near) equal intervals is arbitrary, we could
for instance partition $I$ into $\\{v_{i}\\}$ and $\\{v_{i+1},\dots,v_{j}\\}$.

We next consider the tree $T_{d}$ corresponding to this decomposition process,
where the nodes at depth $i$ correspond to the parts of $P_{i}$, and the
children of a node $x\in P_{i}$ are the parts $y\in P_{i+1}$ such that
$y\subseteq x$ (we usually identify the nodes of $T_{d}$ to subsets of $V$).
The leaves of $T_{d}$ are the vertices $v_{i}$ of $G$. Moreover, the parent of
a leaf $v_{i}$ is $v_{i}$ since $P_{k-1}=P_{k}$. We now describe how to
structure $T_{d}$ as a _delayed tree decomposition_ in order to encode the
graph $G$. The crucial remark here is that if a node $x$ of $T_{d}$ has two
grandchildren $y,z$ which are not siblings (we say that $y,z$ are _cousins_ ,
i.e. their parents are distinct), then we have all edges between $y$ and $z$,
or no edge between them. In other words, cousins are modules with respect to
each other.

From this observation, we define a function $g$ associating to every node
$x\in T_{d}$ a graph $G_{x}:=g(x)$ whose vertex set is the set of
grandchildren of $x$ and such that $yz$ is an edge of $G_{x}$ if $y,z$ are
cousins and there exists an edge between $y$ and $z$ in $G$ (and thus $y$ is
fully joined to $z$).

Given a pair $(T,g)$, now simply seen as a rooted tree $T$ in which the parent
of every leaf only has one child, and each $g(x)$ is a graph on the
grandchildren of $x$ (if any, otherwise $g(x)$ is empty), we define the
_realization_ $R(T,g)$ as the graph such that:

  * •

its vertex set is the set of leaves $L$ of $T$,

  * •

two vertices $x,y\in L$ are joined by an edge if, given that $z$ is their
closest ancestor in $T$ and $x^{\prime},y^{\prime}$ are the respective
grandchildren of $z$ which are the ancestors of $x,y$, the edge
$x^{\prime}y^{\prime}$ belongs to $g(z)$.

The crucial observation is that $G$ is equal to $R(T_{d},g)$, hence every
graph can be expressed as a delayed decomposition tree. Given a class of
graphs $\cal C$, we denote by ${\cal C}_{d}$ the class of graphs $G$ admitting
a delayed tree decomposition $(T_{d},g)$ (for some enumeration of their vertex
set) in which all graphs $g(x)$ belong to $\cal C$. We call ${\cal C}_{d}$ the
_delayed extension_ of $\cal C$. It is not strictly speaking a closure since
applying it twice can produce more graphs than applying it once.

The delayed extension is very similar to the _substitution closure_ ${\cal
C}_{s}$ of $\cal C$, in which $G\in{\cal C}_{s}$ if all its induced _prime_
subgraphs $H$ (i.e. with no modules of size $k$ where $1<k<|V(H)|$) belong to
$\cal C$. We have ${\cal C}_{s}\subseteq{\cal C}_{d}$, but we shall not need
it. Conversely, we can express ${\cal C}_{d}$ in terms of ${\cal C}_{s}$. We
invite the reader not familiar with tree-decompositions with respect to
substitutions to read the Section 6 of this paper.

ABCDE

ACDEB

Figure 1: A delayed decomposition tree of $C_{5}$ and its corresponding
realization. The edges of every $g(x)$ are drawn in the same color as $x$.
Note that all $g(x)$ are cographs.

###### Lemma 1

Every graph in ${\cal C}_{d}$ is the edge union of two graphs in ${\cal
C}_{s}$.

Proof. Let $G:=R(T,g)$ be a graph such that $g(x)\in\cal C$ for all nodes of
$T$. We consider a function $g_{o}$ (o for odd) defined on $T$ such that
$g_{o}(x)=g(x)$ if $x$ has odd depth in $T$ and $g_{o}(x)$ is the edgeless
graph (on the grandchildren of $x$) if $x$ has even depth. We define
analogously $g_{e}$ in which $g_{e}(x)=g(x)$ if $x$ has even depth, and is
edgeless otherwise. We define $G_{o}:=R(T,g_{o})$ and $G_{e}:=R(T,g_{e})$.

By construction, $G$ is the edge union $G_{o}\cup G_{e}$. We now show that
$G_{o}$ is in ${\cal C}_{s}$. Observe that every node $x$ of $T$ with odd
depth (seen as a subset of vertices of $G$) is a module of $G_{o}$. Indeed,
for every vertex $v\notin x$, the subset $x$ is a module of $G_{o}[x\cup v]$:
this is by definition of $G_{o}$ if $v$ is not a descendant of a sibling of
$x$, and if $v$ is a descendant of a sibling of $x$ there is no edge between
$v$ and $x$ since their closest ancestor, the parent of $x$, has even depth.
In particular, if $H$ is a prime induced subgraph of $G_{o}$, we consider the
deepest node $x$ with odd depth such that $V(H)\subseteq x$, and since
$|V(H)\cap y|\leq 1$ for every grandchild $y$ of $x$ ($H$ is prime), we have
that $H$ is an induced subgraph of $g(x)$, hence $H\in\cal C$. The same
argument holds for $G_{e}$.

We now recall the result of Chudnovsky, Penev, Scott and Trotignon [6].

###### Theorem 1

If $\cal C$ is polynomially $\chi$-bounded with function $\omega^{k}$, then
${\cal C}_{s}$ is $\chi$-bounded by $\omega^{3k+11}$.

###### Corollary 1

If $\cal C$ is polynomially $\chi$-bounded with function $\omega^{k}$, then
${\cal C}_{d}$ is $\chi$-bounded by $\omega^{6k+22}$.

Proof. This directly follows from Lemma 1 and the fact that
$\chi(G)\leq\chi(G_{o})\chi(G_{e})$.

For the sake of self containment, we provide in Section 6 a proof of Theorem 1
which is slightly simpler than the one of [6] with the improved bound of
$\omega^{2k+3}$ (hence giving $4k+6$ for delayed trees). It would be
interesting to find the best bounds for Theorem 1.

Thus, it suffices to focus on $\cal C$ if we want to show a polynomial
$\chi$-bounding function for ${\cal C}_{d}$. The key to simplify a graph $G$
is an enumeration of its vertices for which the canonical delayed
decomposition $(T_{d},g)$ satisfies that all $g(x)$ are _simpler_ than $G$.
This is better said for classes: A class ${\cal C}_{0}$ can be _delayed_ to
${\cal C}_{1}$ if ${\cal C}_{0}=({{\cal C}_{1}})_{d}$. For instance, cographs
are the class $({{\cal G}_{2}})_{d}$ where ${\cal G}_{2}$ are the graphs of
size at most 2 (indeed, it is $({{\cal G}_{2}})_{s}$). Let us say that a class
${\cal C}_{0}$ can be _finitely delayed_ to a class ${\cal C}_{k}$ if there
exist ${\cal C}_{0},{\cal C}_{1},\dots,{\cal C}_{k}$ such that ${\cal
C}_{i}=({{\cal C}_{i+1}})_{d}$ for all $i=0,\dots,k-1$. Also, we say that
${\cal C}_{0}$ has _finite delay_ if it can be finitely delayed to ${\cal
G}_{2}$. By Corollary 1, every class with finite delay is polynomially
$\chi$-bounded, as well as every class which can be finitely delayed to a
polynomially $\chi$-bounded class.

An exciting line of future research would be to explore which classes of
graphs have finite delay to simpler classes. This could prove useful for
understanding $\chi$-boundedness. Of course, it is a particular case of a more
complex question asking if a graph can be edge-partitioned into two simpler
graphs, but it has a great advantage: looking for arbitrary edge-partitions
can be extremely complex due to the huge number of possibilities. Focusing
instead on delayed decompositions only requires guessing the right vertex-
ordering, which is a deeply explored field in graphs. To illustrate this,
assuming that the vertex ordering of $G\in\cal C$ is a breadth first search
and that the rule for cutting modules is to isolate the first vertex, note
that $T_{d}$ will mimic the discovery order. In other words, if the induced
subgraphs on the layers of the BFS belong to a class simpler than $\cal C$,
then $\cal C$ is a delayed extension of a simpler class. In this sense,
delayed decompositions can generalize $\chi$-boundedness arguments based on
layer decompositions.

Delayed decompositions also behave very well with twin-width, which has an
alternative definition involving vertex orderings.

##  3 Second operation: Right extension

Our goal in this section is to define an extension of a class of graphs $\cal
C$ which preserves $\chi$-boundedness, and even polynomial $\chi$-boundedness
when the twin-width of $\mathcal{C}$ is bounded. Given a graph $G$, a _right
module partition_ (RMP) is a partition $V_{1},\ldots,V_{k}$ of the vertices of
$G$ such that

  1. 1.

Each $V_{i}$ is a stable set.

  2. 2.

For every $i<j$, $V_{i}$ is a module with respect to $V_{j}$ (i.e. $V_{i}$ is
a module in $G[V_{i}\cup V_{j}]$).

Note that every graph $G$ has a trivial RMP where each $V_{i}$ consists of a
single vertex. Therefore, there should be some limitations to the definition
of RMP. A first attempt is to consider a class of graphs $\mathcal{C}$, and
insist that every induced subgraph intersecting every $V_{j}$ on at most one
vertex (called a _transversal_) belongs to $\mathcal{C}$. Unfortunately, even
RMP with forests transversals are not $\chi$-bounded. To see this, consider
$S_{n,2}$, the $n$-th shift graph, whose vertex set is $\\{(i,j),1\leq i<j\leq
n\\}$ and such that there is an edge between $(i,j)$ and
$(i^{\prime},j^{\prime})$ if and only if $j=i^{\prime}$. Observe that the
graphs $S_{n,2}$ have unbounded chromatic number and are triangle-free.
However, the partition $(V_{2},\ldots,V_{n})$ where $V_{j}=\\{(i,j),1\leq
i<j\\}$ for $2\leq j\leq n$ is an RMP (with $V_{1}$ empty) such that the only
neighbours of $(i,j)\in V_{j}$ in parts $V_{k}$ where $k<j$ are in $V_{i}$.
Thus if $(i,j)$ belongs to a transversal, its degree is at most one with
respect to the vertices in $V_{k}$ with $k<j$. Hence, all transversals are
forests, while the graphs $S_{n,2}$ are not $\chi$-bounded.

For this reason, we introduce a stronger notion of RMP, meant to preserve
$\chi$-boundedness. If $\mathcal{P}=(V_{1},\ldots,V_{k})$ is an RMP of a graph
$G$, for every $1\leq j_{1}<j_{2}<\ldots<j_{\ell}\leq k$ and every
$W_{j_{1}}\subseteq V_{j_{1}},\ldots,W_{j_{\ell}}\subseteq V_{j_{\ell}}$, all
non-empty, we denote by $G/\\{W_{j_{1}},\ldots,W_{j_{\ell}}\\}$ the graph on
vertex set $[\ell]$ such that there is an edge $ii^{\prime}$ if and only if
there is an edge between $W_{j_{i}}$ and $W_{j_{i^{\prime}}}$. We call such a
graph a _transversal minor_ of $(G,\mathcal{P})$. Given a class $\mathcal{C}$,
an RMP such that all transversal minors are in $\mathcal{C}$ is called a
_$\mathcal{C}$ -RMP_. The class of graphs $G$ admitting a $\mathcal{C}$-RMP is
denoted by $RM(\mathcal{C})$ and is called the _right extension_ of $\cal C$.

1, 21, 32, 31, 42, 43, 41, 52, 53, 54, 5 Figure 2: The RMP for $S_{5,2}$.
Here, an edge means that we have all edges from the stable set on the left to
the vertex on the right. Observe that every transversal is a forest, however
we can form every graph on 4 vertices as a transversal minor.

Our goal is now to show that right extension preserves $\chi$-boundedness. We
will express our result in the language of ordered graphs (graphs with a total
order on vertices). An RMP for an ordered graph must respect the order, that
is the parts of the partition must consist of consecutive vertices. The
following result is not used in the proof that bounded twin-width graphs are
polynomially $\chi$-bounded, but it could be useful in other context and its
proof is similar to a later argument.

###### Proposition 1

If $\mathcal{C}$ is a $\chi$-bounded class of ordered graphs, then
$RM(\mathcal{C})$ is $\chi$-bounded.

The proof of Proposition 1 is heavily based on the following lemma about the
clique number. Given an ordered graph $G$ and an RMP
${\mathcal{P}}=(V_{1},\ldots,V_{k})$, we denote by $G/\cal P$ the ordered
graph obtained by contracting all parts of $\cal P$, i.e.
$G/\\{V_{1},\ldots,V_{k}\\}$. This is a particular transversal minor of $G$,
with the property that $\chi(G)\leq\chi(G/{\cal P})$. A class $\cal C$ of
ordered graphs is _$h$ -free_ if it does not contain some ordered graph on $h$
vertices.

###### Lemma 2

There exists a function $\phi$ such that for every $h$-free class $\cal C$ and
every ordered graph $G$ with a $\cal C$-right module partition $\cal P$, we
have $\omega(G/{\cal P})\leq\phi(\omega(G),h)$

Proof. The proof is by induction on $\omega:=\omega(G)$ and $h$. If $h=1$ or
$\omega=1$ then $G$ is edgeless, so we can set $\phi(x,1)=\phi(1,y)=1$. Now,
$\omega\geq 2$ and $h\geq 2$, and we assume that we proved the existence of
$\phi(\omega-1,h)$ and $\phi(\omega,h-1)$. We denote
$\mathcal{P}=(V_{1},\ldots,V_{k})$ and consider an ordered graph $H$ on
vertices $v_{1},\dots,v_{h}$ which is not in $\cal C$. Observe that we can
restrict ourselves to the case where $G/{\cal P}$ is a clique, as we can only
consider a maximal clique of $G/{\cal P}$.

Thus, for every $i<j\in[k]$, there is an edge between $V_{i}$ and $V_{j}$. Let
$D_{k}$ be a subset of $V_{k}$ of minimal size such that there is an edge
between $V_{i}$ and $D_{k}$ for every $i<k$. By minimality of $D_{k}$, for
every $d\in D_{k}$ there exists $i_{d}\in[k-1]$ such that there is an edge
between $V_{i_{d}}$ and $d$ (and thus $d$ dominates $V_{i_{d}}$) but no edge
between $V_{i_{d}}$ and $D_{k}\setminus\\{d\\}$. We consider two cases
depending on the size of $D_{k}$.

  1. 1.

If $|D_{k}|>\phi(\omega,h-1)+1$, we show that we reach a contradiction. Select
some $x\in D_{k}$ and consider the set $\cal P^{\prime}$ of $|D_{k}|-1$ parts
$V_{i_{d}}$ as defined above, except for the part $V_{i_{x}}$ which is not
selected in $\cal P^{\prime}$. Since $G/\cal P^{\prime}$ is a clique of size
at least $\phi(\omega,h-1)+1$, it follows by induction that $(G[\cup{\cal
P^{\prime}}],\cal P^{\prime})$ contains all ordered graphs of size $h-1$ as
transversal minors. In particular, the ordered graph $H^{\prime}=H\setminus
v_{h}$ is a transversal minor of $\cal P^{\prime}$. If $v_{h}$ is isolated in
$H$, we reach a contradiction since $H^{\prime}\cup x$ is isomorphic to $H$
and is a transversal minor of $(G,\cal P)$. Otherwise, observe that one can
extend $H^{\prime}$ in all possible ways as a transversal minor of $\cal P$ by
selecting some vertices in $D_{k}$. Indeed, every $V_{i_{d}}$ corresponds to a
vertex $d$ in $D_{k}$ which is only joined to $V_{i_{d}}$. We can then select
vertices in $D_{k}$ to extend $H^{\prime}$ to $H$, a contradiction.

  2. 2.

If $|D_{k}|\leq\phi(\omega,h-1)+1$. For $d\in D_{k}$, let $S_{d}$ be the set
of neighbours of $d$ in $G$. In particular, $\omega(G[S_{d}])\leq\omega-1$.
Furthermore, $\mathcal{P}$ induces by restriction a $\mathcal{C}$-RMP
$\mathcal{P}_{d}$ of $G[S_{d}]$. We then have
$\omega(G[S_{d}]/\mathcal{P}_{d})\leq\phi(\omega-1,h)$. By taking the union
over all $d\in D_{k}$, we deduce
$\omega(G/\mathcal{P})\leq\phi(\omega-1,h)\cdot(\phi(\omega,h-1)+1)+1$ (the
additional +1 stands for the last class $V_{k}$ which is not dominated).

Therefore, we can choose
$\phi(\omega,h)=\phi(\omega-1,h)\cdot(\phi(\omega,h-1)+1)+1$.

We are now ready to prove Proposition 1. If $\cal C$ has a $\chi$-bounding
function $f$, by the fact that the class of all graphs is not $\chi$-bounded,
there is a graph $H$ of size $h$ which is not in $\cal C$. Consider now any
graph $G$ in $RM(\cal C)$ with clique number $\omega$ and $\mathcal{C}$-RMP
$\cal P$. We have

$\chi(G)\leq\chi(G/{\cal P})\leq f(\omega(G/{\cal P}))\leq
f(\phi(\omega(G),h)).$

Therefore the function $f(\phi(\omega(G),h))$ is $\chi$-bounding for $RM(\cal
C)$. This approach does not provide a polynomial bound if the class $\cal C$
is polynomially $\chi$-bounded. We could not prove (or disprove) that
polynomial $\chi$-boundedness is preserved by RMP. However, this is the case
when the twin-width of $\mathcal{C}$ is bounded, as shown in the following
section.

##  4 Twin-width and almost-mixed minors

We recall here some definitions and results related to twin-width. For a more
intuitive and pedestrian introduction, see [3]. We adopt here the matrix point
of view of twin-width, where every graph $G$ is represented via its symmetric
adjacency matrix $(a_{u,v})$ where $u,v$ are over couples of vertices. The
entry $a_{u,v}$ is 1 if $uv$ is an edge, 0 if $uv$ is not an edge, and $*$ if
$u=v$. The addition of the $*$ symbol slightly simplifies some technicalities,
but is not necessary for the argument.

A $01*$-matrix is _horizontal_ if all its rows are constant. It is _vertical_
if all its columns are constant. It is _constant_ if it is both horizontal and
vertical. It is _mixed_ if it is neither horizontal nor vertical, or if it has
at least 2 rows and 2 columns and contains a $*$ entry. A _corner_ in a matrix
$M$ is a mixed $2\times 2$ submatrix of $M$.

######  Lemma 3 ([3])

A matrix is mixed if and only if it contains a corner.

Let $M$ be a matrix. A _row partition_ of $M$ is a partition of the rows of
$M$ in which each part of the partition consists of consecutive rows. We
define _column partitions_ in a similar way. A _division_ $\mathcal{D}$ of $M$
is a pair $(\mathcal{R},\mathcal{C})$ where $\mathcal{R}$ is a row partition
of $M$ and $\mathcal{C}$ is a column partition of $M$. If $\mathcal{R}$ and
$\mathcal{C}$ both have the same number of parts, say $k$, we say that
$(\mathcal{R},\mathcal{C})$ is a _$k$ -division_ of $M$. In this case, we
index the row blocks and the column blocks of $\mathcal{D}$ with integers from
$[k]$ in the natural order of the blocks. If $\mathcal{D}$ is a $k$-division
of $M$, for $i,j\in[k]$, we denote by $\mathcal{D}[i,j]$ the intersection of
the $i$-th row block with the $j$-th column block, which we call a _zone_ of
$\mathcal{D}$. If $R_{i}\in\mathcal{R}$ and $C_{j}\in\mathcal{C}$, we also
adopt the notation $[R_{i},C_{j}]$ for the zone $\mathcal{D}[i,j]$. It is a
contiguous submatrix of $M$.

We say that a zone of a matrix is _mixed_ if it is mixed as a submatrix. If
$M$ is symmetric, we say that a division $(\mathcal{R},\mathcal{C})$ is
_symmetric_ if $\mathcal{R}$ and $\mathcal{C}$ partition rows and columns in
the same way (i.e. $\mathcal{R}$ is the transpose of $\mathcal{C}$).

Let $M$ be a matrix and $\mathcal{D}$ be a $d$-division of $M$. We say that
$\mathcal{D}$ is a _$d$ -mixed minor_ if each zone of $\mathcal{D}$ is mixed.
If $M$ does not have any $d$-mixed minor, we say that $M$ is _$d$ -mixed
free_. The twin-width parameter and mixed-minor freeness are functionally
equivalent. In particular, it was shown in [3] that if a graph has twin-width
at most $d$, it has a vertex ordering for which the adjacency matrix of $G$ is
$f_{d}$-mixed free for some constant $f_{d}$.

We also recall the following result, which is a direct consequence of the
Marcus-Tardos theorem, see [11]:

###### Theorem 2

For every positive integer $d$, there is a constant $mt_{d}$ such that for
every $d$-mixed free matrix $M$ and every $k$-division of $M$, the number of
mixed zones is at most $mt_{d}\cdot k$

As we will perform some operations on our graphs (such as deleting edges and
contracting subsets of vertices), we show in the next results how mixed zones
are affected. Let $M$ be a $01*$-matrix (not necessarily an adjacency matrix)
with exactly two row blocks $R,R^{\prime}$ and two columns blocks
$C,C^{\prime}$, each of size at least two.

###### Lemma 4

If all four zones of $M$ are mixed, there is a corner intersecting all zones.

Proof. This is clear if $M$ contains a $*$. Consider a non constant row $r$ in
$[R,C]$ and a non constant column $c^{\prime}$ in $[R^{\prime},C^{\prime}]$.
Let $e$ be the entry $(r,c^{\prime})$. Let $c\in C$ such that $e\neq(r,c)$ and
$r^{\prime}\in R^{\prime}$ such that $e\neq(r^{\prime},c^{\prime})$. Now
$\\{r,r^{\prime}\\},\\{c,c^{\prime}\\}$ is a corner.

The _contraction_ $M^{\prime}=M/\\{R,R^{\prime};C,C^{\prime}\\}$ is the
$2\times 2$-matrix obtained by keeping a single value $x$ for each of the 4
zones, with the following rule: $x$ is the maximum value of the zone according
to the order $0<1<*$. Thus, we get $*$ as soon as there exists a $*$, and we
get $0$ only if the zone is full $0$.

###### Lemma 5

If $M^{\prime}$ is mixed, then $M$ is mixed.

Proof. This is clear if $M^{\prime}$ (thus equivalently $M$) contains a $*$.
Let us assume by contrapositive that $M$ is non-mixed. If $M$ is vertical
(resp. horizontal), then observe that $M^{\prime}$ is also vertical (resp.
horizontal).

We keep the same notations as before, and assume moreover that none of the
four zones of $M$ is mixed (in particular $M$ has no value $*$). The
_horizontal-deletion_ $M_{H}$ of $M$ is the matrix obtained from $M$ by
setting all values to 0 in each zone which is not vertical (or equivalently
each zone which is horizontal and non-constant). We similarly define the
_vertical-deletion_ $M_{V}$.

###### Lemma 6

If $M_{H}$ is mixed, then $M$ is mixed.

Proof. Let us assume by contrapositive that $M$ is non-mixed. By assumption,
there is no $*$ in $M_{H}$. If $M$ is vertical, then observe that $M_{H}$ is
also vertical. Now if $M$ is horizontal, note that the zones $R,C$ and
$R,C^{\prime}$ are either both set to 0 (if they are not vertical), or both
left as in $M$. In both cases the rows of $R$ in $M_{H}$ are constant. The
same applies to $R^{\prime}$, so $M_{H}$ is horizontal.

Here is the key-definition of [12]. A $d$-division $\mathcal{D}$ of a matrix
$M$ is a _$d$ -almost mixed minor_ if for every $i\neq j\in[d]$, the zone
$\mathcal{D}[i,j]$ is mixed. If $M$ does not have any $d$-almost mixed minor,
we say that $M$ is _$d$ -almost mixed free_. By extension, a graph is _$d$
-almost mixed free_ if we can order its vertices in such a way that its
adjacency matrix is $d$-almost mixed free.

Observe that every $d$-almost mixed free matrix is also $d$-mixed free.
Conversely, every $d$-mixed free matrix is also $2d$-almost mixed free.
Indeed, if $M$ has a $2d$-almost mixed minor, then merging the first $d+1$ row
blocks, and the last $d+1$ column blocks gives a $d$-mixed minor of $M$. Note
that every submatrix of a $d$-(almost) mixed free matrix is also $d$-(almost)
mixed free, hence every subgraph of a $d$-almost mixed free graph is also
$d$-almost mixed free.

Let $G$ be a graph with an RMP $\mathcal{P}=(V_{1},\ldots,V_{k})$. We say that
$(G,\mathcal{P})$ is _$d$ -almost mixed free_, if for every coarsening $\cal
P^{\prime}$ of $\cal P$ into $d$ parts
$(V^{\prime}_{1},\ldots,V^{\prime}_{d})$, where each $V^{\prime}_{i}$ consists
of consecutive parts of $\cal P$, some zone $[V^{\prime}_{i},V^{\prime}_{j}]$,
where $i\neq j$, is not mixed in the adjacency matrix of $G$. Note that we
only speak here of restrictions on symmetric divisions of $G$, which encompass
much larger classes than bounded twin-width.

###### Lemma 7

If $(G,\cal P)$ is $d$-almost mixed free, then $\omega(G/{\cal
P})\leq\omega(G)^{d}$.

Proof. We write $\omega:=\omega(G)$ and denote
$\mathcal{P}=(V_{1},\ldots,V_{k})$. Let $\phi$ such that $\omega(G/{\cal
P})\leq\phi(\omega,d)$. We have $\phi(\cdot,1)=0$ (empty graph) and
$\phi(1,\cdot)=1$ (edgeless graph). We assume $\omega\geq 2$ and $d\geq 2$ and
show that $\phi(\omega,d)=\phi(\omega-1,d)+\phi(\omega,d-1)+1$ upper bounds
$\omega(G/{\cal P})$. We can restrict ourselves to a maximal clique of
$G/{\cal P}$, so we can assume that there is an edge between $V_{i}$ and
$V_{j}$ whenever $i<j\in[k]$.

Let us consider the smallest $\ell$ such that $\omega(G[V_{1}\cup\dots\cup
V_{\ell}])=\omega$. Denote by $Y$ the set $V_{1}\cup\dots\cup V_{\ell}$, and
consider any $V_{i}$ where $i\geq\ell+1$. Note that $Y$ is not a module with
respect to $V_{i}$, as some vertex in $V_{i}$ would dominate $Y$, hence
forming a clique of size $\omega+1$ in $G$. Conversely, if $V_{i}$ is a module
with respect to $Y$, since $\cal P$ is an RMP, and there exists an edge
between all pairs of parts, $V_{i}$ would dominate $Y$, with the same
contradiction.

Consider the graph $G^{\prime}=G[V_{\ell+1}\cup\dots\cup V_{k}]$ and its RMP
$\mathcal{P^{\prime}}=(V_{\ell+1},\ldots,V_{k})$. We claim that
$(G^{\prime},\cal P^{\prime})$ is $d-1$-almost mixed free, otherwise any
$d-1$-almost mixed minor coarsening $(V^{\prime}_{1},\ldots,V^{\prime}_{d-1})$
of $\mathcal{P^{\prime}}$ could be extended to the $d$-almost mixed minor
$(Y,V^{\prime}_{1},\ldots,V^{\prime}_{d-1})$ of $(G,\cal P)$.

Thus $k=\omega(G/\cal P)$ satisfies by induction that
$k\leq\ell+\phi(\omega,d-1)$. And since the first $\ell-1$ parts do not
contain a clique of size $\omega$, we have
$k\leq\phi(\omega-1,d)+1+\phi(\omega,d-1)=\phi(\omega,d)$. Setting
$\psi(\cdot,\cdot)=\phi(\cdot,\cdot)-1$, we have that
$\psi(\omega,d)=\psi(\omega-1,d)+\psi(\omega,d-1)$. Moreover, we both have
$\psi(\omega,1)=-1$ and $\psi(1,d)=0$, so
$\psi(\omega,d)\leq\binom{\omega+d-2}{d-1}\leq\omega^{d-1}$.

###### Proposition 2

Let $\cal C$ be a class of graphs with polynomial $\chi$-bounding function
$f(x)=x^{c}$. If $\cal P$ is a $\cal C$-RMP of $G$ such that $(G,\cal P)$ is
$d$-almost mixed free, then $\chi(G)\leq\omega^{cd}$.

Proof. Since $\omega(G/{\cal P})\leq\omega(G)^{d}$, we have
$\chi(G)\leq\chi(G/{\cal P})\leq\omega(G/{\cal P})^{c}\leq\omega(G)^{cd}$.

##  5 Polynomial $\chi$-boundedness of bounded twin-width

To prove that a class $\cal C$ is polynomially $\chi$-bounded, a strategy is
to show that every graph $G$ of $\cal C$ has a vertex-partition or an edge-
partition into a bounded number of graphs, each of them belonging to some
known polynomially $\chi$-bounded class $\cal C^{\prime}$. We will use this
argument several times here.

###### Theorem 3

The class of $d$-almost mixed free graphs is polynomially $\chi$-bounded.

Proof. The proof is by induction on $d$. For $d=2$, if $G$ has a 2-almost
mixed free adjacency matrix, $G$ is a cograph (see [12]), hence $G$ is perfect
so the property holds. Now, let $d\geq 3$ and consider a graph $G$, which is
$d$-almost mixed free with respect to the vertex ordering
$v_{1},\ldots,v_{n}$. We first partition the set of vertices
$V^{\prime}=\\{v_{2},\dots,v_{n-1}\\}$ into four subsets
$V^{\prime}_{00},V^{\prime}_{01},V^{\prime}_{10},V^{\prime}_{11}$ according to
their neighbourhood in $\\{v_{1},v_{n}\\}$. For instance,
$V^{\prime}_{01}=(V^{\prime}\setminus N(v_{1}))\cap N(v_{n})$. It suffices to
show that all four graphs $G[V^{\prime}_{ij}]$ belong to some polynomially
$\chi$-bounded class. Hence, without loss of generality, we can assume that
$V^{\prime}$ is a module in $G$. We now consider the delayed decomposition
tree $(T_{d},g)$ of $G^{\prime}:=G[V^{\prime}]$ and consider the class $\cal
C$ containing all $g(x)$ and their induced subgraphs. By Corollary 1, we just
have to show that $\cal C$ is polynomially $\chi$-bounded. The graphs $g(x)$
are obtained by starting from an interval $I=\\{v_{s},\dots,v_{t}\\}$ of
vertices of $G^{\prime}$, partitioning it into local modules
$L_{1},\dots,L_{k}$, and then partitioning each local module into local
submodules. Let $H$ be the graph we obtain from $G[I]$ by removing all edges
inside all local modules $L_{i}$. Note that $H$ can also be obtained by
substituting the vertices of $g(x)$ by stable sets. This does not change
$\chi$ and $\omega$. Therefore, to show that $\mathcal{C}$ is polynomially
$\chi$-bounded, it suffices to prove the following.

###### Claim 1

Let $I=\\{v_{s},\dots,v_{t}\\}$ be any interval of vertices of $G^{\prime}$.
Consider its partition into local modules $L_{1},\dots,L_{k}$ and denote by
$H$ the graph on vertex set $I$ obtained from $G[I]$ by deleting the edges
inside the local modules. Then, $H$ is a bounded (vertex and edge) union of
graphs from hereditary polynomially $\chi$-bounded classes.

Note that the claim holds when $I$ is a non trivial module since it is cut
into two parts. Indeed, in this case $H$ is bipartite and thus $\chi$-bounded
by 2. Assume now that we have local modules $L_{1},\dots,L_{k}$, and consider
all pairs $i<j$ such that $G[L_{i},L_{j}]$ is mixed (call _mixed pairs_). The
$L_{i}$’s form a $k$-division of the adjacency matrix of $G[I]$, which is
$d$-mixed free. Thus, by Theorem 2, the graph $R$ on vertex set $[k]$ whose
edges correspond to mixed pairs has at most $\frac{mt_{d}}{2}\cdot k$ edges.
In particular, $R$ can be vertex-colored into $(mt_{d}+1)$ classes. In other
words, one can partition the set of local modules into $(mt_{d}+1)$ subsets,
in which local modules are not pairwise mixed. We denote by $L^{\prime}$ such
a subset of local modules. To prove our claim, we just have to show that
$H^{\prime}:=H[L^{\prime}]$ belongs to a polynomially $\chi$-bounded class of
graphs.

Observe that for every $i<j$ and $L_{i},L_{j}\in L^{\prime}$, we have that
$L_{i}$ is a module in $H[L_{i}\cup L_{j}]$ (denoted $L_{i}\rightarrow L_{j}$)
or $L_{j}$ is a module in $H[L_{i}\cup L_{j}]$, that is $L_{j}\rightarrow
L_{i}$. Note that if we both have $L_{j}\rightarrow L_{i}$ and
$L_{i}\rightarrow L_{j}$, we have all edges or no edge between $L_{i}$ and
$L_{j}$. We now define two subgraphs $H^{\prime}_{\rightarrow}$ and
$H^{\prime}_{\leftarrow}$ of $H^{\prime}$: in $H^{\prime}_{\rightarrow}$ we
only keep the edges of $H^{\prime}$ between pairs $L_{i}\rightarrow L_{j}$
where $i<j$, and in $H^{\prime}_{\leftarrow}$ we only keep the edges of
$H^{\prime}$ between pairs $L_{i}\leftarrow L_{j}$ where $i<j$. Note that
$H^{\prime}=H^{\prime}_{\rightarrow}\cup H^{\prime}_{\leftarrow}$, and thus we
just have to show that (for instance) $H^{\prime}_{\rightarrow}$ belongs to a
polynomially $\chi$-bounded class of graphs.

The graph $H^{\prime}_{\rightarrow}$ with the partition $L^{\prime}$ is a
right module partition. Note that the same holds for $H^{\prime}_{\leftarrow}$
if we reverse the order of the local modules. We further partition
$H^{\prime}_{\rightarrow}$: let us say that a local module $L_{i}$ is _left_
if $i>1$ and there is a vertex $v_{j}$ among $v_{1},v_{2},\dots,v_{s-1}$ (i.e.
to the left of $I$) which distinguishes $L_{i-1}$ from $L_{i}$. Precisely,
$v_{j}$ is not joined in the same way to the last vertex of $L_{i-1}$ and to
the first of $L_{i}$. If $L_{i}$ (with $i>1$) is not left, then it is _right_
(and indeed some vertex $v_{j}$ to the right of $I$ distinguishes $L_{i-1}$
from $L_{i}$). We neglect $L_{1}$ in this definition (it only adds 1 to the
chromatic number of $H^{\prime}$). We now partition $L^{\prime}$ into
$L^{\prime}_{ri}$ containing all right local modules $L_{i}$ of $L^{\prime}$,
and $L^{\prime}_{le}$ containing the left local modules. Again, by vertex
partition, we just have to show that the RMP $H^{\prime}_{\rightarrow,ri}$
which is the induced restriction of $H^{\prime}_{\rightarrow}$ to
$L^{\prime}_{ri}$ is polynomially $\chi$-bounded. To apply Proposition 2, we
first show that the transversal minors of
$(H^{\prime}_{\rightarrow,ri},L^{\prime}_{ri})$ are $d-1$-almost mixed free,
which by induction implies that they are polynomially $\chi$-bounded. Then we
argue that $(H^{\prime}_{\rightarrow,ri},L^{\prime}_{ri})$ has no large almost
mixed minor. It suffices here to show that it is $2d$-almost mixed free. These
are our last results.

######  Claim 2 ([12])

Every transversal minor of $(H^{\prime}_{\rightarrow,ri},L^{\prime}_{ri})$ is
$d-1$-almost mixed free.

Proof. Assume for contradiction that we can find a sequence of local modules
$L^{\prime}_{1},\dots,L^{\prime}_{t}$ in $L^{\prime}_{ri}$, each of them
containing a non empty subset of vertices $W_{1},\dots,W_{t}$, such that the
graph $Q=H^{\prime}_{\rightarrow,ri}/\\{W_{1},\dots,W_{t}\\}$ has a
$d-1$-almost mixed minor. The vertices of $Q$ are denoted
$W=\\{w_{1},\dots,w_{t}\\}$, where $W_{i}$ is contracted to $w_{i}$. Moreover,
there exist two partitions of $W$ into consecutive blocks of vertices
$(R_{1},\dots,R_{d-1})$ and $(C_{1},\dots,C_{d-1})$ such that $Q$ is mixed on
the zone $[R_{i},C_{j}]$ whenever $i\neq j$ (thus all $R_{i}$ and $C_{j}$ have
size at least 2). We now show how to ”lift” these partitions to $G$ in order
to get a contradiction.

Consider any partition ${\cal
R}^{\prime}=(R^{\prime}_{1},\dots,R^{\prime}_{d-1})$ of $I$ (where parts
consist of consecutive local modules) satisfying that $w_{i}\in R_{j}$ implies
$L^{\prime}_{i}\subseteq R^{\prime}_{j}$. Similarly ${\cal
C}^{\prime}=(C^{\prime}_{1},\dots,C^{\prime}_{d-1})$ partitions $I$ and
$w_{i}\in C_{j}$ implies $L^{\prime}_{i}\subseteq C^{\prime}_{j}$. We now
extend the partitions ${\cal R}^{\prime},{\cal C}^{\prime}$ of $I$ to the
whole vertex set $V$ of $G$ by first setting
$R^{\prime}_{1}:=R^{\prime}_{1}\cup\\{v_{1},\dots,v_{s-1}\\}$ and
$C^{\prime}_{1}:=C^{\prime}_{1}\cup\\{v_{1},\dots,v_{s-1}\\}$, and then adding
a new part $\\{v_{t+1},\dots,v_{n}\\}=R^{\prime}_{d}=C^{\prime}_{d}$ to both
${\cal R}^{\prime}$ and ${\cal C}^{\prime}$. These new partitions are called
${\cal R}$ and ${\cal C}$. Observe that if we were working with
$H^{\prime}_{\rightarrow,le}$, we would have added the part
$R^{\prime}_{0}=C^{\prime}_{0}=\\{v_{1},\dots,v_{s-1}\\}$ to both ${\cal
R}^{\prime}$ and ${\cal C}^{\prime}$ and extended the parts $R^{\prime}_{d-1}$
and $C^{\prime}_{d-1}$ by adding $\\{v_{t+1},\dots,v_{n}\\}$.

We now show that ${\cal R}$ and ${\cal C}$ form a $d$-almost mixed minor for
$G$, which will be our contradiction. We need to focus on two points: the
added parts $R^{\prime}_{d},C^{\prime}_{d}$ should be mixed with respect to
the others, and the original mixed zones $[R_{i},C_{j}]$ of $Q$ should yield
mixed zones $[R^{\prime}_{i},C^{\prime}_{j}]$ of $G$. We separate the two
arguments:

  * •

Consider first some zone $[R^{\prime}_{i},C^{\prime}_{d}]$ where $i<d$
(similar argument for $[R^{\prime}_{d},C^{\prime}_{i}]$). By the fact that
$R_{i}$ contains two vertices $w_{a},w_{b}$, the part $R^{\prime}_{i}$
contains the right local modules $L^{\prime}_{a},L^{\prime}_{b}$ (where
$a<b$). Focus now on the vertex $v_{j}$ which is the first vertex of
$L^{\prime}_{b}$, and note that $v_{j-1}\in R^{\prime}_{i}$ since
$L^{\prime}_{a}\subseteq R^{\prime}_{i}$. Since $L^{\prime}_{b}$ is a right
local module, there exists $v_{k}$, where $k>t$ such that $v_{k}$ is
differently joined to $v_{j-1}$ and $v_{j}$. Recall that $v_{n}$ is joined in
the same way to $v_{j-1}$ and $v_{j}$. Since $v_{j-1},v_{j}\in R^{\prime}_{i}$
and $v_{k},v_{n}\in C^{\prime}_{d}$, they witness the fact that
$[R^{\prime}_{i},C^{\prime}_{d}]$ is mixed.

  * •

Now, consider any zone $[R^{\prime}_{i},C^{\prime}_{j}]$ where $i,j<d$ and
$i\neq j$. If the zone $[R_{i},C_{j}]$ contains a $*$ (i.e. some $w_{a}$ both
belongs to $R_{i}$ and $C_{j}$), then $[R^{\prime}_{i},C^{\prime}_{j}]$ also
contains a $*$. Otherwise, by Lemma 3, $R_{i}$ contains two vertices
$w_{a},w_{b}$ and $C_{j}$ contains two vertices $w_{c},w_{d}$ such that
$\\{w_{a},w_{b}\\},\\{w_{c},w_{d}\\}$ is a corner. Moreover, since there is no
$*$ value, we have $a<b<c<d$ or $c<d<a<b$. Without loss of generality, we
assume $a<b<c<d$. By Lemma 5, the restriction of the adjacency matrix of
$H^{\prime}_{\rightarrow,ri}$ on $[W_{a}\cup W_{b},W_{c}\cup W_{d}]$ is mixed
since its contraction is the corner $\\{w_{a},w_{b}\\},\\{w_{c},w_{d}\\}$. So
the submatrix $[L^{\prime}_{a}\cup L^{\prime}_{b},L^{\prime}_{c}\cup
L^{\prime}_{d}]$ is also mixed. By definition of
$H^{\prime}_{\rightarrow,ri}$, if $L^{\prime}_{a}$ (or $L^{\prime}_{b}$) is
not a module with respect to $L^{\prime}_{c}$ (or to $L^{\prime}_{d}$), then
the zone $[L^{\prime}_{a},L^{\prime}_{c}]$ is set to 0. In other words, the
adjacency matrix of $H^{\prime}_{\rightarrow,ri}$ restricted to
$[L^{\prime}_{a}\cup L^{\prime}_{b},L^{\prime}_{c}\cup L^{\prime}_{d}]$, is
the horizontal-deletion of the adjacency matrix of $G$. Thus the zone
$[R^{\prime}_{i},C^{\prime}_{j}]$ is mixed by Lemma 6.

###### Claim 3

The pair $(H^{\prime}_{\rightarrow,ri},L^{\prime}_{ri})$ is $2d$-almost mixed
free.

Proof. Assume for contradiction that we can find a coarsening
$W^{\prime}_{1},\dots,W^{\prime}_{2d}$ of $L^{\prime}_{ri}$ which forms a
$2d$-almost mixed minor of $H^{\prime}_{\rightarrow,ri}$. We now set
$W_{i}=W^{\prime}_{2i-1}\cup W^{\prime}_{2i}$ for all $i=1,\dots,d$. By Lemma
3 every (mixed) zone $[W_{i},W_{j}]$ with $i\neq j$ of
$H^{\prime}_{\rightarrow,ri}$ contains a corner
$\\{w_{a},w_{b}\\},\\{w_{c},w_{d}\\}$. By Lemma 4, we can assume that
$w_{a},w_{b},w_{c},w_{d}$ belong respectively to
$W^{\prime}_{2i-1},W^{\prime}_{2i},W^{\prime}_{2j-1},W^{\prime}_{2j}$, hence
to respective distinct local modules
$L^{\prime}_{a},L^{\prime}_{b},L^{\prime}_{c},L^{\prime}_{d}$. We assume
without loss of generality that $i<j$, and thus $a<b<c<d$. By definition of
$H^{\prime}_{\rightarrow,ri}$, if $L^{\prime}_{a}$ (or $L^{\prime}_{b}$) is
not a module with respect to $L^{\prime}_{c}$ (or to $L^{\prime}_{d}$), then
the zone $[L^{\prime}_{a},L^{\prime}_{c}]$ is set to 0. In other words, the
adjacency matrix of $H^{\prime}_{\rightarrow,ri}$ restricted to
$[L^{\prime}_{a}\cup L^{\prime}_{b},L^{\prime}_{c}\cup L^{\prime}_{d}]$, is
the horizontal-deletion of the adjacency matrix of $G$. Hence the zone
$[W_{i},W_{j}]$ is mixed in $G$ by Lemma 6. Thus $G$ restricted to
$W_{1},\dots,W_{d}$ has a $d$-almost mixed minor, a contradiction.

From the previous proof, the order of magnitude for the $\chi$-bounding
function of graphs with no $d$-almost mixed minor is $\omega^{d^{O(d)}}$.

##  6 More on the $\chi$-boundedness of substitution-closure

The goal of this section is to provide a proof of the following theorem by
slightly modifying the original argument of Chudnovsky, Penev, Scott and
Trotignon [6].

###### Theorem 4

If $\cal C$ is hereditary and polynomially $\chi$-bounded with function
$\chi\leq\omega^{k}$, then ${\cal C}_{s}$ is polynomially $\chi$-bounded with
function $\chi\leq\omega^{2k+3}$

Given a class of graphs $\cal C$, a _$\cal C$ -tree-decomposition_ is a pair
$(T,g)$ in which $T$ is a rooted tree and $g$ is a function associating to
every internal node $x$ of $T$ a graph $g(x)\in\cal C$ whose vertices are the
children of $x$. The _realization_ $R(T,g)$ is the graph such that:

  * •

its vertex set is the set of leaves $L$ of $T$

  * •

two vertices $x,y\in L$ are joined by an edge if, given that $z$ is their
closest ancestor in $T$ and $x^{\prime},y^{\prime}$ are the respective
children of $z$ which are the ancestors of $x,y$, the edge
$x^{\prime}y^{\prime}$ belongs to $g(z)$.

Given a class $\cal C$, we denote by ${\cal C}_{s}$ the class of all $R(T,g)$
where $(T,g)$ is a $\cal C$-tree-decomposition. For instance, if $\cal C$ is
the class of cliques and independent sets, then ${\cal C}_{s}$ is the class of
cographs. We say that $(T,g)$ is _independent_ if whenever $x,y$ are internal
nodes of $T$ with the same parent $z$, then $xy$ is not an edge of $g(z)$. We
denote by ${\cal C}_{i}$ the class of all $R(T,g)$ where $(T,g)$ is an
independent $\cal C$-tree-decomposition.
Let $\cal C$ be a class of graphs, and $(T,g)$ be a $\cal C$-tree-
decomposition. Let $u$ be any node of $T$ which is not the root, and let $v$
be the parent of $u$. We say that $u$ is _isolated_ in $T$ if it is isolated
in $g(v)$.
The _depth_ $d(x)$ of a node $x$ of $T$ is the number of strict ancestors of
$x$ in $T$ that are not isolated. The _depth_ $d(T,g)$ of $(T,g)$ is the
maximum depth of a leaf of $T$. Finally, if $G\in\mathcal{C}_{s}$, the _depth_
of $G$ is the minimum depth of a $\cal C$-tree-decomposition $(T,g)$ such that
$G=R(T,g)$.

###### Lemma 8

For every class $\cal C$, if $(T,g)$ is a $\mathcal{C}$-tree-decomposition of
depth $d$, then $\omega(R(T,g))\geq d+1$.

Proof. We consider a leaf $x$ with depth $d$. We denote by $y_{1},\dots,y_{d}$
the non-isolated ancestors of $x$, and by $z_{1},\dots,z_{d}$ their respective
parents. We also denote by $w_{1},\dots,w_{d}$ some respective children of
$z_{1},\dots,z_{d}$ such that $y_{i}w_{i}$ is an edge in $g(z_{i})$. We now
pick some leaves $x^{\prime}_{1},\dots,x^{\prime}_{d}$ which are respective
descendants of $w_{1},\dots,w_{d}$. Observe that
$x,x^{\prime}_{1},\dots,x^{\prime}_{d}$ is a clique of $R(T,g)$.

###### Theorem 5

If $\cal C$ is polynomially $\chi$-bounded with function $\chi\leq\omega^{k}$,
then ${\cal C}_{i}$ is polynomially $\chi$-bounded with function
$\chi\leq\omega^{k+1}$

Proof. Let $G\in\mathcal{C}_{i}$. There exists an independent $\cal C$-tree-
decomposition $(T,g)$ such that $G=R(T,g)$. By Lemma 8, we have $\omega(G)\geq
d(T,g)+1$. For every internal node $x$, we have $g(x)\in\cal C$ and
$\omega(g(x))\leq\omega(G)$, thus $g(x)$ is $\omega(G)^{k}$-colorable. For
every internal node $x$, let $\alpha_{x}$ be an $\omega(G)^{k}$-coloring of
$g(x)$. Let $v$ be any vertex of $G$ (equivalently $v$ is a leaf of $T$). If
$T$ has only one node, then $G$ is the graph on a single vertex, so $G$ is
$\omega(G)^{k+1}$-colorable. Otherwise, let $x$ be the parent of $v$ in $T$.
We set $c(v)=(d(v),\alpha_{x}(v))$, where $d(v)$ is the depth of $v$ in
$(T,g)$.
We claim that $c$ is a proper $\omega(G)^{k+1}$-coloring of $G$. First, for
every vertex $v$ of $G$, we have $0\leq d(v)\leq d(T,g)\leq\omega(G)-1$, so we
indeed use at most $\omega(G)^{k+1}$ colors. Then, let $uv$ be an edge of $G$.
Let $z$ be the closest ancestor of $u$ and $v$ in $T$, and
$u^{\prime},v^{\prime}$ be the respective children of $z$ which are the
ancestors of $u,v$. The edge $u^{\prime}v^{\prime}$ belongs to $g(z)$. Since
$(T,g)$ is an independent $\cal C$-tree-decomposition, this implies that
either $u^{\prime}$ or $v^{\prime}$ is a leaf (or both). If they are both
leaves, we have $u=u^{\prime}$ and $v=v^{\prime}$, therefore $u$ and $v$ are
children of $z$ which are adjacent in $g(z)$. Thus,
$\alpha_{z}(u)\neq\alpha_{z}(v)$ so $c(u)\neq c(v)$. If only one of
$u^{\prime},v^{\prime}$ is a leaf, say $u^{\prime}$, then we have that
$v^{\prime}$ is a strict ancestor of $v$ which is not isolated, so
$d(v)>d(v^{\prime})=d(u^{\prime})=d(u)$ hence $c(u)\neq c(v)$.

Proof. We now prove 4 by induction on the depth of $G$.
If $G$ has depth 0, then $G$ is a disjoint union of graphs of $\cal C$, so
$\chi(G)\leq\omega(G)^{k}\leq\omega(G)^{2k+3}$. Now, suppose $G$ has depth 1.
By a previous lemma, we have $\omega(G)\geq 2$. We can assume that $G$ is
connected since we can deal with each connected component separately. Then $G$
can be obtained by starting from a graph $G_{0}\in\mathcal{C}$ on vertex set
$v_{1},\ldots,v_{n}$ and substituting each $v_{i}$ by a graph
$G_{i}\in\mathcal{C}$. Let $X=\\{v_{i},\omega(G_{i})\leq\sqrt{\omega(G)}\\}$
and $Y=V(G_{0})\setminus X$. Let $G_{X}$ be the subgraph of $G$ induced by the
leaves which are descendant of nodes of $X$ and $G_{Y}$ be the graph induced
on the other vertices. The graph $G_{X}$ is obtained by substituting graphs of
$\mathcal{C}$ of clique number at most $\sqrt{\omega(G)}$ inside a graph of
$\mathcal{C}$ of clique number at most $\omega(G)$. Hence, $G_{X}$ can be
colored with at most $\omega(G)^{1.5k}$ colors (consider the product of the
colorings). Similarly, the graph $G_{Y}$ is obtained by substituting graphs of
$\mathcal{C}$ of clique number at most $\omega(G)$ inside a graph of
$\mathcal{C}$ of clique number at most $\sqrt{\omega(G)}$ so it can be colored
with at most $\omega(G)^{1.5k}$ colors. Hence $G$ can be colored with
$2\omega(G)^{1.5k}\leq\omega(G)^{1.5k+1}\leq\omega(G)^{2k+3}$ colors.

Now, suppose that $G$ has depth at least 2. Thus, $\omega(G)\geq 3$. Let
$(T,g)$ be a $\mathcal{C}$-tree-decomposition of $G$. For every node $x$ of
$T$, let $T_{x}$ be the subtree of $T$ that is rooted in $x$, $g_{x}$ be the
restriction of $g$ to the internal nodes of $T_{x}$, and
$G_{x}=R(T_{x},g_{x})$. Finally, let $X=\\{x,\omega(G_{x})>\omega(G)/2\\}$.
Note that if $z$ is the parent of $x$ in $T$, then $G_{x}$ is an induced
subgraph of $G_{z}$, so if $x\in X$, then we also have $z\in X$. In
particular, $T[X]$ is a subtree of $T$. Let $C(X)$ be the set of children of
an element of $X$ in $T$ and $Y=X\cup C(X)$. Let $T^{\prime}=T[Y]$.
$T^{\prime}$ is also a subtree of $T$. Let $g^{\prime}$ be the restriction of
$g$ to the internal nodes of $T^{\prime}$, and let
$H=R(T^{\prime},g^{\prime})$. Note that $H$ is an induced subgraph of $G$ so
$\omega(H)\leq\omega(G)$. Now, suppose $x,y$ are internal nodes of
$T^{\prime}$ with the same parent $z$. Then, $x,y\in X$ so
$\omega(G_{x}),\omega(G_{y})>\omega(G)/2$. Thus, $x$ and $y$ cannot be
adjacent in $g^{\prime}(z)$ otherwise we would have $\omega(H)>\omega(G)$.
This means that $(T^{\prime},g^{\prime})$ is an independent
$\mathcal{C}$-tree-decomposition of $H$, so $H\in\mathcal{C}_{i}$. Thus, $H$
is $\omega(H)^{k+1}\leq\omega(G)^{k+1}$-colorable.
Let $v_{1},\ldots,v_{n}$ be the vertices of $H$. We have that $G$ can be
obtained by substituting each $v_{i}$ by some $G_{v_{i}}\in\mathcal{C}_{s}$.
We can assume that $G$ is connected since we can deal with each connected
component separately. Thus, we get that for every $i\in[n]$,
$d(G_{v_{i}})<d(G)$ (where $d$ stands for the depth). Futhermore, if $v_{i}$
is a vertex of $H$, it means that it is a leaf of $T^{\prime}$. Indeed, since
$\omega(G)\geq 3$, if $v_{i}\in X$ then $\omega(G_{v_{i}})\geq 2$ so $v_{i}$
has children in $T$. Thus, $v_{i}\notin X$, which means
$\omega(G_{v_{i}})\leq\omega(G)/2$. Let $\omega_{i}=\omega(G_{v_{i}})$. By
induction hypothesis, we have $\chi(G_{v_{i}})\leq\omega_{i}^{2k+3}$.
Let $m=\lfloor\log(\omega(G))\rfloor$. For $j\in[m]$, let
$V_{j}=\\{v_{i}:\frac{\omega(G)}{2^{j+1}}<\omega_{i}\leq\frac{\omega(G)}{2^{j}}\\}$.
Note that the $V_{j}$’s partition $\\{v_{1},\ldots,v_{n}\\}$. For $j\in[m]$,
let $H_{j}=H[V_{j}]$ and $G_{j}$ be the corresponding induced subgraph of $G$.

If $j\in[m]$ and $v_{i}\in V_{j}$ then $\omega_{i}>\frac{\omega(G)}{2^{j+1}}$
so $\omega(H_{j})\leq 2^{j+1}$. Thus, $\chi(H_{j})\leq 2^{(j+1)(k+1)}$ because
$H_{j}$ is an induced sugraph of $H\in\mathcal{C}_{i}$. Thus, we have
$\chi(G_{j})\leq
2^{(j+1)(k+1)}\cdot\left(\frac{\omega(G)}{2^{j}}\right)^{2k+3}$ (by doing the
product of the colorings). Now, let’s color separately each $V_{j}$ with a
different palette. The number of colors used is:

$\displaystyle\sum_{j=1}^{m}\chi(G_{j})$
$\displaystyle\leq\sum_{j=1}^{m}2^{(j+1)(k+1)}\cdot\left(\frac{\omega(G)}{2^{j}}\right)^{2k+3}$
$\displaystyle=2^{k+1}\omega(G)^{2k+3}\sum_{j=1}^{m}2^{-j(k+2)}$
$\displaystyle\leq 2^{k+1}\omega(G)^{2k+3}\frac{2^{-(k+2)}}{1-2^{-(k+2)}}$
$\displaystyle\leq\omega(G)^{2k+3}\times\frac{2^{k+2}}{2(2^{k+2}-1)}$
$\displaystyle\leq\omega(G)^{2k+3}$

##  7 Mixed extensions

We conclude with another type of class extension which preserves
$\chi$-boundedness. Given an ordered graph $G$ with vertex ordering
$v_{1},\dots,v_{n}$ (denoted by $<$), we only ask here that the restriction to
”mixed parts” of $G$ are $\chi$-bounded. Precisely, given a class $\cal C$ of
graphs, we say that $(G,<)$ is a _$\cal C$ -mixed extension_ if for every
partition $\cal P$ into intervals $I_{1},\dots,I_{k}$, the subgraph
$\text{Mix}(G,<,\cal P)$ of $G$ in which we only keep edges between intervals
$I_{s},I_{t}$ for which $I_{s},I_{t}$ is mixed, belongs to $\cal C$. The class
of graphs $G$ admitting a vertex-ordering $<$ such that $(G,<)$ is a $\cal
C$-mixed extension is denoted by ME$(\cal C)$.

Observe that graphs with twin-width at most $d$ are mixed extensions of the
class of graphs with chromatic number at most $f(d)$. To see this, observe
that they admit vertex-orderings with no large mixed-minors, hence the Marcus-
Tardos theorem implies that every partition $\cal P$ has a linear number of
mixed zones. So $\text{Mix}(G,<,\cal P)$ has bounded chromatic number by
degeneracy. Hence the fact that bounded twin-width graphs are $\chi$-bounded
is a particular case of the following result (whose proof mimics the one of
Proposition 2):

###### Theorem 6

If $\cal C$ is $\chi$-bounded, then ME$(\cal C)$ is $\chi$-bounded.

Proof. Assume that all graphs $H$ in $\mathcal{C}$ satisfy $\chi(H)\leq
f(\omega(H))$. Consider $G\in\cal C$ with clique number $\omega$ and assume
that we have already proved that the chromatic number of every graph in
$ME(\mathcal{C})$ with smaller value of $\omega$ is at most $c$. Consider $<$,
a vertex ordering $v_{1},\dots,v_{n}$ of $G$ such that $(G,<)$ is a $\cal
C$-mixed extension. Pick a smallest initial interval
$I_{1}=v_{1},\dots,v_{i_{1}}$ such that $G[I_{1}]$ has a clique of size
$\omega$. Then pick a smallest interval $I_{2}=v_{i_{1}+1},\dots,v_{i_{2}}$
such that $G[I_{2}]$ has a clique of size $\omega$, otherwise pick all
remaining vertices. Continue the process to get a partition $\cal P$ into
intervals $I_{1},\dots,I_{k}$. Observe that if there is an edge between
$I_{s}$ and $I_{t}$, where $s<t<k$, then $I_{s},I_{t}$ is mixed, otherwise one
of the intervals would be a module with respect to the other, and we would
find a clique of size $\omega+1$. Therefore the chromatic number of $G$ is at
most $(c+1)f(\omega)+c+1$ since $\chi(G[I_{k}])\leq c+1$ and
$G[I_{1}\cup\dots\cup I_{k-1}]$ is the edge union of two graphs, one of
chromatic number at most $c+1$ inside the $I_{i}$’s, and one of chromatic
number at most $f(\omega)$ across the $I_{i}$’s.

## References

  * [1] Marthe Bonamy and Michał Pilipczuk.  Graphs of bounded cliquewidth are polynomially $\chi$-bounded.  Advances in Combinatorics, (8):21pp, 2020.
  * [2] É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), volume 198 of Leibniz International Proceedings in Informatics (LIPIcs), pages 35:1–35:20, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [3] Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant.  Twin-width I: Tractable FO model checking.  J. ACM, 69(1), nov 2021.
  * [4] Marcin Briański, James Davies, and Bartosz Walczak.  Separating polynomial $\chi$-boundedness from $\chi$-boundedness, 2022\.
  * [5] Alvaro Carbonero, Patrick Hompe, Benjamin Moore, and Sophie Spirkl.  A counterexample to a conjecture about triangle-free induced subgraphs of graphs with large chromatic number.  Journal of Combinatorial Theory, Series B, 158:63–69, jan 2023\.
  * [6] Maria Chudnovsky, Irena Penev, Alex Scott, and Nicolas Trotignon.  Substitution and $\chi$-boundedness.  Journal of Combinatorial Theory, Series B, 103(5):567–586, 2013\.
  * [7] Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas.  The strong perfect graph theorem.  Annals of Mathematics, 164:51–229, 2006.
  * [8] James Davies and Rose McCarty.  Circle graphs are quadratically $\chi$-bounded.  Bulletin of the London Mathematical Society, 53(3):673–679, 2021\.
  * [9] Zdeněk Dvořák and Daniel Král’.  Classes of graphs with small rank decompositions are $\chi$-bounded.  European Journal of Combinatorics, 33(4):679–683, 2012.
  * [10] Xiaonan Liu, Joshua Schroeder, Zhiyu Wang, and Xingxing Yu.  Polynomial $\chi$-binding functions for $t$-broom-free graphs, 2021.
  * [11] Adam Marcus and Gábor Tardos.  Excluded permutation matrices and the Stanley-Wilf conjecture.  Journal of Combinatorial Theory - Series A, 107(1):153–160, July 2004.
  * [12] Michał Pilipczuk and Marek Sokołowski.  Graphs of bounded twin-width are quasi-polynomially $\chi$-bounded, 2022\.
  * [13] Alex Scott and Paul Seymour.  A survey of $\chi$-boundedness.  Journal of Graph Theory, 95(3):473–504, 2020.
  * [14] Alex Scott, Paul Seymour, and Sophie Spirkl.  Polynomial bounds for chromatic number IV. a near-polynomial bound for excluding the five-vertex path, 2022.
  * [15] Alex Scott, Paul Seymour, and Sophie Spirkl.  Polynomial bounds for chromatic number I. excluding a biclique and an induced tree.  Journal of Graph Theory, 102(3):458–471, 2023.


$\kappa_{i,j}$, $i,j\in\mathcal{S}_{N}$. Here,
$Q_{1}(\theta)=G(Q_{0}(u),\theta)$ and
$\partial_{q}G=\partial_{Y}G(Q_{0}(u),\theta_{0})$. Under standard conditions,
and as $N,S_{N}\to\infty$, the estimator has asymptotic linear representation
as follows:

$\displaystyle\sqrt{N}(\check{\theta}-\theta_{0})=$
$\displaystyle-(\partial_{\theta^{\prime}}G_{S_{N}}^{\prime}\boldsymbol{\kappa}_{S_{N}}\partial_{\theta^{\prime}}G_{S_{N}})^{-1}\partial_{\theta^{\prime}}G_{S_{N}}^{\prime}\boldsymbol{\kappa}_{G_{N}}\Big{[}\frac{1}{\sqrt{p}_{1}}\boldsymbol{f_{1}}^{-1}*\sqrt{N_{1}}F_{Y(1),S_{N}}+$
$\displaystyle\frac{\boldsymbol{\partial_{q}G}}{\sqrt{p}_{0}}*\boldsymbol{f_{0}}^{-1}*\sqrt{N_{0}}F_{Y(0),S_{N}}\Big{]}+o_{p}(1)\,,$

where $*$ denotes entry-by-entry multiplication,
${\boldsymbol{f}_{d}}^{-1}=\begin{pmatrix}\frac{1}{f_{d}(Q_{Y(d)}(s_{1})}&\frac{1}{f_{d}(Q_{Y(d)}(s_{2}))}&\ldots&\frac{1}{f_{d}(Q_{Y(d)}(s_{S_{N}}))}\end{pmatrix}^{\prime}$
and $\boldsymbol{\partial_{q}G}$ is similarly defined. First, we observe that:

$\frac{1}{f_{1}(Q_{1}(v))}=Q^{\prime}_{Y(1)}(v)=\partial_{q}G(Q_{0}(v);\theta_{0})\cdot\frac{1}{f_{0}(Q_{0}(v))}\,,$

which implies, by taking
$\mathcal{S}_{N}=\Big{\\{}\frac{1}{S_{N}+1},\frac{2}{S_{N}+1},\ldots,\frac{S_{N}}{S_{N}+1}\Big{\\}}$
and applying Lemma C.1. in Firpo et al. (2022), that we are able to show that
the variance of the estimator under optimal weights is:

$\mathbb{V}^{*}=((\partial
G_{S_{N}}*(\mathbf{1}_{d}^{\prime}\otimes\boldsymbol{f_{1}}))^{\prime}\Sigma_{S_{N}}^{-1}(\partial
G_{S_{N}}*(\mathbf{1}_{d}^{\prime}\otimes\boldsymbol{f_{1}})))^{-1}\,,$

where

$(\Sigma_{S_{N}}^{-1})_{s_{i},s_{j}}=p_{0}p_{1}[\mathbbm{1}_{\\{s_{i}=s_{j}\\}}2(S_{N}+1)-(\mathbbm{1}_{\\{s_{i}=s_{j+1}\\}}+\mathbbm{1}_{\\{s_{i}=s_{j-1}\\}})(S_{N}+1)]\,.$

Proceeding similarly as in Appendix G of ACM, we obtain that:

$\lim_{N\to\infty}\left(\mathbbm{V}^{*-1}\right)_{d_{1},d_{2}}=p_{0}p_{1}\int_{0}^{1}\frac{dH_{d_{1}}(v)}{dv}\Bigg{|}_{v=u}\frac{dH_{d_{2}}(v)}{dv}\Bigg{|}_{v=u}du\,,$

with $H_{d}(u)=f_{1}(Q_{1}(v))\partial_{\theta_{d}}G(Q_{0}(v),\theta_{0})$.
Next, proceeding similarly as in ACM, we conclude that:

$\left(\mathbbm{V}^{*-1}\right)_{d_{1},d_{2}}=p_{0}p_{1}(I(\theta_{0}))_{d_{1},d_{2}}\,,$

where $I(\theta_{0})$ is the Fisher information matrix of the parametric model
$\theta\mapsto f_{1}(y|\theta)$ that assumes $Q_{0}$ known. It then follows by
Lemma 1 of Athey et al. (2023) that the estimator is asymptotically efficient,
as it achieves the efficiency bound derived by the authors.

To conclude, we note that, since the $\\{P_{l}\\}_{l}$ form an orthonormal
basis, the estimator $\check{\theta}$ corresponds to GMLM that uses infinitely
many moments. We are then able to show, by reasoning similarly as in Appendix
G of ACM, that an estimator (15) that uses a finite but increasing number of
L-moments and a suitable choice of weights, is also efficient, since under an
appropriate choice of weights this estimator is asymptotically equivalent to
$\check{\theta}$. But then, since the optimally weighted GMLM estimator
minimises, for each $R$, the variance of the leading term of the approximation
(17), we conclude that it is also efficient.

###  B.3. Selecting the number of L-moments

In a parametric setting, ACM propose two methods to select the number of
L-moments. One method relies on higher-order expansions of the estimator
(Donald et al., 2009); whilst the other on regularised estimation of the
moment-combination matrix (Luo et al., 2015). Similarly, Athey et al. (2023)
propose a method to choose the trimming constants
$(\underline{p},\overline{p})$ based on minimization of an estimate of the
asymptotic variance of their estimator.272727See Crump et al. (2009) on an
earlier example of this approach in the context of observational studies.

While these different approaches can be extended to our semiparametric
estimator, we note that, in an experimental setting, both rely on tuning
hyperparameters in the same sample used in the analysis. Inasmuch as, in
finite samples, there is some room for overfitting, such approaches may
somewhat hinder the credibility of the analysis, going counter to one of the
primary goals of employing randomization in the first place (Athey and Imbens,
2017).

Motivated by these concerns, and inspired by the literature on synthetic
controls (Abadie, 2021), we propose a method to tune
$(R,\underline{p},\overline{p})$ which relies on availability of pre-treatment
data for the units in the experimental sample. Specifically, we assume that,
for each unit in the sample, we observe the outcome of interest $Y$ for pre-
treatment periods $t\in\\{-1,-2,\ldots,-T_{0}\\}$. In addition, we assume that
the semiparametric model (1) admits a “null effect” parameter value, i.e.
there exists a known $\tilde{\theta}\in\Theta$ such that:

$G(y;\tilde{\theta})=y,\quad\forall y\in\mathbb{R}\,.$

For each $t\in\\{-1,-2,\ldots,-T_{0}\\}$, let $\hat{\theta}(t;h)$ be the
“placebo” GMLM estimator that replaces $\hat{Q}_{d}$ with the empirical
quantiles of the outcome at the pre-treatment period $t$ in the group whose
post-treatment status is $d$. We denote by $h$ the set of hyperparameters used
in the estimation. Under the assumption that the treatment is not anticipated,
we would expect $\hat{\theta}(t;h)$ to be close to $\tilde{\theta}$.
Consequently, letting $\mathbf{H}$ denote a grid for the hyperparameters, we
propose to choose the hyperparameters $h^{*}$ by minimizing:

$h^{*}\operatorname{argmin}_{h\in\mathbf{H}}\frac{1}{T_{0}}\sum_{t=-1}^{-T_{0}}\lVert\hat{\theta}(t;h)-\tilde{\theta}\rVert_{2}^{2}\,.$

Our approach to calibrating the hyperparameters amounts to choosing those that
entail the best pre-treatment fit, where “fit” is to be understood as
minimising the average squared Euclidean distance between the estimated model
parameters and the “null effect” parameter value. Notice that, with a large of
number of pre-treatment periods, and assuming a law of large numbers holds at
the time series, our approach to calibration may be seen as minimising average
mean-squared error.

###  B.4. Monte Carlo exercise

We revisit an exercise in Athey et al. (2023), which is based on house price
data available in Linden and Rockoff (2008). Following Athey et al. (2023), we
independently draw two samples of size $\frac{N}{2}$ without replacement from
the price data, and label one of these as the treatment group. We contrast the
behaviour of four different estimators in estimating the (zero) population
average treatment effect: the difference-in-means estimator, Athey et al.’s
efficient influence function (EIF) estimator, and the optimally-weighted
semiparametric generalised L-moment estimator, with and without (upper-tail)
trimming. To select the hyperparameters in the GMLM, we generate $T_{0}=16$
pre-treatment periods by independently drawing from the price data.282828The
value of $T_{0}$ is chosen to more closely replicate the empirical application
in the main text, where $19$ pre-treatment periods are available. We consider
$N\in\\{500,1000,2000\\}$, and, for each sample size, run $1,000$
replications.

Table 7 reports results from employing the semiparametric location model
$Y(1)=\theta_{0}+Y(0)$. As we can see, the semiparametric methods are able to
provide substantial improvements over the nonparametric approach, both in
terms of root mean squared error and mean absolute error, as well as shorter
confidence intervals. The GMLM with no trimming offers further improvement in
estimation error over the EIF approach, with reductions in the root mean
squared error ranging from 50 ($N=2000$) to 180 ($N=500$) dollars. Confidence
intervals have coverage close to the nominal level. In this setting, trimming
does not appear to offer significant improvements: on the contrary, when
employing trimming, the J-test appears to slightly overreject, whereas the
non-trimmed version is closer to the nominal level.

Table 8 reports results from working with the data in logs. In this case, we
employ the semiparametric model $\log(Y(1))=\theta_{0}+\log(Y(0))$. In this
setting, both the difference-in-means and the semiparametric methods have a
similar performance. The J-test has rejection rate close to the nominal level
for both the trimmed and non-trimmed GMLM.

Table 7. Monte Carlo: model in levels

|  |  | 95% CI |  |
---|---|---|---|---|---
| RMSE | MAE | Coverage | Average length | J-test | Median R
N = 500 |  |  |  |  |  |
Difference in means | 11910.56 | 9614.08 | 0.95 | 46299.88 |  |
Efficient Influence Function | 6096.84 | 4893.39 | 0.98 | 27873.95 |  |
L-moment estimator (no trimming) | 5916.71 | 4720.83 | 0.94 | 22041.1 | 0.06 | 7
L-moment estimator (trimming) | 5928.17 | 4738.4 | 0.94 | 22095.1 | 0.08 | 7
N = 1000 |  |  |  |  |  |
Difference in means | 8340.56 | 6623.62 | 0.95 | 32743.11 |  |
Efficient Influence Function | 4324.92 | 3485.73 | 0.97 | 18901.91 |  |
L-moment estimator (no trimming) | 4253.06 | 3436.87 | 0.93 | 15112.15 | 0.06 | 8
L-moment estimator (trimming) | 4244.89 | 3430.02 | 0.92 | 15134.11 | 0.09 | 8
N = 2000 |  |  |  |  |  |
Difference in means | 5944.96 | 4756.24 | 0.95 | 23163.82 |  |
Efficient Influence Function | 3003.63 | 2398.17 | 0.97 | 12925.77 |  |
L-moment estimator (no trimming) | 2951.57 | 2339.18 | 0.94 | 11267.76 | 0.03 | 8
L-moment estimator (trimming) | 2937.56 | 2328.19 | 0.94 | 11187.06 | 0.08 | 8

Notes: outcomes are measured in dollars. The number of replications is set to
$1,000$. RMSE stands for root-mean squared error. MAE stands for mean absolute
error. The confidence intervals are based on a normal approximation and on an
estimate of the estimator’s asymptotic variance. Column J-test reports the
rejection rate of a test of overidentifying-restrictions based on the
J-statistic (19) at the 5% level.

Table 8. Monte Carlo: model in logs

|  |  | 95% CI |  |
---|---|---|---|---|---
| RMSE | MAE | Coverage | Average length | J-test | Median R
N = 500 |  |  |  |  |  |
Difference in means | 0.05 | 0.04 | 0.95 | 0.21 |  |
Efficient Influence Function | 0.04 | 0.03 | 0.96 | 0.17 |  |
L-moment estimator (no trimming) | 0.04 | 0.04 | 0.94 | 0.16 | 0.05 | 6
L-moment estimator (trimming) | 0.04 | 0.04 | 0.94 | 0.16 | 0.05 | 6
N = 1000 |  |  |  |  |  |
Difference in means | 0.04 | 0.03 | 0.94 | 0.15 |  |
Efficient Influence Function | 0.03 | 0.02 | 0.96 | 0.12 |  |
L-moment estimator (no trimming) | 0.03 | 0.02 | 0.94 | 0.11 | 0.05 | 6
L-moment estimator (trimming) | 0.03 | 0.02 | 0.93 | 0.11 | 0.06 | 6
N = 2000 |  |  |  |  |  |
Difference in means | 0.03 | 0.02 | 0.95 | 0.1 |  |
Efficient Influence Function | 0.02 | 0.02 | 0.95 | 0.08 |  |
L-moment estimator (no trimming) | 0.02 | 0.02 | 0.95 | 0.08 | 0.04 | 6
L-moment estimator (trimming) | 0.02 | 0.02 | 0.94 | 0.08 | 0.05 | 7

Notes: outcomes are measured in logs. The number of replications is set to
$1,000$. RMSE stands for root-mean squared error. MAE stands for mean absolute
error. The confidence intervals are based on a normal approximation and on an
estimate of the estimator’s asymptotic variance. Column J-test reports the
rejection rate of a test of overidentifying-restrictions based on the
J-statistic (19) at the 5% level.

##  Appendix C Additional results with nonparametric estimators

Figures 4 and 5 replicate Figures 2 and 3 in the main text, but replacing the
semiparametric estimators used in each aggregation with the corresponding
nonparametric estimators reported in Tables 2, 3, 4, and 5.

(a) Average

(b) Dispersion

Figure 4. Nonparametric estimates of effects of discounts on integrated rides

Notes: The figure plots estimates, along with 95% confidence intervals, of the
effects of each discount on the mean and dipersion of integrated rides across
the last two pre-treament fortnights (left of vertical dark line) and the
post-treatment window. We aggregate effects across prior train/metro usage by
averaging the nonparametric estimators discussed in the main text across $u$,
with weights given by the proportion of usage type $u$ in the sample.
Confidence intervals are computed using a normal approximation and the delta
method. For reference, the average number of integrated rides in the control
(no-discount) group in each fortnight is: 2018-10-29: 0.12; 2018-11-12: 0.11;
2018-11-26: 0.13; 2018-12-10: 0.14; 2018-12-24: 0.04; 2019-01-07: 0.11;
2019-01-21: 0.11; 2019-02-04: 0.08; 2019-02-18: 0.12; 2019-03-04: 0.1;
2019-03-18: 0.1; 2019-04-01: 0.12; 2019-04-15: 0.11; 2019-04-29: 0.08;
2019-05-13: 0.1; 2019-05-27: 0.09; 2019-06-10: 0.11; 2019-06-24: 0.11;
2019-07-08: 0.1.

(a) Average

(b) Dispersion

Figure 5. Nonparametrics estimates of discounts on non-integrated rides

Notes: The figure plots estimates, along with 95% confidence intervals, of the
effects of each discount on the mean and dipersion of non-integrated rides
across the last two pre-treament fortnights (left of vertical dark line) and
the post-treatment window. We aggregate effects across prior train/metro usage
by averaging the nonparametric estimators discussed in the main text across
$u$, with weights given by the proportion of usage type $u$ in the sample.
Confidence intervals are computed using a normal approximation and the delta
method. For reference, the average number of non-integrated rides in the
control (no-discount) group in each fortnight is: 2018-10-29: 2.14;
2018-11-12: 2.02; 2018-11-26: 2.23; 2018-12-10: 2.15; 2018-12-24: 1.24;
2019-01-07: 1.96; 2019-01-21: 2.11; 2019-02-04: 2.11; 2019-02-18: 2.27;
2019-03-04: 1.9; 2019-03-18: 2.05; 2019-04-01: 2.14; 2019-04-15: 1.97;
2019-04-29: 1.88; 2019-05-13: 1.73; 2019-05-27: 1.84; 2019-06-10: 1.74;
2019-06-24: 1.81; 2019-07-08: 1.52.