# Clique number of tournaments

Pierre Aboulker  DIENS, École normale supérieure, CNRS, PSL University, Paris,
France.  Guillaume Aubian  DIENS, École normale supérieure, CNRS, PSL
University, Paris, France.  Université de Paris, CNRS, IRIF, F-75006, Paris,
France.  Charles University, Prague, Czech Republic.  Pierre Charbit
Université de Paris, CNRS, IRIF, F-75006, Paris, France.  Raul Lopes  DIENS,
École normale supérieure, CNRS, PSL University, Paris, France.

###### Abstract

We introduce the notion of clique number of a tournament and investigate its
relation with the dichromatic number. In particular, it permits defining
$\operatorname{\overrightarrow{\chi}}$-bounded classes of tournaments, which
is the paper’s main topic.

###### Contents

  1. 1 Introduction
  2. 2 Definitions and Notations
  3. 3 $\chi$-bounded classes of tournaments
    1. 3.1 First properties about $\operatorname{\overrightarrow{\chi}}$ and $\operatorname{\overrightarrow{\omega}}$
    2. 3.2 Substitution and a class of tournaments with unbounded $\operatorname{\overrightarrow{\omega}}$
    3. 3.3 Do tournaments with bounded twin-width are dic-bounded?
  4. 4 Classes of tournaments defined by forbidding a single tournament
    1. 4.1 Gentlemen are the same as heroes
    2. 4.2 Gyárfás-Sumner Conjecture for tournaments
    3. 4.3 Relation with the Erdős-Hajnal property and the BIG-BIG conjecture
  5. 5 Local to Global - Links with domination number
  6. 6 Conclusion and future direction

##  1 Introduction

In this paper, we only consider _graphs_ or _directed graphs_ (_digraphs_ in
short) with no loops, no parallel edges or arcs nor anti-parallel arcs (in
particular our digraphs contain no cycle of length $2$).

Given an undirected graph $G$, we denote by $\omega(G)$ the size of a maximum
clique of $G$ and by $\chi(G)$ its chromatic number. Given a digraph $G$, we
denote by $\operatorname{\overrightarrow{\chi}}(G)$ its dichromatic number,
that is the minimum integer $k$ such that the set of vertices of $G$ can be
partitioned into $k$ acyclic subdigraphs.

Relations between the chromatic number and the clique number of a graph have
been studied for decades in structural graph theory. The goal of this paper is
to introduce a notion of clique number for digraphs, that would be a lower
bound for the dichromatic number as in the undirected case, and start to
investigate its relation with the dichromatic number.

Given a digraph $D$, and a total order $\prec$ on $V(D)$, we denote
$D^{\prec}$ the (undirected) graph with vertex set $V(D)$ and edge $uv$ if
$u\prec v$ and $vu\in A(D)$. We call it the _backedge graph_ of $D$ with
respect to $\prec$. It is straightforward that every independent set of
$D^{\prec}$ induces an acyclic digraph. As a consequence, we have that
$\operatorname{\overrightarrow{\chi}}(D)\leq\chi(D^{\prec})$. Conversely, by
taking an ordering built from a
$\operatorname{\overrightarrow{\chi}}(D)$-dicolouring, that is taking colour
classes one after the other, and ordering each colour class in a topological
ordering, we get that:

$\operatorname{\overrightarrow{\chi}}(D)=\min\,\big{\\{}\chi(D^{\prec}):\mbox{$\prec$
is a total order of $V(D)$}\big{\\}}$

This gives an alternative definition for the dichromatic number, which
naturally leads to the following definition of the _clique number of a
digraph_ 111This definition was introduced during a discussion between the
authors and Stéphan Thomassé in Sète during the fifth ANR Digraphs meeting.

$\operatorname{\overrightarrow{\omega}}(D)=\min\,\big{\\{}\omega(D^{\prec}):\mbox{$\prec$
is a total order on $V(D)$}\big{\\}}$

We point out that although this is the first time (up to our knowledge), that
this definition formally appears, the idea of looking at the clique number of
ordered digraphs is not new, and in the nice survey [22], Nguyen, Scott and
Seymour study (amongst other things) the clique number of backedge graphs of
tournaments, so the idea was clearly in their minds.

Obviously, since $\omega(G)\leq\chi(G)$ for any graph $G$, we also have
$\operatorname{\overrightarrow{\omega}}(D)\leq\operatorname{\overrightarrow{\chi}}(D)$
for any digraph $D$. In the context of graphs, since there are families of
graphs with clique number $2$ but an arbitrarily large chromatic number, there
has been in the past decades a very important amount of work dedicated to the
study of so-called $\chi$-bounded classes of graphs, that is classes for which
$\chi$ is bounded above by a function of $\omega$. See [24] for a survey on
$\chi$-boundedness. Analogously, we say that a class of digraphs is
_$\operatorname{\overrightarrow{\chi}}$ -bounded_ if there exists $f$ such
that for every digraph $D\in\mathcal{C}$,
$\operatorname{\overrightarrow{\chi}}(D)\leq
f(\operatorname{\overrightarrow{\omega}}(D))$. The object of the paper is to
give first results and conjectures about clique number of tournaments and
$\operatorname{\overrightarrow{\chi}}$-bounded classes of tournaments. We
briefly discuss clique number of general digraphs in Section 6.

Note that another definition of
$\operatorname{\overrightarrow{\chi}}$-boundedness is given in [1] where the
clique number of a digraph $D$ is defined as the maximum size of a transitive
tournament contained in $D$. (More precisely, it is defined as the size of a
maximum clique of the underlying of $D$, but since an orientation of the
complete graphs on $2^{k}$ vertices contains $TT_{k}$, if a class of oriented
graphs is $\operatorname{\overrightarrow{\chi}}$-bounded for one notion, it is
also $\operatorname{\overrightarrow{\chi}}$-bounded for the other). Such a
definition does not give a lower bound on the dichromatic number, which is the
reason why we were looking for another definition.

The next section is devoted to notations and definitions used throughout the
paper. Section 3 establishes some first properties of clique number, and
explores the connections between the clique number of a tournament and the
clique number of its backedge graphs. We then endeavour to extend standard
results on $\chi$-boundedness to tournaments. In subsection 3.2, we describe a
simple family having arbitrarily large clique number and prove that
$\operatorname{\overrightarrow{\chi}}$-boundedness of tournaments is preserved
by substitution (and a similar result for some classes of digraphs). We then
discuss in subsection 3.3 if, as in the undirected case, classes of
tournaments of bounded twin-width are
$\operatorname{\overrightarrow{\chi}}$-bounded.

A fruitful discussion when studying tournaments involves examining the class
of tournaments not containing a given tournament $T$, and deciding which $T$
will ensure that this class has a given property. For example, choices of $T$
guaranteeing a small dichromatic number [4] (such $T$ are called heroes), a
small domination number [10] or a small twin-width [15] have been studied
before. Section 4 is devoted to this for the property of being
$\operatorname{\overrightarrow{\chi}}$-bounded. In Section 4.1 we study
gentlemen, which are tournaments such that the clique number of tournaments
not containing them is bounded, and prove that gentlemen are the same as
heroes. In Subsection 4.2, we propose an analogue of Gyárfás-Summner
Conjecture for tournaments, proving multiple results supporting this
conjecture. We then link $\operatorname{\overrightarrow{\chi}}$-binding
tournaments to the famous Erdős-Hajnal property and to the $BIG\Rightarrow
BIG$ conjecture in Subsection 4.3.

Eventually, in Section 5, we discuss local to global results for clique
number, trying to adapt and generalize results of Harutyunyan, Le, Thomassé
and Wu in [19] about dichromatic number and domination number.

##  2 Definitions and Notations

Definitions and notations of this paper that are not explained in this section
follow from classical textbooks such as [3], [5] or [13].

Given two disjoint sets of vertices $X,Y$ of a digraph $D$, we write
$X\Rightarrow Y$ to say that for every $x\in X$ and for every $y\in Y$, $xy\in
A(D)$, and we write $X\rightarrow Y$ to say that every arc with one end in $X$
and the other one in $Y$ is oriented from $X$ to $Y$ (but some vertices of $X$
might be non-adjacent to some vertices of $Y$). When $X=\\{x\\}$ we write
$x\Rightarrow Y$ and $x\rightarrow Y$.

We also use the symbol $\Rightarrow$ to denote a composition operation on
digraphs: for two digraphs $D_{1}$ and $D_{2}$, $D_{1}\Rightarrow D_{2}$ is
the digraph obtained from the disjoint union of $D_{1}$ and $D_{2}$ by adding
all arcs from $V(D_{1})$ to $V(D_{2})$.

A _dominating set_ of a digraph $D$ is a set of vertices $X$ such that
$N^{+}[X]=V(D)$. The _dominating number_ $\operatorname{dom}(D)$ of $D$ is the
size of a smallest dominating set of $D$.

A _tournament_ is an orientation of a complete graph. A transitive tournament
is an acyclic tournament and we denote by $TT_{n}$ the unique acyclic
tournament on $n$ vertices.

Given three tournaments $T_{1},T_{2},T_{3}$, we denote by
$\Delta(T_{1},T_{2},T_{3})$ the tournament obtained from disjoint copies of
$T_{1},T_{2},T_{3}$ by adding arcs in such a way that $T_{1}\Rightarrow
T_{2}$, $T_{2}\Rightarrow T_{3}$ and $T_{3}\Rightarrow T_{1}$. If one or more
of the tournaments $T_{i}$ is a transitive tournament $TT_{k}$, we simplify
the notation by using its size $k$ instead of writing $TT_{k}$ in the $\Delta$
construction: for example, $\Delta(1,k,T)$ corresponds to
$\Delta(TT_{1},TT_{k},T)$ and $\Delta(1,1,1)$ is simply the directed triangle,
which we also denote by $C_{3}$.

A class of graphs (resp. digraphs) is a collection of graphs (resp. digraphs)
that is closed under induced subgraphs, meaning that if $G$ belongs to the
collection, then any induced subgraph of $G$ also belongs to the collection.
Given a collection $\mathcal{C}$ the hereditary closure of $\mathcal{C}$ is
the class of all induced subgraphs of elements of $\mathcal{C}$. Given a set
of digraphs $\mathcal{H}$, we say that a digraph $G$ is _$\mathcal{H}$ -free_
if it contains no member of $\mathcal{H}$ as an induced subgraph and denote by
$Forb(\mathcal{H})$ the class of $\mathcal{H}$-free digraphs. We write
$Forb(F_{1},\dots,F_{k})$ instead of $Forb(\\{F_{1},\dots,F_{k}\\})$ for
simplicity.

Because of the definition of $\operatorname{\overrightarrow{\omega}}$, this
paper is very often concerned with total orders on the vertices of a graph or
a tournament. For a graph or tournament $T$ we denote by $\mathfrak{S}(T)$ the
set of total orderings of $V(T)$. Given a graph or tournament with a total
ordering $\prec$ of its vertex set $V$ and two disjoint subsets $A,B$ of $V$,
we write $A\prec B$ to say that for every $a\in A$ and every $b\in B$, $a\prec
b$. For a digraph or tournament with a total ordering $\prec$ of its vertex
set $V$, an arc $uv$ such that $u\prec v$ is called forward, and otherwise it
is called backward. Recall that given a tournament $T$, and a total order
$\prec$ on $V(T)$, the backedge graph $T^{\prec}$ of $T$ with respect to
$\prec$ is the (undirected) graph with vertex set $V(T)$ and edges $uv$ if
$u\prec v$ and $vu\in A(T)$ (i.e. $vu$ is backward). An ordering $\prec$ such
that $\omega(T^{\prec})=\operatorname{\overrightarrow{\omega}}(T)$ (resp.
$\operatorname{\overrightarrow{\chi}}(T^{\prec})=\operatorname{\overrightarrow{\chi}}(T)$)
is called an _$\operatorname{\overrightarrow{\omega}}$ -ordering_ of $T$
(resp. $\operatorname{\overrightarrow{\chi}}$-ordering). We denote by
$\mathfrak{S}_{\operatorname{\overrightarrow{\omega}}}(T)$ the set of
$\operatorname{\overrightarrow{\omega}}$-orderings and by
$\mathfrak{S}_{\operatorname{\overrightarrow{\chi}}}(T)$ the set of
$\operatorname{\overrightarrow{\chi}}$-orderings.

##  3 $\chi$-bounded classes of tournaments

###  3.1 First properties about $\operatorname{\overrightarrow{\chi}}$ and
$\operatorname{\overrightarrow{\omega}}$

We begin with an easy fact relating the clique number of a digraph and the
clique number of its strong components.

######  Property 3.1.

The clique number of a digraph is equal to the maximum clique number of its
strong components.

###### Proof.

Assume a digraph $D$ has two strong components $A$ and $B$ such that
$A\rightarrow B$ and let us prove that
$\operatorname{\overrightarrow{\omega}}(D)=\max(\operatorname{\overrightarrow{\omega}}(A),\operatorname{\overrightarrow{\omega}}(B))$.
It is clear that
$\operatorname{\overrightarrow{\omega}}(D)\geq\max(\operatorname{\overrightarrow{\omega}}(A),\operatorname{\overrightarrow{\omega}}(B))$.
Let $\prec_{A}$ (resp. $\prec_{B}$) be an
$\operatorname{\overrightarrow{\omega}}$-ordering of $A$ (resp. of $B$). Then
the ordering of $D$ obtained from $\prec_{A}$ and $\prec_{B}$ by setting, for
every $a\in V(A)$ and $b\in V(B)$, $b\prec a$ satisfies
$\omega(D^{\prec})=\max(\operatorname{\overrightarrow{\omega}}(A),\operatorname{\overrightarrow{\omega}}(B))$.
∎

As observed in the introduction, the definition of
$\operatorname{\overrightarrow{\omega}}$ immediately implies that
$\operatorname{\overrightarrow{\omega}}(T)\leq\operatorname{\overrightarrow{\chi}}(T)$
for any tournament $T$. The following proves a relation with the domination
number. In Section 5 we will expose some other results linking
$\operatorname{dom}$, $\operatorname{\overrightarrow{\chi}}$ and
$\operatorname{\overrightarrow{\omega}}$

######  Property 3.2.

For every tournament $T$,
$\operatorname{dom}(T)\leq\operatorname{\overrightarrow{\omega}}(T)\leq\operatorname{\overrightarrow{\chi}}(T)$.

###### Proof.

We already know that the second inequality holds. Let $T$ be a tournament, set
$V(T)=\\{v_{1},\dots,v_{n}\\}$ and assume that $v_{1}\prec
v_{2}\prec\dots\prec v_{n}$ is an $\operatorname{\overrightarrow{\omega}}$
ordering of $T$. Greedily construct a dominating set $X$ of $T$ as follows:
$v_{1}\in X$, and if $v_{i}$ is the last vertex added to $X$, add $v_{j}$ to
$X$ where $j$ is minimum such that there is an arc from $v_{j}$ to every
vertex of $X$. Then $X$ is a dominating set of $T$, and it induces a clique in
the backedge graph of $T$ defined by an
$\operatorname{\overrightarrow{\omega}}$-ordering. So
$\operatorname{dom}(T)\leq\operatorname{\overrightarrow{\omega}}(T)$. ∎

In [22], the following fundamental inequality is proved (the second inequality
is trivial by definition). We give a proof anyway, to make the paper self-
contained and familiarize the reader with the notations. Moreover our prove is
presented slightly differently then the one in [22].

######  Theorem 3.3 ([22]).

For any tournament $T$ and ordering $\prec$ of $V(T)$.

$\frac{\chi(T^{\prec})}{\omega(T^{\prec})}\leq\operatorname{\overrightarrow{\chi}}(T)\leq\chi(T^{\prec})$

###### Proof.

Let $T$ be a tournament and $\prec$ an ordering of $V(T)$. Let $X\subseteq
V(T)$ such that $T[X]$ is a transitive tournament. To prove that
$\chi(T^{\prec})\leq\omega(T^{\prec})\operatorname{\overrightarrow{\chi}}(T)$,
it suffices to prove that $\chi(T^{\prec}[X])\leq\omega(T^{\prec})$.

Let $\varphi:X\to\mathbb{N}$ be such that $\varphi(x)$ is the number of
vertices of a longest $\prec$-decreasing path in $T^{\prec}[X]$ finishing in
$x$. We claim that $\varphi$ is a $\omega(T^{\prec})$-colouring of
$T^{\prec}$. Let $u,v\in X$ with $u\prec v$ and $uv\in E(T^{\prec})$. Then
$\varphi(u)\geq\varphi(v)+1$, so $\varphi$ is a colouring of $T^{\prec}[X]$.
If $x_{1},x_{2},x_{3}\in X$, $x_{3}\prec x_{2}\prec x_{1}$ and
$x_{1}x_{2},x_{2}x_{3}\in E(T^{\prec})$, then $x_{1}x_{2},x_{2}x_{3}\in A(T)$
and thus, since $T[X]$ is a transitive tournament, $x_{1}x_{3}\in A(T)$, i.e.
$x_{1}x_{3}\in E(T^{\prec})$. This implies that the vertices of a
$\prec$-decreasing path in $T^{\prec}[X]$ induces a clique of $T^{\prec}$. So
for every vertex $x\in X$, $\varphi(x)\leq\omega(T^{\prec})$. ∎

Observe that for an aribtrary order $\prec$, $\omega(T^{\prec})$ and
$\chi(T^{\prec})$ can be arbitrarily larger than
$\operatorname{\overrightarrow{\omega}}(T)$ or
$\operatorname{\overrightarrow{\chi}}(T)$. For example, there is an ordering
$\prec$ of $TT_{n}$ such that $\omega(T^{\prec})=\chi(T^{\prec})=n$, while
$\operatorname{\overrightarrow{\omega}}(TT_{n})=\operatorname{\overrightarrow{\chi}}(TT_{n})=1$.
However, an $\operatorname{\overrightarrow{\omega}}$-ordering always provides
a good approximation of $\operatorname{\overrightarrow{\chi}}$ in the
following sense:

######  Property 3.4.

For every tournament $T$ and every
$\operatorname{\overrightarrow{\omega}}$-ordering $\prec$ we have:

$\operatorname{\overrightarrow{\chi}}(T)\leq\chi(T^{\prec})\leq\operatorname{\overrightarrow{\chi}}(T)^{2}$

###### Proof.

Let $T$ be a tournament and $\prec$ an
$\operatorname{\overrightarrow{\omega}}$-ordering of $T$. By Theorem 3.3, we
have that
$\chi(T^{\prec})\leq\omega(G^{\prec})\operatorname{\overrightarrow{\chi}}(T)$.
But since $\omega(G^{\prec})=\operatorname{\overrightarrow{\omega}}(T)$ and
$\operatorname{\overrightarrow{\omega}}(T)\leq\operatorname{\overrightarrow{\chi}}(T)$,
we get that:

$\operatorname{\overrightarrow{\chi}}(T)\leq\chi(T^{\prec})\leq\operatorname{\overrightarrow{\chi}}(T)^{2}$

∎

It is natural to ask if the following stronger form of the above property
holds (we have no reason to believe it does, but we could not find a counter-
example).

######  Question 3.5.

Is it true that for every tournament $T$, there exists
$\prec\in\mathfrak{S}(T)$ such that $\prec$ is both a
$\operatorname{\overrightarrow{\omega}}$-ordering and a
$\operatorname{\overrightarrow{\chi}}$-ordering?

Given a class of tournaments $\mathcal{T}$, let us denote by
$\mathcal{T}^{\prec}$ the class of all backedge graphs of tournaments in
$\mathcal{T}$ :

$\mathcal{T}^{\prec}=\\{T^{\prec}:T\in\mathcal{T},\prec\in\mathfrak{S}(T)\\}$

A natural question is whether $\mathcal{T}$ is
$\operatorname{\overrightarrow{\chi}}$-bounded has to do with the fact that
$\mathcal{T}^{\prec}$ is $\chi$-bounded in the usual sense for undirected
graphs. And one can ask the same question for the more restricted class of
"optimal" backedge graphs
$\mathcal{T}^{\prec_{\operatorname{\overrightarrow{\omega}}}}$ :

$\mathcal{T}^{\prec_{\operatorname{\overrightarrow{\omega}}}}=\\{T^{\prec}:T\in\mathcal{T},\prec\in\mathfrak{S}_{\operatorname{\overrightarrow{\omega}}}(T)\\}$

The following theorem answers these questions.

######  Theorem 3.6.

Let $\mathcal{T}$ be a class of tournaments. The following properties are
equivalent:

  1. (i)

$\mathcal{T}$ is $\operatorname{\overrightarrow{\chi}}$-bounded.

  2. (ii)

$\mathcal{T}^{\prec}$ is $\chi$-bounded.

  3. (iii)

$\mathcal{T}^{\prec_{\operatorname{\overrightarrow{\omega}}}}$ is
$\chi$-bounded.

###### Proof.

$(i)\Rightarrow(ii)$: let $f$ be a function such that any tournament
$T\in\mathcal{T}$ satisfies $\operatorname{\overrightarrow{\chi}}(T)\leq
f(\operatorname{\overrightarrow{\omega}}(T))$. Now for any tournament
$T\in\mathcal{T}$ and $\prec\in\mathfrak{S}(T)$.

$\displaystyle\chi(T^{\prec})$
$\displaystyle\leq\omega(T^{\prec})\operatorname{\overrightarrow{\chi}}(T)$ by
Theorem 3.3
$\displaystyle\leq\omega(T^{\prec})f(\operatorname{\overrightarrow{\omega}}(T))$
by $(i)$ $\displaystyle\leq\omega(T^{\prec})f(\omega(T^{\prec}))$

$(ii)\Rightarrow(iii)$ is trivial since
$\mathcal{T}^{\prec_{\operatorname{\overrightarrow{\omega}}}}\subset\mathcal{T}^{\prec}$

$(iii)\Rightarrow(i)$: let $g$ be a function such that for every
$T\in\mathcal{T}$ and for every
$\prec\in\mathfrak{S}_{\operatorname{\overrightarrow{\omega}}}(T)$,
$\chi(T^{\prec})\leq g(\omega^{\prec}(T))$. Now for any $T\in\mathcal{T}$ and
$\prec\in\mathfrak{S}_{\operatorname{\overrightarrow{\omega}}}(T)$.

$\operatorname{\overrightarrow{\chi}}(T)\leq\chi(T^{\prec})\leq
g(\omega(T^{\prec}))=g(\operatorname{\overrightarrow{\omega}}(T))\\\ $

∎

In a converse manner, given a class of undirected graphs $\mathcal{C}$, one
can define $\mathcal{T}[\mathcal{C}]$ as the set of tournaments $T$ that
admits a backedge graph belonging to $\mathcal{C}$. This operation has already
been used to construct classes of tournaments with nice properties, see for
example [22]. More formally:

$\mathcal{T}[\mathcal{C}]=\\{T:T\mbox{ is a tournament such that there
exists}\prec\in\mathfrak{S}(T)\mbox{ with }T^{\prec}\in\mathcal{C}\\}$

It is natural to wonder if, given a $\chi$-bounded class of undirected graph
$\mathcal{C}$, the class of tournaments $\mathcal{T}[\mathcal{C}]$ is
$\operatorname{\overrightarrow{\chi}}$-bounded. It turns out that the answer
is no as we explain now.

Given a graph $G$, denote by $G^{c}$ be the complement of $G$, that is the
graph $\big{(}V(G),\binom{V(G)}{2}\setminus E(G)\big{)}$, and set
$\mathcal{C}^{c}=\\{G^{c}:G\in\mathcal{C}\\}$.

######  Property 3.7.

Let $\mathcal{C}$ be a class of undirected graphs. Then
$\mathcal{C}^{c}\subseteq\mathcal{T}[\mathcal{C}]^{\prec}$.

###### Proof.

Let $G\in\mathcal{\mathcal{missing}}C$. Let $T$ and $\prec$ be such that
$T^{\prec}=G$. Denoting $\prec_{r}$ the reverse ordering of $\prec$, we get
that $T^{\prec_{r}}=G^{c}\in\mathcal{T}[\mathcal{C}]^{\prec}$. Hence,
$\mathcal{C}^{c}\subseteq\mathcal{T}[\mathcal{C}]$. ∎

Let now $\mathcal{C}$ be the class of graphs with stability number at most
$2$. Then for every $G\in\mathcal{C}$,
$\chi(G)\leq|V(G)|\leq\omega(G)+\omega(G)^{2}$ (by Ramsey theory), so
$\mathcal{C}$ is $\chi$-bounded. But $\mathcal{T}[\mathcal{C}]^{\prec}$
contains $\mathcal{C}^{c}$, the class of triangle-free graphs and is thus not
$\chi$-bounded. By Theorem 3.6, this implies that $\mathcal{T}[\mathcal{C}]$
is not $\operatorname{\overrightarrow{\chi}}$-bounded.

###  3.2 Substitution and a class of tournaments with unbounded
$\operatorname{\overrightarrow{\omega}}$

We start this section by giving a simple and natural construction of
tournaments with arbitrarily large clique number. Let
$\widetilde{S}_{1}=TT_{1}$ and inductively, for $n\geq 1$, let
$\widetilde{S}_{n}=\Delta(\widetilde{S}_{n-1},\widetilde{S}_{n-1},\widetilde{S}_{n-1})$.

######  Lemma 3.8.

For any integer $n$,
$\operatorname{\overrightarrow{\omega}}(\widetilde{S}_{n})\geq n$

###### Proof.

It is clear that
$\operatorname{\overrightarrow{\omega}}(\widetilde{S}_{1})=1$. Let $n\geq 2$
and let $A,B,C$ be the partition of $V(\widetilde{S}_{n})$ such that each set
induces a copy of $\widetilde{S}_{n-1}$ and $A\Rightarrow B\Rightarrow
C\Rightarrow A$. Let $\prec$ be an
$\operatorname{\overrightarrow{\omega}}$-ordering of $\widetilde{S}_{n}$.

Let $a$ be the first vertex of $\prec$ and assume without loss of generality
that $a\in A$. By definition of $\operatorname{\overrightarrow{\omega}}$,
there exists a clique in the backedge graph of $T[C]=\widetilde{S}_{n-1}$ with
respect to $\prec$ that is of size at least
$\operatorname{\overrightarrow{\omega}}(\widetilde{S}_{n-1})$, which, together
with vertex $a$, form a clique of $\widetilde{S}_{n}^{\prec}$ of size
$1+\operatorname{\overrightarrow{\omega}}(\widetilde{S}_{n-1})\leq\operatorname{\overrightarrow{\omega}}(\widetilde{S}_{n})$,
the desired bound. ∎

It is also easy to see that
$\operatorname{\overrightarrow{\chi}}(\widetilde{S}_{n})\leq
2\operatorname{\overrightarrow{\chi}}(\widetilde{S}_{n-1})$ since one can
colour two copies of $\widetilde{S}_{n-1}$ with
$\operatorname{\overrightarrow{\chi}}(\widetilde{S}_{n-1})$ colours, and then
use $\widetilde{S}_{n-1}$ new colours for the third copy. So
$\operatorname{\overrightarrow{\chi}}(S_{n})\leq 2^{n}\leq
2^{\operatorname{\overrightarrow{\omega}}(\widetilde{S}_{n})}$ (in fact one
can improve this to $3/2$ instead of $2$). One can wonder whether this
inequality is still true for any $T$ in the hereditary closure of the family
$\\{\widetilde{S}_{n}\mid n\in\mathbf{N}\\}$, that is for $T$ being a
subtournament of some $\widetilde{S}_{n}$. It is in fact not obvious that this
hereditary closure is even $\chi$-bounded (a subtournament of
$\widetilde{S}_{n}$ can have clique number much smaller than $n$). Our next
Theorem 3.9 implies that $\operatorname{\overrightarrow{\chi}}(T)\leq
9^{\operatorname{\overrightarrow{\omega}}(T)}$ for every tournament $T$ in
this class. This is due to the fact that this class can also be defined
through the operation of substitution, defined below.

Given two digraphs $D_{1}$ and $D_{2}$ with disjoint vertex sets, a vertex
$u\in V(D_{1})$, and a digraph $D$, we say that $D$ is obtained by
substituting $D_{2}$ for $u$ in $D_{1}$ provided that the following holds:

  * •

$V(D)=(V(D_{1})\setminus u)\cup V(D_{2})$,

  * •

$D[V(D_{1})\setminus u]=D_{1}\setminus u$,

  * •

$D[V(D_{2})]=D_{2}$,

  * •

for all $v\in V(D_{1})\setminus u$ if $vu\in A(D_{1})$ (resp. $uv\in
A(D_{1})$, resp. $u$ and $v$ are non-adjacent in $D_{1}$), then
$V(H_{1})\Rightarrow v$ (resp. $v\Rightarrow V(D_{2})$, resp. there is no arcs
between $v$ and $V(D_{2})$) in $D$.

Given a class of digraphs $\mathcal{C}$ we define $\mathcal{C}^{subst}$ to be
the closure of $\mathcal{C}$ under substitution.

It is a well-known easy-to-prove fact that, if a class of (undirected) graphs
is $\chi$-bounded, so is $\mathcal{C}^{subst}$. The first item of the
following theorem proves the analogue for classes of tournaments. The second
item applies to classes of digraphs (instead of tournaments) but only in the
case of families of digraphs whose underlying graphs have bounded chromatic
number. In that case we get a better
$\operatorname{\overrightarrow{\chi}}$-binding function.

######  Theorem 3.9.

Let $\mathcal{T}$ be a class of digraphs.

  1. 1.

If $\mathcal{T}$ is a class of tournaments
$\operatorname{\overrightarrow{\chi}}$-bounded by a function $f$, then
$\mathcal{T}^{subst}$ is $\operatorname{\overrightarrow{\chi}}$-bounded by
function $g(w)=(3wf(w))^{w}$.

  2. 2.

If there exists $K$ such that for every digraph $D$ in $\mathcal{T}$ the
underlying graph of $D$ has chromatic number at most $K$, then
$\mathcal{T}^{subst}$ is $\operatorname{\overrightarrow{\chi}}$-bounded by
function $g(w)=(3K)^{w}$.

###### Proof.

We will prove the two statements simultaneously, as the difference only occurs
at one particular point of the proof. We want to prove that for every
$T\in\mathcal{T}^{subst}$, $\operatorname{\overrightarrow{\chi}}(T)\leq
g(\operatorname{\overrightarrow{\omega}}(T))$. Assume by contradiction that
the result does not hold and let $T\in\mathcal{T}^{subst}$ be a counter-
example minimizing $\operatorname{\overrightarrow{\omega}}(T)+|V(T)|$. We
refer to this by saying “by minimality of $T$”.

Define $w:=\operatorname{\overrightarrow{\omega}}(T)$ and observe that $w\geq
2$ since if $\operatorname{\overrightarrow{\omega}}(T)=1$, then $T$ is acylic,
so $\operatorname{\overrightarrow{\chi}}(T)=1$ and the result holds.

Since $T\in\mathcal{T}^{subst}$, $T$ can be constructed from a digraph
$X\in\mathcal{T}$, with $|V(X)|\geq 2$, by substituting each vertex $v\in
V(X)$ by a digraph $T_{v}\in\mathcal{T}^{subst}$. For any set of vertices
$Y\subseteq V(X)$, we define $T_{Y}=T[\cup_{y\in Y}V(T_{y})]$. We call a
vertex $v\in X$ _big_ if

$\operatorname{\overrightarrow{\chi}}(T_{v})\geq 2g(w-1)+3$

and _small_ otherwise. We call $B$ the set of big vertices and $S$ the set of
small vertices (so $V(X)=B\cup S$).

Let $\prec$ be an $\operatorname{\overrightarrow{\omega}}$-ordering of $T$. We
are going to construct, in two steps, a dicolouring of $T$ using at most
$g(w)$ colours. First we colour the vertices of $T_{S}$ with at most $g(w)$
colours in such a way that for every small vertex $s$ the digraph $T_{s}$ is
properly dicoloured, and with the additional property that if $xy$ is a
backward arc of $T$ such that there is two distinct small vertices $s$ and
$s^{\prime}$ such that $x\in T_{s}$ and $y\in T_{s^{\prime}}$, then $x$ and
$y$ receive distinct colours. Secondly we use induction to colour the vertices
of $T_{B}$ and argue that no directed cycle is monochromatic.

For the first step, we distinguish between the two cases of the theorem’s
statement. For both cases, we set $\phi_{s}$ to be a dicolouring of $T_{s}$
using at most $2g(w-1)+2$ colours (such a dicolouring exists by definition of
$S$).

  * •

In case $1$ we observe that since $X\in\mathcal{T}$ and
$\operatorname{\overrightarrow{\omega}}(X)\leq\operatorname{\overrightarrow{\omega}}(T)=w$,
we have $\operatorname{\overrightarrow{\chi}}(X)\leq f(w)$ and thus there
exists a colouring $\phi$ of $X[S]$ using at most $f(w)$ colours. We colour
the vertices of $T_{S}$ by a Cartesian product of colourings: for each $s\in
S$, each vertex $x\in T_{s}$ receives the colour $(\phi(s),\phi_{s}(x))$. It
is clear that this yields a dicolouring of $T_{S}$ using at most
$f(w)(2g(w-1)+2)$ distinct colours. Now, by Theorem 3.3, we have:

$\chi(T_{S}^{\prec})\leq\omega(T_{S}^{\prec})\operatorname{\overrightarrow{\chi}}(T_{S})\leq
wf(w)(2g(w-1)+2)\leq 3wf(w)g(w-1)\leq g(w)$

A colouring of $T_{S}^{\prec}$ with at most $g(w)$ gives a dicolouring of
$T_{S}$ such that no backward arc is monochromatic, which implies the property
described in the previous paragraph.

  * •

In case $2$, we apply a similar approach. Define $H$ to be the undirected
graph with vertex set $S$ and with an edge $ss^{\prime}$ if $ss^{\prime}$ is
an arc of $X$ and there exists $x\in T_{s}$ and $y\in T_{s^{\prime}}$ with
$y\prec x$.

Observe that $H$ is a subgraph of the underlying graph of $X[S]$ so by
assumption there exists a colouring $\phi$ of $H$ using at most $K$ colours.

We colour the vertices of $T_{S}$ again by a Cartesian product of colourings:
each vertex $x\in T_{s}$ receives the colour $(\phi(s),\phi_{s}(x))$. This
colouring uses at most $K(2g(w-1)+2)\leq g(w)$ colours and satisfies the
desired property: no $T_{s}$ contains a monochromatic directed cycle (because
of $\phi_{s}$) and if $xy$ is a backward arc of $T$ such that there is two
distinct small vertices $s$ and $s^{\prime}$ such that $x\in T_{s}$ and $y\in
T_{s^{\prime}}$, then $ss^{\prime}\in E(H)$ and thus
$\phi(s)\neq\phi(s^{\prime})$ which implies that $x$ and $y$ receive distinct
colours as desired.

For the second step, we first observe that for each big vertex $b\in B$, the
digraph $T_{b}$ has strictly less vertices then $T$ (because $X$ has at least
two vertices), so by minimality of $T$ we have
$\operatorname{\overrightarrow{\chi}}(T_{b})\leq
g(\operatorname{\overrightarrow{\omega}}(T_{b}))\leq g(w)$. Moreover since $b$
is big, $\operatorname{\overrightarrow{\chi}}(T_{b})>g(w-1)$ , so by
minimality of $T$ we also get
$\operatorname{\overrightarrow{\omega}}(T_{b})=w$.

For each $b\in B$, and each $x\in T_{b}$, we define the two following
digraphs:

$T_{b}[\prec x]=T[\\{u\in V(T_{b}):u\prec x\\}]\text{ and
}T_{b}[x\prec]=T[\\{u\in V(T_{b}):x\prec u\\}]$

and, since $\operatorname{\overrightarrow{\chi}}(T_{b})\geq 2g(w-1)+3$, there
is a vertex $m_{b}\in V(T_{b})$ such that

$\operatorname{\overrightarrow{\chi}}(T_{b}[\prec m_{b}])\geq g(w-1)+1\text{
and }\operatorname{\overrightarrow{\chi}}(T_{b}[m_{b}\prec])\geq g(w-1)+1$

Hence, by minimality of $T$, for every $b\in B$:

$\operatorname{\overrightarrow{\omega}}(T_{b}[\prec m_{b}])\geq w\text{ and
}\operatorname{\overrightarrow{\omega}}(T_{b}[m_{b}\prec])\geq w$

Let $b\in B$. We claim that the inequalities above imply that if $m_{b}$ is
incident to a backward arc, then the other extremity of the arc is in $T_{b}$.
There are two symmetric cases (depending on whether $m_{b}$ is the tail or the
head of the backward arc), so let us assume by contradiction that $xm_{b}$ is
an backward arc and $x\in T_{x}$, $x\neq b$. Then because of the substitution
$xm_{b}\in A(T)$ implies that $xy\in A(T)$ for any $y\in T_{b}$. In particular
$xy\in A(T)$ for any $y\in T_{b}[\prec m_{b}]$. Since
$\operatorname{\overrightarrow{\omega}}(T_{b}[\prec m_{b}])\geq w$, a clique
of size $w$ in $T_{b}[\prec m_{b}]^{\prec}$ together with $y$ form a clique of
size $w+1$ in $T^{\prec}$, a contradiction. The argument is exactly the same
if $m_{b}x$ is an arc with $x\prec m_{b}$ because
$\operatorname{\overrightarrow{\omega}}(T_{b}[m_{b}\prec])$ also equals $w$.

We are now ready to conclude. Consider the colouring of $V(T_{S})$ obtained in
the first step of the proof and extend it to $V(T)$ by assigning to the
vertices of each $T_{b}$ for $b$ big a valid dicoulouring using at most $g(w)$
colours (remember that we showed that
$\operatorname{\overrightarrow{\chi}}(T_{b})\leq g(w)$). We claim that this
defines a valid dicolouring of $T$. Assume by contradiction that there exists
a monochromatic directed cycle and let $C$ be a minimal such cycle. Since for
a fixed $x\in V(X)$, any two vertices in $V(T_{x})$ share the same adjacency
relation with each vertex of $V(T)\setminus V(T_{x})$, the minimality of $C$
implies that $C$ contains at most one vertex of $V(T_{x})$ for any $x\in
V(X)$, for otherwise $C$ would be entirely included into some $T_{x}$, which
is not possible since the colouring is valid dicolouring on each digraph
$T_{x}$. Now define $C^{\prime}$ to be the directed cycle obtained from $C$ by
replacing each vertex belonging to $V(T_{b})$ for some $b\in B$ by the vertex
$m_{b}$. Since $C^{\prime}$ is a directed cycle, it must contain some backward
arc, i.e. some arc $uv$ with $v\prec u$. Since $u$ and $v$ do not belong to
the same $T_{x}$, and because of the property of the vertices $m_{b}$ proven
in the previous paragraph, both vertices $u$ and $v$ belong to $T_{S}$. But
then they are vertices of $C$ and the arc $uv$ is thus monochromatic and
backward, which contradicts the property of the colouring of $T_{S}$
established in the first step of the proof. ∎

Note that the hereditary closure of $\\{\widetilde{S}_{n},n\in\mathbb{N}\\}$
mentioned earlier is easily seen to be exactly
$\\{TT_{1},TT_{2},\overrightarrow{C_{3}}\\}^{subst}$. Therefore the first item
implies $\operatorname{\overrightarrow{\chi}}(T)\leq
9^{\operatorname{\overrightarrow{\omega}}(T)}$ for any $T$ which is a
subtournament of some $\widetilde{S}_{n}$. We do not know if this class is
$\operatorname{\overrightarrow{\chi}}$-bounded by a polynomial function. One
can prove for example that that the order of magnitude of
$\operatorname{\overrightarrow{\chi}}(\widetilde{S}_{n})$ is $(3/2)^{n}$ but
it could be that the lower bound
$\operatorname{\overrightarrow{\omega}}(\widetilde{S}_{n})\geq n$ given by
Lemma 3.8 is far from tight.

Chudnovsky, Penev, Scott and Trotignon [11] proved that if a class of graphs
is $\chi$-bounded by a polynomial function, so is its closure under
substitution. Could it be that the same holds for tournaments?

######  Question 3.10.

Is it true that if a class of tournaments $\mathcal{T}$ is polynomially
$\operatorname{\overrightarrow{\chi}}$-bounded, then so is
$\mathcal{T}^{subst}$.

Before closing this section on substitutions we mention here another sequence
of tournaments belonging to
$\\{TT_{1},TT_{2},\overrightarrow{C_{3}}\\}^{subst}$ that will be of use in
the proof of Theorem 4.2. Let $S_{1}=TT_{1}$ and inductively, for $n\geq 2$,
let $S_{n}=\Delta(1,S_{n-1},S_{n-1})$. It is easy to observe that
$\operatorname{\overrightarrow{\chi}}(S_{n})=n$. Since $S_{n}$ is obviously a
subtournament of $\widetilde{S}_{n}$, we have therefore
$\operatorname{\overrightarrow{\omega}}(S_{n})\geq\log_{9}(n)$. Again it could
be that this logarithm is not necessary. It is clear that
$\operatorname{\overrightarrow{\omega}}(S_{1})=1$,
$\operatorname{\overrightarrow{\omega}}(S_{2})=2$ and it is not hard (but a
bit laborious) to prove that $\operatorname{\overrightarrow{\omega}}(S_{3})=2$
and $\operatorname{\overrightarrow{\omega}}(S_{4})=3$. The clique number of
$S_{k}$ for $k\geq 5$ is not known but we doubt that one can compute an exact
formula for it.

###  3.3 Do tournaments with bounded twin-width are
$\operatorname{\overrightarrow{\chi}}$-bounded?

_Twin-width_ is a parameter introduced in [7] measuring the complexity of a
binary structure. We refer to [15] for the definitions of the twin-width of a
graph, an ordered graph and a tournament. Given a graph or digraph $G$ and a
total order $\prec$ on $V(G)$, we denote by $tww(G)$ the twin-width of $G$ and
by $tww(G,\prec)$ the twin-width of the ordered graph (digraph) $(G,\prec)$.

Classes of graphs of bounded twin-width have been shown to be $\chi$-bounded
[6, 23], and even polynomially $\chi$-bounded [8].

######  Theorem 3.11 ([8]).

For every $k\geq 1$, the class of undirected graphs with twin-width at most
$k$ is polynomially $\chi$-bounded.

Observe that for every integer $k\geq 2$, $S_{k}$ has twin-width $1$ and
dichromatic number $k$, so tournaments with bounded twin-width can have
arbitrarily large dichromatic number.

######  Conjecture 3.12.

Let $k\geq 1$. The class of tournaments with twin-width at most $k$ is
$\operatorname{\overrightarrow{\chi}}$-bounded.

Given a tournament $T$ and an ordering $\prec$ of $V(T)$, we denote by
$(T,\prec)$ the ordered tournament with ordering $\prec$, and by
$(T^{\prec},\prec)$ the ordered backedge graph with ordering $\prec$. The
following conjecture implies Conjecture 3.12.

######  Conjecture 3.13.

There exists a function $f$, such that for every tournament $T$, there exists
an ordering $\prec^{*}$ of $V(T)$ such that:

$\omega(T^{\prec^{*}})\leq
f(\operatorname{\overrightarrow{\omega}}(T))\quad\text{ and }\quad
tww(T,\prec^{*})\leq f(tww(T))$

######  Theorem 3.14.

Conjecture 3.13 implies Conjecture 3.12.

###### Proof.

Let $\mathcal{T}_{k}$ the class of tournaments with twin-width at most $k$.
For each $T\in\mathcal{T}_{k}$, we associate an ordering $\prec_{T}^{*}$ given
by Conjecture 3.13. For every $T\in\mathcal{T}_{k}$, we have (the two first
inequalities are true for every tournament and any ordering, the last one
comes from the property of $\prec_{T}^{*}$):

$tww(T^{\prec_{T}^{*}})\leq tww(T^{\prec_{T}^{*}},\prec_{T}^{*})\leq
tww(T,\prec_{T}^{*})\leq f(k)$ (1)

Hence, the class of undirected graphs
$\mathcal{C}_{k}=\\{T^{\prec_{T}^{*}}\mid T\in\mathcal{T}_{k}\\}$ has bounded
twin-width, and is thus $\chi$-bounded by a polynomial function $g$.

Let $T\in\mathcal{T}_{k}$. We have: $T^{\prec_{T}^{*}}\in\mathcal{C}_{k}$,
$tww(T^{\prec_{T}^{*}})\leq f(k)$ by (1), $\omega(T^{\prec_{T}^{*}})\leq
f(\operatorname{\overrightarrow{\omega}}(T))$ by the choice of
$\prec_{T}^{*}$. Hence,

$\chi(T^{\prec_{T}^{*}})\leq g(f(\operatorname{\overrightarrow{\omega}}(T)))$

and thus $\operatorname{\overrightarrow{\chi}}(T)\leq
g(f(\operatorname{\overrightarrow{\omega}}(T))$. ∎

Geniet and Thomassé [15] introduced a particular ordering of tournaments
called _BST-ordering_. Informally, a $BST$-ordering of a tournament $T$ is
based on a rooted binary search tree on vertex set $V(T)$ with the property
that for every vertex $x$, the left child of $x$ and its descendent are in
$N^{-}(x)$, and the right child of $x$ and its descendent are in $N^{+}(x)$,
and the order is the left-to-right order defined by this tree. See [15]
Section 4 for a formal definition. They prove that $BST$-orderings give an
approximation of the twin-width in the following sense:

######  Theorem 3.15 ([15]).

There exists a function $f$ such that, for every tournament $T$ and any
$BST$-ordering $\prec$ of $T$, we have:

$tww(T,\prec)\leq f(tww(T))$

Hence, $BST$-orderings are natural candidates for the ordering of Conjecture
3.13.

######  Conjecture 3.16.

There exists a function $f$ such that, for every tournament $T$, there exists
a $BST$-ordering $\prec$ of $T$ such:

$\omega(T^{\prec})\leq f(\operatorname{\overrightarrow{\omega}}(T))$

##  4 Classes of tournaments defined by forbidding a single tournament

In this section, we will investigate the classes defined by forbidding a
single tournament. Our main question will be to understand which tournaments
$H$ are such that $\operatorname{Forb}(H)$ is $\chi$-bounded. Such a
tournament is said to be _$\operatorname{\overrightarrow{\chi}}$ -binding_.

###  4.1 Gentlemen are the same as heroes

The most trivial case of $\chi$-bounding function is a constant function. A
tournament $H$ is a _hero_ if there exists an integer $c_{H}$ such that every
$H$-free tournament $T$ has dichromatic number at most $c_{H}$.

In a seminal paper, Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott,
Seymour and Thomassé [4] characterized heroes:

######  Theorem 4.1 (Berger, Choromanski, Chudnovsky, Fox, Loebl, Scott,
Seymour and Thomassé [4]).

A tournament $H$ is a hero if and only if:

  * •

$H=TT_{1}$, or

  * •

$H=H_{1}\Rightarrow H_{2}$, where $H_{1}$ and $H_{2}$ are heroes in
tournaments, or

  * •

$H=\Delta(1,k,H_{1})$ or $H=\Delta(1,H_{1},k)$, where $k\geq 1$ and $H_{1}$ is
a hero in tournaments.

Similarly, we say that a tournament $H$ is a _gentleman_ if there exists a
number $c_{H}$ such that every $H$-free tournament has clique number at most
$c_{H}$. Since
$\operatorname{\overrightarrow{\omega}}(T)\leq\operatorname{\overrightarrow{\chi}}(T)$
for any tournament $T$, heroes are gentlemen. We prove that the converse is
also true.

In [22], Nguyen, Scott and Seymour introduce a class of tournaments called
_crossing tournaments_ (it is the class $\mathcal{T}[\mathcal{C}]$ where
$\mathcal{C}$ is the class of circle graphs). They prove that crossing
tournaments are $S_{3}$-free and prove a result (see 12.4 in [22]) that can be
translated in our language by saying that they have arbitrarily large clique
number. It is a key ingredient in the proof of the following theorem.

######  Theorem 4.2.

Gentlemen and heroes are the same.

###### Proof.

For every tournament $T$,
$\operatorname{\overrightarrow{\omega}}(T)\leq\operatorname{\overrightarrow{\chi}}(T)$,
thus it is clear that all heroes are gentlemen.

Let us now prove that all gentlemen are heroes. Suppose there exists a
gentleman $H$ that is not a hero, and let it be chosen so as to minimize
$|V(H)|$. Since all subtournaments of a gentleman are gentlemen (because
tournaments not containing a subtournament of $H$ do not contain $H$ and thus
have bounded clique number), every subtournament of $H$ is a hero by
minimality of $V(H)$. Consider the sequence of tournaments $S_{n}$ defined at
the end of subsection 3.2. Since this sequence has unbounded clique number and
$H$ is a gentlemen, there exists an integer $k$ such that $H$ is a
subtournament of $S_{k}$. This implies that either $H=A\Rightarrow B$ or
$H=\Delta(1,A,B)$ for some tournaments $A$ and $B$. Since $A$ and $B$ are two
strict subtournaments of $H$, they are heroes by minimality of $H$. Thus
$H\neq A\Rightarrow B$ for $H$ would be a hero by Theorem 4.1. Thus
$H=\Delta(1,A,B)$.

But we know that $S_{3}$ is not a gentleman since crossing tournaments are
$S_{3}$-free and can have arbitrarily large clique number. Thus $H$ does not
contain $S_{3}=\Delta(1,\vec{C}_{3},\vec{C}_{3})$. This implies that one of
$A$ or $B$ does not contain $\vec{C}_{3}$ and thus either $A$ or $B$ is a
transitive tournament, which implies $H$ is a hero, a contradiction.

∎

###  4.2 Gyárfás-Sumner Conjecture for tournaments

We propose the following analogue of the celebrated Gyárfás-Sumner Conjecture
[16, 25] that states that a graph $F$ is $\chi$-binding if and only if $F$ is
a forest (where, as in the directed case, a graph $F$ is $\chi$-binding if the
class of graphs not containing $F$ as an induced subgraph is $\chi$-bounded).

######  Conjecture 4.3.

A tournament $H$ is $\operatorname{\overrightarrow{\chi}}$-binding if and only
if $H$ has a backedge graph which is a forest.

Despite the link between $\operatorname{\overrightarrow{\chi}}$-bounded
classes of tournaments and $\chi$-bounded classes of graphs given by Theorem
3.6, we were not able to prove that Gyárfás-Sumner Conjecture applies or is
applied by Conjecture 4.3. We now believe that the two conjectures are
independent, but we would be very happy if a bridge between them was shown.

To support the conjecture, we prove that :

  * •

the "only if" part is true (Theorem 4.4),

  * •

it is enough to prove it for trees instead of forests (Proposition 4.5),

  * •

if it holds for a tournament $T$ then it holds for the tournaments obtained by
reversing every arc of $T$ (Proposition 4.7),

  * •

if it holds for two tournaments $H_{1}$ and $H_{2}$ then it holds for the
tournament $H_{1}\Rightarrow H_{2}$ (Theorem 4.9),

A _star_ is a tree that has at most one non-leaf vertex. We also prove that
heroes admit a backedge graph that is a disjoint union of stars. See
Proposition 4.6.

At the end of the section we also discuss the case of tournaments $T$ that
admits a backedge graph that is a matching.

######  Theorem 4.4.

Let $H$ be a tournament. If $H$ is
$\operatorname{\overrightarrow{\chi}}$-binding, then $H$ admits an ordering
whose backedge graph is a forest.

###### Proof.

Let $H$ be a tournament that does not admit an ordering whose backedge graph
is a forest. Let $\mathcal{C}$ be the class of undirected graphs with girth at
least $|V(H)|+1$, and let $\mathcal{T}[\mathcal{C}]$ be the class of
tournaments that admit a graph of $\mathcal{C}$ as a backedge graph.

Let $T\in\mathcal{T}[\mathcal{C}]$ and let $X\subseteq V(T)$ such that
$|X|=|V(H)|$. $T$ admits an ordering such that the backedge graph has girth at
least $|V(H)|+1$, so $T[X]$ admits an ordering for which the backedge graph is
a forest. So $T[X]\neq H$. This proves that tournaments in
$\mathcal{T}[\mathcal{C}]$ are $H$-free.

Since for every $T\in\mathcal{T}[\mathcal{C}]$, a backedge graph of $T$ has
girth $|V(H)|+1\geq 4$, we have $\operatorname{\overrightarrow{\omega}}(T)\leq
2$.

By a celebrated result of Erdős [14], for every integer $k$, there exists
$G\in\mathcal{C}$ such that $\chi(G)\geq k$. Let
$T\in\mathcal{T}[\mathcal{C}]$ such that $T$ admits an ordering $\prec$ such
that $T^{\prec}=G$. By Theorem 3.3,
$\operatorname{\overrightarrow{\chi}}(T)\geq\chi(T^{\prec})/\omega(T^{\prec})=k/2$.

This proves that there are $H$-free tournaments with clique number $2$ and
arbitrarily large dichromatic number, i.e. $H$ is not
$\operatorname{\overrightarrow{\chi}}$-binding. ∎

Let $T$ be a tournament admitting a forest as a backedge graph. We claim that
$T$ also admits a tree as a backedge graph. Indeed, let $\prec$ be an ordering
of $V(T)$ such that $T^{\prec}$ is a forest and among such ordering, assume it
minimizes the number of connected components of $T^{\prec}$. We claim that
$T^{\prec}$ is a tree. Assume for contradiction that it is not. Let $v$ be the
smallest vertex not in the same connected component of $T^{\prec}$ as the
first vertex, and let $u$ be the vertex preceding $v$ in $\prec$. Then the
backedge graph resulting from switching $u$ and $v$ in the ordering is
obtained from $T^{\prec}$ by adding the edges $uv$ and thus has one less
connected component than $T^{\prec}$, a contradiction. We thus have the
following:

######  Proposition 4.5.

It is enough to prove Conjecture 4.3 for tournaments that admit a tree as a
backedge graph.

As mentioned before, heroes are by definition
$\operatorname{\overrightarrow{\chi}}$-binding tournaments, and by Theorem 4.4
they admit a backedge graph that is a forest. The following proposition proves
that for heroes, this backedge graphs is a star forest.

######  Proposition 4.6.

If $H$ is a hero, then $H$ admits a backedge graph that is a disjoint union of
stars.

###### Proof.

We prove this using the inductive construction of heroes given by Theorem 4.1.
It is true for $TT_{1}$ so we need to maintain this property if
$H=H_{1}\Rightarrow H_{2}$ and if $H=\Delta(1,k,H_{1})$.

If $H=H_{1}\Rightarrow H_{2}$, consider orderings $\prec_{i}$ of $H_{i}$ given
by the induction, and simply construct the order on $V(H)$ in which all
vertices of $H_{1}$ are placed before those of $H_{2}$ (respecting $\prec_{1}$
and $\prec_{2}$). This adds no new back arc, so the back edge graph is the
union of those of $H_{1}$ and $H_{2}$, so we have our result.

If $H=\Delta(1,k,H_{1})$, then consider the ordering $\prec$ of $H_{i}$ given
by the induction, and construct the order on $V(H)$ obtained by placing the
vertices of $TT_{k}$ first so that all arcs go forward, then the vertices of
$H_{1}$ in the order $\prec$, and finally the vertex $x$ corresponding to the
"1" in $\Delta(1,k,H_{1})$. The only new back arcs are the one from $x$ to the
vertices of the $TT_{k}$, which produce a star, so we again get our desired
result. ∎

Given a tournament $T$, the reverse $T_{r}$ of $T$ is the tournament obtained
from $T$ by reversing the direction of every arc.

######  Proposition 4.7.

If $H$ is $\operatorname{\overrightarrow{\chi}}$-binding, then the reverse
$H_{r}$ of $H$ is also $\operatorname{\overrightarrow{\chi}}$-binding.

###### Proof.

Observe that, for every tournament $H$ and every ordering $\prec$ of $H$,
$H^{\prec}=H_{r}^{\prec_{r}}$. So
$\operatorname{Forb}(H)^{\prec}=\operatorname{Forb}(H_{r})^{\prec}$ and the
result holds by Theorem 3.6. ∎

In order to prove our next theorem, we will use the following very nice result
of Le, Harutyunyan, Thomassé and Wu that states that if the outneighbourhood
of each vertex of a tournament has bounded dichromatic number, so does the
whole tournament. We will discuss more of these kinds of “local to global”
properties in Section 5.

######  Theorem 4.8 (Le, Harutyunyan, Thomassé and Wu [18]).

There exists a function $\lambda_{1}$ such that, for every integer $t$, if $T$
is a tournament such that for every $v\in V(T)$,
$\operatorname{\overrightarrow{\chi}}(T[N^{+}(v)])\leq t$, then
$\operatorname{\overrightarrow{\chi}}(T)\leq\lambda_{1}(t)$.

Following [20], we define the _neighbourhood $N(uv)$ of an arc $uv$_ to be
$N^{-}(u)\cap N^{+}(v)$, that is the set of vertices forming a directed
triangle with $uv$.

######  Theorem 4.9.

If $H_{1}$ and $H_{2}$ are two $\operatorname{\overrightarrow{\chi}}$-binding
tournaments, then $H_{1}\Rightarrow H_{2}$ is also
$\operatorname{\overrightarrow{\chi}}$-binding.

###### Proof.

For $i=1,2$, let $f_{i}$ be a $\operatorname{\overrightarrow{\chi}}$-binding
function for the class of $H_{i}$-free tournaments. Set $f=\max(f_{1},f_{2})$
and $h=\max(|H_{1}|,|H_{2}|)$. We are going to prove that the class of
$(H_{1}\Rightarrow H_{2})$-free tournaments is
$\operatorname{\overrightarrow{\chi}}$-bounded by a function $g$ that will be
fixed at the end of the proof.

The result is trivial for tournaments with clique number $1$. We proceed by
induction on $\operatorname{\overrightarrow{\omega}}$. Let $k\geq 1$. Assume
the result holds for tournaments with clique number at most $k$ and let $T$ be
a $(H_{1}\Rightarrow H_{2})$-free tournament with clique number $k+1$.

Let $\prec$ be an $\operatorname{\overrightarrow{\omega}}$-ordering of $T$. We
call an arc $uv$ heavy if $\operatorname{\overrightarrow{\chi}}(T[N(uv)])\geq
2g(k)+1$, and light otherwise.

######  Claim 4.9.1.

If $uv$ is a heavy arc, then $v\prec u$

Proof of Claim : Assume for contradiction that $u\prec v$. Let $(L,M,R)$ be
the partition of $N(uv)$ such that $L\prec u\prec M\prec v\prec R$. Since
$L\cup M\prec v$ and $v\Rightarrow L\cup M$,
$\operatorname{\overrightarrow{\omega}}(T[L\cup M])\leq k$. Since $u\prec R$
and $R\Rightarrow u$, $\operatorname{\overrightarrow{\omega}}(T[R])\leq k$.
Hence, by induction, $\operatorname{\overrightarrow{\chi}}(T[N(uv)])\leq
2g(k)$, a contradiction with the fact that $uv$ is heavy. $\square$

######  Claim 4.9.2.

Every vertex $u$ satisfies
$\min(\operatorname{\overrightarrow{\chi}}(T[N^{-}(u)]),\operatorname{\overrightarrow{\chi}}(T[N^{+}(u)])\leq
f(k+1)+g(k)+2hg(k)$.

Proof of Claim : Let $u\in V(T)$. Set $X_{h}^{+}=\\{v\mid uv\text{ is
heavy}\\}$, $X_{h}^{-}=\\{v\mid vu\text{ is heavy}\\}$, $X_{\ell}^{+}=\\{v\mid
uv\text{ is light}\\}$ and $X_{\ell}^{-}=\\{v\mid vu\text{ is light}\\}$. Note
that $N^{+}(u)=X_{h}^{+}\cup X_{\ell}^{+}$ and $N^{-}(u)=X_{h}^{-}\cup
X_{\ell}^{-}$

By claim 4.9.1, $X_{h}^{+}\prec u\prec X_{h}^{-}$, and since
$X_{h}^{-}\Rightarrow u\Rightarrow X_{h}^{+}$, we have
$\operatorname{\overrightarrow{\omega}}(T[X_{h}^{+}\cup X_{h}^{-}])\leq k$ and
thus, by induction, $\operatorname{\overrightarrow{\chi}}(T[X_{h}^{+}])\leq
g(k)$ and $\operatorname{\overrightarrow{\chi}}(T[X_{h}^{-}])\leq g(k)$.

Now, if
$\min(\operatorname{\overrightarrow{\chi}}(T[X_{\ell}^{+}]),\operatorname{\overrightarrow{\chi}}(T[X_{\ell}^{-}]))\leq
f(k+1)+2hg(k)$, we are done.

Assume first that
$\operatorname{\overrightarrow{\chi}}(T[X_{\ell}^{+}])>f(k+1)+2hg(k)$. Then
there exists $V_{2}\subseteq X_{\ell}^{+}$ such that $T[V_{2}]=H_{2}$. Let
$X\subseteq X_{\ell}^{-}$ such that $X\Rightarrow V_{2}$. Then $X$ is
$H_{1}$-free and thus $\operatorname{\overrightarrow{\chi}}(T[X])\leq f(k+1)$.
For each $w\in X_{\ell}^{-}\setminus X$, there exists $v\in V_{2}$ such that
$w\in N(uv)$. Since for each $v\in V_{2}$, $uv$ is light, i.e.
$\operatorname{\overrightarrow{\chi}}(T[N(uv)])\leq 2g(k)$, we have
$\operatorname{\overrightarrow{\chi}}(T[X_{\ell}^{-}\setminus X])\leq 2hg(k)$.
Hence $\operatorname{\overrightarrow{\chi}}(T[N^{-}(u)])\leq
g(k)+f(k+1)+2hg(k)$.

If $\operatorname{\overrightarrow{\chi}}(T[X_{\ell}^{-}])>f(k+1)+2hg(k)$, we
similarly get that $\operatorname{\overrightarrow{\chi}}(T[N^{+}(u)])\leq
g(k)+f(k+1)+2hg(k)$. $\square$

By claim 4.9.2, we can partition $V(T)$ into two sets $V_{1}$ and $V_{2}$ such
that for every $v\in V_{1}$,
$\operatorname{\overrightarrow{\chi}}(T[N^{+}(v)])\leq f(k+1)+g(k)+2hg(k)$ and
for every $v\in V_{2}$, $\operatorname{\overrightarrow{\chi}}(T[N^{-}(v)])\leq
f(k+1)+g(k)+2hg(k)$. Hence, by Theorem 4.8,
$\operatorname{\overrightarrow{\chi}}(V_{i})\leq\gamma(f(k+1)+g(k)+2hg(k))$.
Hence, the function $g=2\gamma(f(k+1)+g(k)+2hg(k))$ is a
$\operatorname{\overrightarrow{\chi}}$-binding function for the class of
$H_{1}\Rightarrow H_{2}$-free tournaments. ∎

For the last part of this section we need to consider _ordered graphs_ , that
is pairs $(G,\prec)$, where $G$ is an undirected graph, and
$\prec\in\mathfrak{S}(G)$ is an order on its vertices. We say that an ordered
graph $(H,\prec_{H})$ is an induced ordered subgraph of an ordered graph
$(G,\prec_{G})$ if there exists an injective mapping $\phi:V(H)\to V(G)$ such
that for all vertices $x,y$ of $V(H)$, $x\prec_{H}y$ if and only if
$\phi(x)\prec_{G}\phi(y)$ and $xy\in E(H)$ if an only if $\phi(x)\phi(y)\in
E(G)$.

Given that definition, and for a given class $\mathcal{O}$ of ordered graphs,
one can define $\operatorname{Forb}(\mathcal{O})$ as the set of ordered graphs
that do not contain any member of $\mathcal{O}$ as an induced ordered
subgraph. We say that a class of ordered graphs $\mathcal{O}$ is
$\chi$-bounded if the set of graphs $G$ such that there exists $\prec$ with
$(G,\prec)\in\mathcal{O}$ is $\chi$-bounded (we simply ignore the orderings
here).

Let $\mathcal{T}$ be a class of tournaments. Recall that $\mathcal{T}^{\prec}$
is the set of graphs that are backedge graphs of a tournament in
$\mathcal{T}$. We now define the ordered version of it as follows:

$\mathcal{T}_{o}^{\prec}=\\{(T^{\prec},\prec):T\in\mathcal{T},\prec\in\mathfrak{S}(T)\\}$

Note that, given a tournament $T$, $\\{T\\}^{\prec}$ is the set of backedge
graphs of $T$ and $\\{T\\}^{\prec}_{o}$ the set of ordered backedge graphs of
$T$. The following is an ordered analogue of Theorem 3.6.

######  Property 4.10.

Let $T$ be a tournament. The class of tournaments $Forb(T)$ is
$\operatorname{\overrightarrow{\chi}}$-bounded if and only if the class of
ordered undirected graphs $Forb(\\{T\\}^{\prec}_{o})$ is $\chi$-bounded.

###### Proof.

Assume first that $Forb(T)$ is $\operatorname{\overrightarrow{\chi}}$-bounding
by a function $f$. Let $(G,\prec_{G})\in Forb(\\{T\\}^{\prec}_{o})$. Let $T$
be the tournament on the same vertex set as $G$, such that
$(T^{\prec_{G}},\prec_{G})=(G,\prec_{G})$ (i.e. $T$ is obtained from
$(G,\prec_{G})$ by oriented edges of $G$ from right to left, and all other
edges from left to right). Since $(G,\prec_{G})\in Forb(\\{T\\}^{\prec}_{o})$,
$T\in Forb(T)$ and thus $\operatorname{\overrightarrow{\chi}}(T)\leq
f(\operatorname{\overrightarrow{\omega}}(T))\leq f(\omega(G))$ (because
$\operatorname{\overrightarrow{\omega}}(T)\leq\omega(G)$). We have the first
inequality by Theorem 3.3

$\chi(G)=\chi(T^{\prec})\leq\operatorname{\overrightarrow{\chi}}(T)\omega(T^{\prec})\leq
f(\omega(G))\omega(G)$

which proves that $Forb(\\{T\\}^{\prec}_{o})$ is $\chi$-bounded.

Assume now that $Forb(\\{T\\}^{\prec}_{o})$ is $\chi$-bounded by a function
$f$. Let $T\in Forb(T)$ and let $\prec$ be an
$\operatorname{\overrightarrow{\omega}}$-ordering of $T$. Then $T^{\prec}\in
Forb(\\{T\\}^{\prec}_{o})$. Hence:
$\operatorname{\overrightarrow{\chi}}(T)\leq\chi(T^{\prec})\leq
f(\omega(T^{\prec}))=f(\operatorname{\overrightarrow{\omega}}(T))$ ∎

Briański, Davies and Walczak [9] studied for which ordered graphs
$(G,\prec_{G})$, $Forb((G,\prec_{G}))$ is $\chi$-bounded, and claimed in a
personal communications to have proven that excluding any ordered matching
yields a $\chi$-bounded class.

######  Conjecture 4.11.

Let $(M,\prec)$ be an ordered graph with maximum degree $1$. Then the class of
$(M,\prec)$-free ordered graphs is $\chi$-bounded.

By Property 4.10, we have:

######  Lemma 4.12.

If Conjecture 4.11 holds, then any tournament that admits a backedge graph of
maximum degree $1$ is $\operatorname{\overrightarrow{\chi}}$-binding.

For the usual undirected version of Gyárfás-Sumner conjecture, one of the
first non trivial cases that was proven (by Gyárfás, see [17]) concerns the
class of graphs that do not contain a path of fixed length as an induced
subgraph. An analogue for tournaments could be the tournament $TP_{n}$ on $n$
vertices obtained from the transitive tournament $TT_{n}$ by reversing the
direction of each arc of the unique Hamiltonian path $v_{1}v_{2}\ldots v_{n}$.
Now consider $\prec$ to be the ordering $v_{2}\prec v_{1}\prec v_{4}\prec
v_{3}\prec\ldots\prec v_{2p}\prec v_{2p-1}\prec\ldots\prec v_{n}\prec v_{n-1}$
(assuming for simplicity that $n$ is even, otherwise we end with $v_{n}$). It
is easy to observe that the backedge graph of $TP_{n}$ with respect to $\prec$
has maximum degree $1$. Hence, by 4.10, we have:

######  Lemma 4.13.

If Conjecture 4.11 holds, then for every $k\geq 1$, $TP_{k}$ is
$\operatorname{\overrightarrow{\chi}}$-binding.

###  4.3 Relation with the Erdős-Hajnal property and the $BIG\Rightarrow BIG$
conjecture

A tournament $H$ has the _Erdős-Hajnal property_ if there exists an integer
$c$ such that for every $H$-free tournaments $T$, $T$ contains a transitive
tournament on $|T|^{c}$ vertices. It was proven in [2] that the famous Erdős-
Hajnal conjecture on undirected graphs is equivalent to the conjecture saying
that every tournament has the Erdős-Hajnal property.

######  Theorem 4.14.

If $H$ is a polynomially $\operatorname{\overrightarrow{\chi}}$-binding
tournament, then $H$ has the Erdős-Hajnal property.

###### Proof.

Let $H$ be a tournament and $c$ an integer such that for every $H$-free
tournaments $T$,
$\operatorname{\overrightarrow{\chi}}(T)\leq\operatorname{\overrightarrow{\omega}}(T)^{c}$.
Let us prove that $H$ has the Erdős-Hajnal property (for the constant
$\frac{1}{1+c}$).

Let $T$ be an $H$-free tournament. If
$\operatorname{\overrightarrow{\omega}}(T)\geq n^{\frac{1}{1+c}}$, then $T$
contains a transitive tournament of size $n^{\frac{1}{1+c}}$ and we are done.
So assume that $\operatorname{\overrightarrow{\omega}}(T)\leq
n^{\frac{1}{1+c}}$. Then $\operatorname{\overrightarrow{\chi}}(T)\leq
n^{\frac{c}{1+c}}$ and thus $T$ contains a transitive tournament on
$\frac{n}{n^{\frac{c}{1+c}}}=n^{\frac{1}{1+c}}$ vertices. ∎

A tournament $H$ has the _strong Erdős-Hajnal property_ if there exists a
number $c$ such that all $H$-free tournaments contain two disjoint set of
vertices $A$ and $B$ such that $A\Rightarrow B$ and $|A|,|B|\geq c|H|$. It can
be shown that if $H$ has the strong Erdős-Hajnal then it has the Erdős-Hajnal
property, and that not every tournament has the strong Erdős-Hajnal property
(the Paley tournament on $7$ vertices being an example). Heroes have the
strong Erdős-Hajnal property since bounded dichromatic number implies a
transitive tournament of linear size, and thus a directed cut of linear size.
In [12], the authors prove that every tournament that has the strong Erdős-
Hajnal property admits a backedge graph that is a forest and conjecture that
the converse is true :

######  Conjecture 4.15 ([12]).

A tournament $H$ has the strong Erdős-Hajnal property if and only if it has a
backedge graph that is a forest.

Note that in view of our conjecture 4.3, it could be that being chi-bounding
is the same has having the strong Erdős-Hajnal property. We are not able to
prove any inclusion yet.

We say that a class of tournaments $\mathcal{T}$ has the _$BIG\Rightarrow BIG$
property_ if there exists a function $f$ such that, for every
$T\in\mathcal{T}$, if $\operatorname{\overrightarrow{\chi}}(T)\geq f(t)$, then
$T$ contains two disjoint subtournaments $A$ and $B$ such that
$\operatorname{\overrightarrow{\chi}}(A),\operatorname{\overrightarrow{\chi}}(B)\geq
t$ and $A\Rightarrow B$. In [22], the following beautiful conjecture is
proposed:

######  Conjecture 4.16 ($BIG\Rightarrow BIG$ Conjecture [22]).

The class of all tournaments has the $BIG\Rightarrow BIG$ property.

Nguyen, Scott and Seymour proved in [21] that the $BIG\Rightarrow BIG$
Conjecture implies the Erdős-El-Zahar conjecture, which states that there
exists a function $f$ such that, for every integer $c$, every graph $G$ with
$\chi(G)\geq f(\omega(G),c)$ contains two disjoint subgraphs $A$ and $B$ such
that $\chi(A),\chi(B)\geq c$ and there is no edge between $A$ and $B$.
Klingelhöfer and Newman [20] showed recently the other direction, that is the
Erdős-El-Zahar conjecture implies the $BIG\Rightarrow BIG$ Conjecture. To
prove it, they first prove the following beautiful theorem. Given an oriented
graph $G$, we denote by $\alpha(G)$ the size of a maximum independent set of
$G$.

######  Theorem 4.17 ([20]).

There exists a function $\lambda$ such that, for every integer $t$, if $G$ is
an oriented graph such that for every $a\in A(T)$,
$\operatorname{\overrightarrow{\chi}}(G[N^{+}(a)])\leq t$, then
$\operatorname{\overrightarrow{\chi}}(G)\leq\lambda(t,\alpha(G))$.

Applying the exact same method as Klingelhöfer and Newman used to prove that
the Erdős-El-Zahar conjecture implies the $BIG\Rightarrow BIG$ Conjecture, we
can prove the following.

######  Theorem 4.18.

If $H$ is a $\operatorname{\overrightarrow{\chi}}$-binding tournament, then
the class of $H$-free tournaments has the $BIG\Rightarrow BIG$ property

###### Proof.

Let $\ell$ be a function defined inductively as follows: $\ell(1)=1$ and for
every $t\geq 1$, $\ell(t+1)=(t+1)+\binom{t+1}{2}\ell(t)$. Given a tournament
$T$, we say that a subtournament $X$ of $T$ is a $t$-cluster if
$\operatorname{\overrightarrow{\chi}}(X)\geq t$ and $|X|\leq\ell(t)$

Let $H$ be a $\operatorname{\overrightarrow{\chi}}$-binding tournament and $c$
be an integer. Let $T$ be an $H$-free tournament such that $T$ does not
contain two disjoint subtournaments $A$ and $B$ such that $A\Rightarrow B$ and
$\operatorname{\overrightarrow{\chi}}(A),\operatorname{\overrightarrow{\chi}}(B)\geq
c$. We want to prove that the dichromatic number of $T$ is bounded by a
function of $c$.

We first prove a weaker statement : we prove by induction on $t$ that if $T$
contains no $t$-cluster for some $t$ and no two disjoint subtournaments $A$
and $B$ such that $A\Rightarrow B$ and
$\operatorname{\overrightarrow{\chi}}(A),\operatorname{\overrightarrow{\chi}}(B)\geq
c$, then $\operatorname{\overrightarrow{\chi}}(T)$ is bounded (by a function
of $c$ and $t$). Since a $1$-cluster is a vertex, the result trivially holds
for $t=1$. Now assume it holds for $t<2c$, and let us prove it for $t+1$. So
assume $T$ has no $(t+1)$-cluster, and say that an arc $a$ is _heavy_ if
$N(a)$ contains a $t$-cluster, and it is _light_ otherwise (we recall that if
$xy$ is an arc, $N(xy)$ denotes the set of vertices $z$ such that $yz\in A$
and $zx\in A$). Let $T_{h}$ be the oriented graph induced by the heavy arcs,
and $T_{\ell}$ the oriented graphs induced by the light arcs.

We first claim that the underlying graph of $T_{h}$ has maximum clique at most
$t$. Assume by contradiction there exists $K$ of size $t+1$ inducing a
tournament in $T_{h}$. For every arc $a$ with both endvertices in $K$, $a$ is
heavy so there exists $C_{a}$ a $t$-cluster included in $N(a)$. Let $X$ be the
subtournament of $T$ induced by the union of $K$ and all such sets $C_{a}$.
The number of its vertices is at most $(t+1)+\binom{t+1}{2}l(t)=l(t+1)$. If
$X$ admits a dicolouring with at most $t$ colours then there must be two
vertices $x,y$ in $K$ that get the same colour (because $K$ has size $t+1$),
but then this colour cannot appear in $C_{xy}$ (for it would create a
monochromatic $C_{3}$), which contradicts the fact that $C_{xy}$ has
dichromatic number at least $t$. Hence
$\operatorname{\overrightarrow{\chi}}(X)\geq t+1$ and so $X$ is a
$(t+1)$-cluster which contradicts our hypothesis. Hence we are proven our
claim, which can be stated as $\alpha(T_{\ell})\leq t$.

By induction, since for every light arc $a$, $N(a)$ contains no $t$-cluster,
we have that $\operatorname{\overrightarrow{\chi}}(N^{+}(a))$ is bounded for
every light arc $a$. Now, by Theorem 4.17,
$\operatorname{\overrightarrow{\chi}}(T_{\ell})$ is also bounded, say by $k$.
Let $(S_{1},\dots,S_{k})$ be a dicolouring of $T_{\ell}$, i.e.
$T_{\ell}[S_{i}]$ is acylic for $i=1,\dots,k$. Then, for $i=1,\dots,k$, there
is an ordering $\prec_{i}$ of $S_{i}$ such that all backward arcs of
$(T[S_{i}],\prec_{i})$ are heavy. Hence
$\operatorname{\overrightarrow{\omega}}(T[S_{i}])\leq t$, and since $T[S_{i}]$
is $H$-free and $H$ is $\operatorname{\overrightarrow{\chi}}$-binding,
$\operatorname{\overrightarrow{\chi}}(T[S_{i}])$ is bounded, which implies
that $\operatorname{\overrightarrow{\chi}}(T)$ is also bounded.

We can now conclude. Either $T$ contains no $2c$-cluster and we win by what
precedes, or $T$ contains a $2c$-cluster $X$. Partition $V(T)\setminus V(X)$
with respect to their adjacency to $X$. This gives a partition of
$V(T)\setminus X$ into at most $2^{|X|}\leq 2^{\ell(2c)}$ parts. Assume by
contradiction that one of these parts, let it be $A$, has dichromatic number
at least $c$. Call $B^{+}$ (resp. $B^{-}$) the subset of $X$ such that
$A\Rightarrow B^{+}$ (resp $B^{-}\Rightarrow A$). Since
$\operatorname{\overrightarrow{\chi}}(X)\geq 2c$, one of $B^{+}$ or $B^{-}$
has dichromatic number of at least $c$, and we get a contradiction with the
assumption on $T$. So every such part $A$ has dichromatic number at most $c$
and hence $\operatorname{\overrightarrow{\chi}}(T)$ is bounded by
$\ell(2c)+2^{\ell(2c)}c$.

∎

##  5 Local to Global - Links with domination number

Informally, given a digraph parameter $\gamma$, a $\gamma$-cluster of a
tournament $T$ is a subtournament $X$ of $T$ of bounded size with large
$\gamma$. In this section, we investigate for which parameters $\gamma_{1}$
and $\gamma_{2}$ we have that, for all tournaments $T$ with sufficiently large
$\gamma_{1}$, $T$ has a $\gamma_{2}$-cluster.

We say that _large $\gamma_{1}$ implies a $\gamma_{2}$-cluster_ if there
exists two functions $f$ and $\ell$ such that for every integer $k$, if
$\gamma_{1}(T)\geq k$, then $T$ contains a subtournament $X$ such that
$\gamma_{1}(X)\geq k$ and $|X|\leq\ell(k)$. We review what is known on this
topic and propose some new conjectures.

Such property was first studied by Thomassé, Le, Harutyunyan and Wu in [18]:

######  Theorem 5.1 (Large $dom$ implies a
$\operatorname{\overrightarrow{\chi}}$-cluster, [18]).

There exists two functions $f$ and $\ell$ such that, for every integer $k$,
every tournament $T$ with $\operatorname{dom}(T)\geq f(k)$ contains a
subtournament $X$ with $|X|\leq\ell(k)$ and
$\operatorname{\overrightarrow{\chi}}(X)\geq k$.

In the same paper, Thomassé, Le, Harutyunyan and Wu conjectured the following:

######  Conjecture 5.2 (Large $dom$ implies a $dom$-cluster, [18]).

There exist two functions $f$ and $\ell$ such that, for every integer $k$,
every tournament $T$ with $\operatorname{dom}(T)\geq f(k)$ contains a
subtournament $X$ with $|X|\leq\ell(k)$ and $\operatorname{dom}(X)\geq k$.

Since
$\operatorname{dom}(T)\leq\operatorname{\overrightarrow{\omega}}(T)\leq\operatorname{\overrightarrow{\chi}}(T)$,
the following is stronger than Theorem 5.1 but weaker than Conjecture 5.2.

######  Conjecture 5.3 (Large $dom$ implies an
$\operatorname{\overrightarrow{\omega}}$-cluster).

There exist two functions $f$ and $\ell$ such that, for every integer $k$,
every tournament $T$ with $\operatorname{dom}(T)\geq f(k)$ contains a
subtournament $X$ with $|X|\leq\ell(k)$ and
$\operatorname{\overrightarrow{\omega}}(X)\geq k$.

A tournament $R$ is a _rebel_ if tournaments not containing $R$ have bounded
domination number. A tournament is a poset tournament if it admits a backedge
graph that is a comparability graph. Chudnovsky, Kim, Liu, Seymour and
Thomassé proved in [10] that every rebel is a poset tournament, but the
converse remains open.

######  Conjecture 5.4 (Chudnovsky, Kim, Liu, Seymour and Thomassé).

Every poset tournament is a rebel.

In particular, the $S_{k}$ defined in Section 3.2 are posets tournaments, and
have arbitrarily large clique number (see Corollary LABEL:coro:S_k). Hence, if
one can prove that, for every integer $k$, $S_{k}$ is a rebel, then Conjecture
5.3 holds. More generally:

######  Theorem 5.5.

Conjecture 5.4 implies Conjecture 5.3.

Thomassé, Le, Harutyunyan and Wu applied Theorem 5.1 to prove Theorem 4.8,
which can be seen as a local to global theorem about dichromatic number. The
analogue of Theorem 4.8 for clique number is the following conjecture.

######  Conjecture 5.6.

There exists a function $g$ such that, for every integer $t$, if $T$ is a
tournament such that for every $v\in V(T)$,
$\operatorname{\overrightarrow{\omega}}(N^{+}(v))\leq t$, then
$\operatorname{\overrightarrow{\omega}}(T)\leq g(t)$.

The analogue of Theorem 5.1 for clique number is Conjecture 5.3 and indeed we
have the following implication.

######  Theorem 5.7.

Conjecture 5.3 implies Conjecture 5.6

###### Proof.

Let $T$ be a tournament and $t\in\mathbb{N}$ such that for every vertex $v\in
V(T)$, $\operatorname{\overrightarrow{\omega}}(N^{+}(v))\leq t$. Let $f$ and
$\ell$ be the functions given by Conjecture 5.3. We will prove that
$\operatorname{\overrightarrow{\omega}}(T)\leq\max(tf(t+1),t\ell(t+1))$.

If $\operatorname{dom}(T)<f(t+1)$, then, since
$\operatorname{\overrightarrow{\omega}}(N^{+}(v))\leq t$ for every $v\in
V(T)$, we have $\operatorname{\overrightarrow{\omega}}(T)<tf(t+1)$. So we may
assume that $\operatorname{dom}(T)\geq f(t+1)$ and thus $T$ has a
subtournament $X$ such that $|X|\leq\ell(t+1)$ and
$\operatorname{\overrightarrow{\omega}}(A)\geq t+1$. Hence, since for every
$v\in V(T)$, $\operatorname{\overrightarrow{\omega}}(N^{+}(v))\leq t$, we have
$A\subsetneq N^{+}(v)$. So $A$ is a dominating set of $T$, and thus
$\operatorname{\overrightarrow{\omega}}(T)\leq t|A|\leq t\ell(t+1)$ ∎

Since $\operatorname{dom}(T)\leq\operatorname{\overrightarrow{\omega}}(T)$ for
every tournament $T$, the following conjecture implies Conjecture 5.3 and
would give a natural property of the clique number of tournaments.

######  Conjecture 5.8 (Large $\operatorname{\overrightarrow{\omega}}$ implies
a $\operatorname{\overrightarrow{\omega}}$-cluster).

There exists two functions $f$ and $\ell$ such that, for every integer $k$,
every tournament $T$ with $\operatorname{\overrightarrow{\omega}}(T)\geq f(k)$
contains a subtournament $X$ with $|X|\leq\ell(k)$ and
$\operatorname{\overrightarrow{\omega}}(X)\geq k$.

We believe (or maybe only hope) that the above conjecture is true, and
actually we were not even able to disprove the following stronger form of it,
where $f$ is taken to be the identity:

######  Question 5.9.

Is there a function $\ell$ such that, for every tournament $T$, if
$\operatorname{\overrightarrow{\omega}}(T)\geq k$, then $T$ has a
subtournament $A$ such that $|A|\leq\ell(k)$ and
$\operatorname{\overrightarrow{\omega}}(A)\geq k$.

Let us say that a tournament $T$ is
$k$-$\operatorname{\overrightarrow{\omega}}$-critical if
$\operatorname{\overrightarrow{\omega}}(T)=k$ and for every $v\in V(T)$,
$\operatorname{\overrightarrow{\omega}}(T-v)=k-1$. Observe that the only
$1$-$\operatorname{\overrightarrow{\omega}}$-critical tournament if the one
vertex tournament, and the only
$2$-$\operatorname{\overrightarrow{\omega}}$-critical tournament is
$\vec{C}_{3}$.

######  Conjecture 5.10.

For every integer $k\geq 3$, there is an infinite number of
$k$-$\operatorname{\overrightarrow{\omega}}$-critical tournaments.

Observe that if Conjecture 5.10 is true (resp. false), then it answers to the
negative (resp. to the positive) to Question 5.9.

It is also open if large $\operatorname{\overrightarrow{\omega}}$ implies a
$\operatorname{\overrightarrow{\chi}}$-cluster (resp. a $dom$-cluster).

On the negative side, Thomassé, Le, Harutyunyan and Wu proved the following:

######  Theorem 5.11 (Large $\operatorname{\overrightarrow{\chi}}$ does not
imply a $\operatorname{\overrightarrow{\chi}}$-cluster).

For every integer $K,\ell$, there exists a tournament $T$ such that
$\operatorname{\overrightarrow{\chi}}(T)\geq K$, and all subtournaments $X$ of
$T$ on at most $\ell$ vertices are $2$-dicolourable.

##  6 Conclusion and future direction

We did not give much thought yet to the clique number of digraphs. On this
matter, it is to be noted that Theorem 3.3 does not hold for digraphs, which
implies that many of the results that we proved for tournaments cannot be
proved as easily for digraphs. Actually, even if our definition of clique
number makes at first glance as much sense applied to tournaments or digraphs,
we strongly believe that the notion will be very fruitful on tournaments,
while on digraphs it is less clear for the moment. On the positive side, we
think that Theorem 3.9 can be generalised to classes of digraphs.

######  Conjecture 6.1.

If a class of digraphs $\mathcal{C}$ is
$\operatorname{\overrightarrow{\chi}}$-bounded, then so is its closure under
substitution.

Note that, while Theorem 3.3 does not hold for digraphs, a similar weaker
bound exists for digraphs of bounded independence number. We denote by
$\alpha(D)$ the size of a maximum independent set in $D$ and by $R(i,j)$ the
smallest integer such that every graph on $R(i,j)$ vertices contains either a
clique of size $j$, or an independent set of size $j$. $R(i,j)$ exists for all
integers $i,j$ by Ramsey Theorem.

######  Theorem 6.2 ([22]).

For any digraph $D$ and ordering $\prec$ of $V(D)$, we have:

$\frac{\chi(D^{\prec})}{R(\omega(D^{\prec})+1,\alpha(D)+1)}\leq\operatorname{\overrightarrow{\chi}}(D)\leq\chi(D^{\prec})$

###### Proof.

Let $D$ be a digraph and $\prec$ an ordering of $V(D)$. Set
$\omega=\omega(D^{\prec})$ and $\alpha=\alpha(D)$. Let $X\subseteq V(D)$ such
that $D[X]$ is acyclic. To prove that $\chi(D^{\prec})\leq
R(\omega+1,\alpha+1)\operatorname{\overrightarrow{\chi}}(D)$, it suffices to
prove that $\chi(D^{\prec}[X])\leq R(\omega+1,\alpha+1)$.

Let $\varphi:X\to\mathbb{N}$ be such that $\varphi(x)$ is the number of
vertices of a longest $\prec$-decreasing path in $D^{\prec}[X]$ finishing in
$x$. We claim that $\varphi$ is a $R(\omega+1,\alpha+1)$-colouring of
$D^{\prec}$. Let $u,v\in X$ with $u\prec v$ and $uv\in E(D^{\prec})$. Then
$\varphi(u)\geq\varphi(v)+1$, so $\varphi$ is a colouring of $D^{\prec}[X]$.

Suppose for contradiction that $\varphi$ uses more than $R(\omega+1,\alpha+1)$
colours. Then there is a $\prec$-decreasing path $P$ of size
$R(\omega+1,\alpha+1)+1$. Note that since $D[V(P)]$ is acyclic, every arc of
$D[V(P)]$ corresponds to an edge of $D^{\prec}[V(P)]$ (i.e. for every $x,y\in
V(P)$, if $xy\in A(D)$, then $y\prec x$ and thus $xy\in E(D^{\prec})$). Hence,
$\alpha(D^{\prec}[V(P)]=\alpha(D[V(P)])\leq\alpha$. Now, since
$|V(P)|>R(\omega+1,\alpha+1)$ and $\alpha(D^{\prec}[V(P)])\leq\alpha$, we get
that $\omega(D^{\prec}[V(P)])\geq\omega+1$, a contradiction. ∎

Using the above inequation, most results of the paper can be adapted to
classes of tournaments with bounded independence number.

An obvious topic that we did not investigate is the complexity of computing
the clique number. Nguyen, Scott and Seymour ask in Section 9 of [22] if
deciding if a tournament has bounded clique number is in co-NP.

#### Acknowledgement

This research was partially supported by the ANR project DAGDigDec (JCJC)
ANR-21-CE48-0012 and by the group Casino/ENS Chair on Algorithmics and Machine
Learning.

## References

  * [1] Pierre Aboulker, Pierre Charbit, and Reza Naserasr.  Extension of Gyárfás-Sumner conjecture to digraphs.  The Electronic Journal of Combinatorics, 28(2), May 2021.
  * [2] Noga Alon, János Pach, and József Solymosi.  Ramsey-type theorems with forbidden subgraphs.  Combinatorica, 21(2):155–170, 2001.
  * [3] Jørgen Bang-Jensen and Gregory Gutin.  Classes of Directed Graphs.  Springer Publishing Company, Incorporated, 1st edition, 2018.
  * [4] Eli Berger, Krzysztof Choromanski, Maria Chudnovsky, Jacob Fox, Martin Loebl, Alex Scott, Paul Seymour, and Stéphan Thomassé.  Tournaments and colouring.  Journal of Combinatorial Theory, Series B, 103:1–20, 01 2013.
  * [5] J.A. Bondy and U.S.R Murty.  Graph Theory.  Springer Publishing Company, Incorporated, 1st edition, 2008.
  * [6] É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.
  * [7] É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.
  * [8] Romain Bourneuf and Stéphan Thomassé.  Bounded twin-width graphs are polynomially $\chi$-bounded, 2023.
  * [9] Marcin Briański, James Davies, and Bartosz Walczak.  personal communication", 2022.
  * [10] Maria Chudnovsky, Ringi Kim, Chun-Hung Liu, Paul Seymour, and Stéphan Thomassé.  Domination in tournaments.  Journal of Combinatorial Theory, Series B, 130:98–113, 2018.
  * [11] Maria Chudnovsky, Irena Penev, Alex Scott, and Nicolas Trotignon.  Substitution and $\chi$-boundedness.  Journal of Combinatorial Theory, Series B, 103(5):567–586, 2013\.
  * [12] Maria Chudnovsky, Alex Scott, Paul Seymour, and Sophie Spirkl.  Pure pairs. x. tournaments and the strong erdős-hajnal property.  European Journal of Combinatorics, 115:103786, 2024.
  * [13] Reinhard Diestel.  Graph Theory (Graduate Texts in Mathematics).  Springer, 2005.
  * [14] P. Erdös.  Graph theory and probability.  Canadian Journal of Mathematics, 11:34–38, 1959.
  * [15] Colin Geniet and Stéphan Thomassé.  First order logic and twin-width in tournaments and dense oriented graphs, 2023.
  * [16] A. Gyárfás.  On ramsey covering-number.  In Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), pages 801–816. Colloq. Math. Soc. Janos Bolyai 10, North-Holland, Amsterdam, 1975.
  * [17] A. Gyárfás.  Problems from the world surrounding perfect graphs.  Zastowania Matematyki Applicationes Mathematicae, XIX:413–441, 1987\.
  * [18] Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, and Hehui Wu.  Coloring tournaments: From local to global.  Journal of Combinatorial Theory, Series B, 138, 02 2017.
  * [19] Ararat Harutyunyan, Tien-Nam Le, Stéphan Thomassé, and Hehui Wu.  Coloring tournaments: from local to global.  J. Combin. Theory Ser. B, 138, 2019.
  * [20] Felix Klingelhoefer and Alantha Newman.  Bounding the chromatic number of dense digraphs by arc neighborhoods, 2023\.
  * [21] Tung Nguyen, Alex Scott, and Paul Seymour.  On a problem of el-zahar and erdos, 2023.
  * [22] Tung Nguyen, Alex Scott, and Paul Seymour.  Some results and problems on tournament structure, 2023.
  * [23] Michał Pilipczuk and Marek Sokołowski.  Graphs of bounded twin-width are quasi-polynomially $\chi$-bounded.  Journal of Combinatorial Theory, Series B, 161:382–406, 2023.
  * [24] Alex Scott and Paul Seymour.  A survey of $\chi$-boundedness.  Journal of Graph Theory, 95, 08 2020.
  * [25] D. P. Sumner.  Subtrees of a graph and chromatic number.  In The Theory and Applications of Graphs, (G. Chartrand, ed.), pages 557–576, New York, 1981. John Wiley & Sons.