# Computing the clique number of tournaments

Guillaume Aubian111Supported by project 22-17398S (Flows and cycles in graphs
on surfaces) of Czech Science Foundation.

###### Abstract

The clique number of a tournament is the maximum clique number of a graph
formed by keeping backwards arcs in an ordering of its vertices. We study the
time complexity of computing the clique number of a tournament and prove that,
for any integer $k\geq 3$, deciding whether a tournament has clique number at
most $k$ is NP-complete. This answers an interrogation of Nguyen, Scott and
Seymour. To do so, we make use of a construction which we then modify to
provide a counterexample to a conjecture of Aboulker, Aubian, Charbit and
Lopes.

###### Contents

  1. 1 Introduction
  2. 2 Definitions and Notations
  3. 3 Computing the clique number of tournaments is NP-complete
    1. 3.1 Useful tools to increase the clique number
    2. 3.2 Gadgets and NP-completeness
  4. 4 A counterexample to a conjecture of Aboulker, Aubian, Charbit and Lopes
  5. 5 Conclusion and future works

##  1 Introduction

Given an undirected graph $G$, its clique number, denoted $\omega(G)$, is the
maximum number of pairwise adjacent vertices of $G$. Its chromatic number,
denoted $\chi(G)$, is the minimum size of a partition of $V(G)$ in stable
sets. A tournament is an orientation of a complete graph.

The clique number is a central notion in graph theory, finding applications in
domains as diverse as chemistry [12], automatic test pattern generation [7],
bioinformatics [4] etc. Computing the clique number of a graph has been proven
to be NP-complete [8]. However, for a fixed integer $k$, whether a graph on
$n$ vertices has clique number at most $k$ can be decided in time complexity
$O(n^{k})$, by checking all subsets of at most $k$ vertices.

Given a tournament $T$ and an ordering $\prec$ of $V(T)$, we define the
backedge graph of $T$ relative to $\prec$ as $T^{\prec}=(V(T),\\{uv\in
A(T)\mid v\prec u\\})$. In [1], Aboulker, Aubian, Charbit and Lopes formally
study the clique number of tournaments defining it as the minimum over all
orderings $\prec$ of $V(T)$ of the clique number of $T^{\prec}$, and denoting
it as $\operatorname{\overrightarrow{\omega}}(T)$. Note that while they
formally introduced it, the same notion was already studied in [11] by Nguyen,
Scott and Seymour. In the beginning of Section 9, they wonder what is the time
complexity of computing the clique number of tournaments.

In this paper, we prove that, akin to the undirected case, this problem is NP-
complete:

######  Theorem 1.1.

Computing the clique number of tournaments is NP-complete.

We prove a stronger theorem. Let $k\geq 1$, the problem $k$-DIOMEGA-ORDERING
is defined as follows:

$k$-DIOMEGA-ORDERING

Input: A tournament $T$

Output: Does $\operatorname{\overrightarrow{\omega}}(T)\leq k$ ?

Unlike the undirected case, we prove the following:

######  Theorem 1.2.

Let $k\geq 3$. $k$-DIOMEGA-ORDERING is NP-complete.

Note that, since $1$-DIOMEGA-ORDERING is equivalent to testing whether a given
tournament is acyclic, and thus is polynomial, only the case $k=2$ remains
open:

######  Conjecture 1.3.

$2$-DIOMEGA-ORDERING is NP-complete.

Every graph $G$ satisfies $\chi(G)\geq\omega(G)$. However, there exist graphs
with $\chi(G)>\omega(G)$ – for example a cycle on $5$ vertices. Another
question is whether there exists a function $f$ such that for any graph $G$,
$\chi\leq f(\omega(G))$. This question was answered in the negative by Zykov
in [14]. However, various graph classes $\mathcal{C}$ actually satisfy that
for any graph $G\in\mathcal{C}$, $\chi(G)\leq f(\omega(G))$ for some function
$f$. Such graph classes are said to be $\chi$-bounded.

$\chi$-bounded classes of graphs have been widely studied, see for example
[13] for a nice survey on $\chi$-boundedness. Since most graph classes
$\mathcal{C}$ that appear in the literature are preserved under taking induced
subgraphs, and thus can be defined from a set $S$ as the class of graphs not
containing a graph in $S$ as an induced subgraph, the following question
arises naturally: at which condition on $S$ is $\mathcal{C}$ $\chi$-bounded?
In [6], Erdős proved that, if $S$ is finite and $\mathcal{C}$ is
$\chi$-bounded, $S$ must contain at least one forest. Gyárfás and Sumner thus
asked whether the converse holds:

######  Conjecture 1.4 (Gyárfás, 1975 & Sumner, 1981).

For any forest $F$, the class of graphs not containing $F$ as an induced
subgraph is $\chi$-bounded.

This conjecture remains largely open. See [13].

In $1982$, Victor Neumann-Lara introduced in [10] a directed analogue of the
chromatic number: the dichromatic number of a directed graph $D$, denoted
$\operatorname{\overrightarrow{\chi}}(D)$, is the minimum size of a partition
of its vertices into acyclic subsets[10]. This notion has been reintroduced by
Mohar in [9], and since then this notion has known a growing interest, mainly
in trying to translate undirected results to a directed setting.

Similarly to the undirected setting, Aboulker, Aubian, Charbit and Lopes have
then defined in [1] a notion of $\chi$-boundedness for tournaments: a
tournament class $\mathcal{T}$ is
$\operatorname{\overrightarrow{\chi}}$-bounded if there exists a function $f$
such that for any tournament $T\in\mathcal{T}$,
$\operatorname{\overrightarrow{\chi}}(T)\leq
f(\operatorname{\overrightarrow{\omega}}(T))$. A question that arises
naturally is the following: which tournaments $T$ are such that the class of
tournaments not containing $T$ are
$\operatorname{\overrightarrow{\chi}}$-bounded? In a similar flavour to the
directed case, they proved that such a $T$ must contain a backedge graph that
is a forest. This directly implies an analogue of Gyárfás-Sumner conjecture
for tournaments:

######  Conjecture 1.5.

Let $T$ be a tournament with a backedge graph that is a forest. The class of
tournaments not containing $T$ as a subgraph is
$\operatorname{\overrightarrow{\chi}}$-bounded.

We answer this question in the negative.

##  2 Definitions and Notations

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

Given a set $X$ and an integer $n$, $X\choose n$ is the set of all subsets of
$X$ of size exactly $n$.

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 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 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}$. Suppose one or
more of the tournaments $T_{i}$ is a transitive tournament $TT_{k}$. In that
case, 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}$.

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; otherwise, it is called backwards. 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)$ is called an
_$\operatorname{\overrightarrow{\omega}}$ -ordering_ of $T$. For $\prec$ an
ordering of a set $X$, we denote by $\prec_{\mid Y}$ the restriction of
$\prec$ to a subset $Y\subseteq X$. For $T,T^{\prime}$ two tournaments with
$V(T)\subseteq V(T^{\prime})$ and $\prec$ an ordering of $T^{\prime}$, we
sometimes use $T^{\prec}$ to denote $T^{\prec_{\mid V(T)}}$.

##  3 Computing the clique number of tournaments is NP-complete

In this section, we will be interested in the algorithmic aspects of computing
the clique number of tournaments. Our main result is the following:

######  Theorem 3.1.

Let $k\geq 3$. $k$-DIOMEGA-ORDERING is NP-complete.

which directly implies:

######  Theorem 3.2.

Computing the clique number of tournaments is NP-complete.

Note that while Theorem 3.2 is expected, as an analogue of the undirected
case, Theorem 3.1 is surprising, in that it contrasts with the undirected case
where the corresponding decision problem can be answered in polynomial time.
To prove this, we will need intermediate results: this is the purpose of
Subsection 3.1.

###  3.1 Useful tools to increase the clique number

Note that a variation of the construction in the following proof will be used
in Definition 4.3.

######  Lemma 3.3.

Let $T$ be a tournament. There exists a tournament $T^{\prime}$ with
$\operatorname{\overrightarrow{\omega}}(T^{\prime})=\operatorname{\overrightarrow{\omega}}(T)$
and such that for any $X\subseteq V(T^{\prime})$, $T^{\prime}[X]$ contains a
copy of $T$ or $T^{\prime}[\overline{X}]$ contains a copy of $T$.

###### Proof.

If $\operatorname{\overrightarrow{\omega}}(T)=1$, then $T$ is a transitive
tournament, and thus $T^{\prime}=T\Rightarrow T$ has the desired property.
Thus, we can suppose $\operatorname{\overrightarrow{\omega}}(T)\geq 2$.

Let $v_{1},\dots,v_{n}$ be a $\operatorname{\overrightarrow{\omega}}$-ordering
of $V(T)$. Let $m={{n(n-1)+1}\choose n}$ and let $T_{1},\dots,T_{m\times n}$
be $m\times n$ copies of $T$. Let $i\in\llbracket 1,n\rrbracket$. Let
$B_{i}=\llbracket 1+(i-1)\times m,i\times m\rrbracket$. Note that
$(B_{i})_{i\in\llbracket 1,n\rrbracket}$ is a partition of $\llbracket
1,m\times n\rrbracket$, thus we can associate to each $x\in\llbracket
1,m\times n\rrbracket$ an integer $B^{-1}(x)$ such that $x\in B_{B^{-1}(x)}$.
Let $\varphi_{i}$ be a bijection from $B_{i}$ to ${\llbracket
1,n\times(n-1)+1\rrbracket}\choose n$ and for $j\in B_{i}$, let $\psi_{j}$ be
a bijection from $V(T_{j})$ to $\varphi_{i}(j)$. Thus, we associate to each
$j\in B_{i}$ a list of $n$ integers $\varphi_{i}(j)$, and to each $v\in
V(T_{j})$ an element in this list. $T^{\prime}$ will be obtained from
$T_{1}\Rightarrow\dots\Rightarrow T_{m}$ by reversing arc $uw$ where $u\in
T_{i}$ and $w\in T_{j}$ if and only if:

  * •

$i<j$,

  * •

$\psi_{i}(u)=\psi_{j}(w)$,

  * •

$v_{B^{-1}(j)}v_{B^{-1}(i)}\in A(T)$.

Let us first prove that
$\operatorname{\overrightarrow{\omega}}(T^{\prime})=\operatorname{\overrightarrow{\omega}}(T)$.
Let $\prec$ be the ordering of $V(T^{\prime})$ such that if $u$ is the copy of
vertex $v_{i}$ in $T_{j}$ and $w$ is the copy of vertex $v_{i^{\prime}}$ in
$T_{j^{\prime}}$, $u\prec w$ if and only if $(j,i)$ is lexicographically
smaller than $(j^{\prime},i^{\prime})$. Let $K\subseteq V(T^{\prime})$
inducing a clique in $T^{\prime\prec}$.

Suppose that for every $i\in\llbracket 1,n\rrbracket$, $K$ intersects
$\bigcup_{j\in B_{i}}V(T_{j})$ on at most one vertex $u_{i}$. Then
$\\{v_{i}\mid u_{i}\in K\\}$ induces a clique in $T$, and thus
$|K|\leq\operatorname{\overrightarrow{\omega}}(T)$. Hence,
$|K\cap\bigcup_{j\in B_{i}}V(T_{j})|\geq 2$ for some $i\in\llbracket
1,n\rrbracket$. Let $X=K\cap\bigcup_{j\in B_{i}}V(T_{j})$. Let $u,w$ be
distinct vertices of $X$ with $u\in V(T_{j})$ and $w\in V(T_{k})$.

We cannot have $k>j$, for since $uw\in A(T)$ and $u\prec w$, $K$ would not
induce a clique in $T^{\prec}$. Hence $k=j$, and $\psi_{j}(u)\neq\psi_{j}(w)$
If $K\neq X$, let $y\in K\setminus X$ and let $\ell$ be such that $y\in
V(T_{\ell})$, then since $K$ induces a clique in $T^{\prec}$,
$\psi_{\ell}(y)=\psi_{j}(u)$ and $\psi_{\ell}(y)=\psi_{j}(w)$, which
contradicts $\psi_{j}(u)=\psi_{j}(w)$. Hence, $K=X$. But, since $\prec_{\mid
V(T_{j})}$ is a $\operatorname{\overrightarrow{\omega}}$-ordering of $T_{j}$,
$|K|\leq\operatorname{\overrightarrow{\omega}}(T)$. Thus,
$\operatorname{\overrightarrow{\omega}}(T^{\prime})\leq\operatorname{\overrightarrow{\omega}}(T)$.

Let us now prove by contradiction that for any $X\subseteq V(T^{\prime})$,
$T^{\prime}[X]$ contains a copy of $T$ or $T^{\prime}[\overline{X}]$ contains
a copy of $T$. Suppose this is not the case. Then, for every $i\in\llbracket
1,m\times n\rrbracket$, there exists a vertex $u_{i}\in X\cap T_{i}$. For
$j\in\llbracket 1,n\rrbracket$, let $C_{j}=\\{\psi_{i}(u_{i})\mid i\in
B_{j}\\}$. We have that $|C_{j}|\geq(n-1)^{2}+2$, since if there exists
$C\subseteq\llbracket 1,n(n-1)+1\rrbracket\setminus C_{j}$ of size $n$, let
$i=\varphi^{-1}(C)$, then $\psi_{i}(u_{i})\in C$, contradicting that
$\psi_{i}(u_{i})\in C_{j}$. Hence $|\bigcap_{j\in\llbracket
1,n\rrbracket}C_{j}|\geq 1$, which implies there exists
$c\in\bigcap_{j\in\llbracket 1,n\rrbracket}C_{j}$. Thus, for every
$j\in\llbracket 1,n\rrbracket$, there exists a vertex $w_{j}\in T_{i}\cap X$
with $i\in B_{j}$ such that $\psi_{i}(w_{j})=c$. By definition of
$T^{\prime}$, $w_{j}w_{j}^{\prime}\in A(T^{\prime})$ if and only if
$v_{j}v_{j}^{\prime}\in A(T)$, and thus $T^{\prime}[\\{w_{j}\mid
j\in\llbracket 1,n\rrbracket\\}]$ is isomorphic to $T$, yet is included in
$X$, a contradiction.

∎

Using this first lemma, we can then define the tournament $T_{k}$ as follows:

######  Definition 3.4.

Let $k\in\mathbb{N}$. Let $T$ be any tournament with
$\operatorname{\overrightarrow{\omega}}(T)=k$. We denote as $T_{k}$ a
tournament such that $\operatorname{\overrightarrow{\omega}}(T_{k})=k$ and for
any $X\subseteq V(T_{k})$, $T_{k}[X]$ or $T_{k}[\overline{X}]$ contains a copy
of $T$.

Note that such a $T_{k}$ necessarily exists due to Lemma 3.3. Using $T_{k}$,
we can modify constructions to force the order of some pairs of vertices.

######  Lemma 3.5.

Let $k\in\mathbb{N}$. Let $D$ be a digraph, let $u,v\in V(D)$ and let
$W\subseteq u^{+}\cap v^{-}$ such that $D[W]=T_{k}$. If $\prec$ is an ordering
of $V(D)$ with $\omega(D^{\prec})\leq k$, then $u\prec v$.

###### Proof.

Suppose $v\prec u$. Let $W^{\prec}=\\{w\in W\mid w\prec u\\}$ and
$W^{\succ}=\\{w\in W\mid u\prec w\\}$. Since $u\Rightarrow W$,
$\operatorname{\overrightarrow{\omega}}(W^{\prec})\leq k-1$. Thus, there is a
copy of $T$ in $W^{\succ}$ and thus
$\operatorname{\overrightarrow{\omega}}(D[W^{\succ}])=k$. But since
$W\Rightarrow v$ and $v\prec u\prec W^{\succ}$, this implies that
$\omega(D^{\prec})>k$, a contradiction. ∎

We can also use $T_{k}$ to leverage
$\operatorname{\overrightarrow{\omega}}$-orderings of a tournament of a given
clique number into $\operatorname{\overrightarrow{\omega}}$-orderings of a
tournament with a larger clique number.

######  Lemma 3.6.

Let $k\in\mathbb{N}$. If $D$ is a digraph with
$\operatorname{\overrightarrow{\omega}}(D)=k-1$, then
$\operatorname{\overrightarrow{\omega}}(\Delta(1,D,T_{k}))=k$ and
$\\{\prec\mid\omega(D^{\prec})=k-1\\}=\\{\prec_{\mid
V(D)}\mid\omega(\Delta(1,D,T_{k})^{\prec})=k\\}$

###### Proof.

We will prove that $D^{\prime}=\Delta(1,D,T_{k})$ has the desired property.
Clearly $\operatorname{\overrightarrow{\omega}}(D^{\prime})\geq k$ since
$T_{k}$ is a subdigraph of $D^{\prime}$. Let $\\{v\\}=V(D^{\prime})\setminus
V(D)\setminus V(T_{k})$.

Let $\prec_{k}$ be a $\operatorname{\overrightarrow{\omega}}$-ordering of
$T_{k}$. For any $\operatorname{\overrightarrow{\omega}}$-ordering $\prec$ of
$V(D)$, let $\prec^{\prime}$ be the ordering of $V(D^{\prime})$ obtained by
concatenating the vertices of $D$ ordered according to $\prec$, followed by
the vertices of $T_{k}$ ordered according to $\prec_{k}$ followed by vertex
$v$. Then $\prec^{\prime}$ satisfies $\omega(D^{\prime\prec^{\prime}})=k$, and
$\prec^{\prime}_{\mid V(D)}=\prec$. Thus
$\operatorname{\overrightarrow{\omega}}(D^{\prime})\leq k$ and
$\\{\prec\mid\omega(D^{\prec})=k-1\\}\subseteq\\{\prec_{\mid
V(D)}\mid\omega(\Delta(1,D,T_{k})^{\prec})=k\\}$.

Let $\prec^{\prime}$ be an ordering of $V(D^{\prime})$ with
$\omega(D^{\prime\prec^{\prime}})=k$. Let $u\in V(D)$: by Lemma 3.5,
$u\prec^{\prime}v$. Thus, $T_{k}\prec^{\prime}v$, which implies that
$\omega(T^{\prec^{\prime}}_{k})=k-1$. Thus $\\{\prec_{\mid
V(D)}\mid\omega(\Delta(1,D,T_{k})^{\prec})=k\\}\subseteq\\{\prec\mid\omega(D^{\prec})=k-1\\}$.
∎

###  3.2 Gadgets and NP-completeness

Using the tournaments $T_{k}$ constructed in Definition 3.4, we can now build
gadgets that will be used to prove that $k$-DIOMEGA-ORDERING is NP-complete.
We will do so using a reduction from $3$-SAT.

In order to do so, we need to build a tournament in which one fixed edge is
forward if and only if another fixed edge is not. This tournament will encode
a variable, and which edge is forward will encode whether this variable is set
to true.

######  Lemma 3.7.

There exists a tournament $T_{var}$ and $uv,wx$ disjoint arcs of $T_{var}$
such that:

  * •

$\operatorname{\overrightarrow{\omega}}(T_{var})=3$

  * •

in any $\operatorname{\overrightarrow{\omega}}$-ordering, exactly one of $uv$
or $wx$ is forward.

  * •

there exists a $\operatorname{\overrightarrow{\omega}}$-ordering in which $uv$
is forward

  * •

there exists a $\operatorname{\overrightarrow{\omega}}$-ordering in which $uv$
is backward

This proof relies mainly on computer help. However, since checking all
orderings of a graph is a complex task, we proceed by first finding such a
tournament with $\operatorname{\overrightarrow{\omega}}=2$, and then
leveraging it using Lemma 3.6.

###### Proof.

Let $T$ be the tournament with the following ordered graph as a backedge
graph:

$1$$2$$3$$4$$5$$6$$7$$8$$9$ Figure 1: The backedge graph corresponding to the
ordering $1\prec 2\prec 3\prec 4\prec 5\prec 6\prec 7\prec 8\prec 9$

and let $uv=7\rightarrow 9$ and $wx=8\rightarrow 3$.

Note that $T$ is not transitive and the ordering $1\prec 2\prec 3\prec 4\prec
5\prec 6\prec 7\prec 8\prec 9$ is such that $\omega(T^{\prec})=2$, thus
$\operatorname{\overrightarrow{\omega}}(T)=2$.

The ordering $1\prec 2\prec 3\prec 4\prec 5\prec 6\prec 7\prec 8\prec 9$ is a
$\operatorname{\overrightarrow{\omega}}$-ordering in which $uv$ is forward.
See Figure 1.

The ordering $6\prec 8\prec 2\prec 9\prec 1\prec 3\prec 4\prec 5\prec 7$ is a
$\operatorname{\overrightarrow{\omega}}$-ordering in which $uv$ is backward.
See Figure 2.

$6$$8$$2$$9$$1$$3$$4$$5$$7$ Figure 2: The backedge graph of $T$ corresponding
to the ordering $6\prec 8\prec 2\prec 9\prec 1\prec 3\prec 4\prec 5\prec 7$

It can be checked that in every
$\operatorname{\overrightarrow{\omega}}$-ordering, exactly one of $uv$ or $wx$
is forward. See for example the Python code in Figure 3.

import itertools

T = [ [0,1,1,1,1,1,0,0,0], [0,0,1,1,0,0,1,0,1], [0,0,0,1,1,1,1,0,0],
[0,0,0,0,1,0,1,1,1], [0,1,0,0,0,1,1,1,0], [0,1,0,1,0,0,1,1,0],
[1,0,0,0,0,0,0,1,1], [1,1,1,0,0,0,0,0,1], [1,0,1,0,1,1,0,0,0] ]

for P in itertools.permutations(range(9)): omega_at_most_two = True for i in
range(9): for j in range(i + 1,9): for k in range(j + 1, 9): if T[P[j]][P[i]]
and T[P[k]][P[j]] and T[P[k]][P[i]]: omega_at_most_two = False if
omega_at_most_two: assert((P.index(6) < P.index(8)) != (P.index(7) <
P.index(2)))

Figure 3: Python code to check that in every
$\operatorname{\overrightarrow{\omega}}$-ordering, exactly one of $uv$ or $wx$
is forward

By Lemma 3.6, there exists a tournament $T_{3}$ such that
$T_{var}=\Delta(1,T,T_{3})$ satisfies the desired property.

∎

We also need a gadget tournament to encode clauses, In order to do so, we
build a tournament in which three fixed arcs are such that at least one of
them is always backward. This will encode a disjunction.

######  Lemma 3.8.

There exists a tournament $T_{clause}$ and $uv,wx,yz$ pairwise disjoint arcs
of $T_{clause}$ such that:

  * •

$\operatorname{\overrightarrow{\omega}}(T_{clause})=3$

  * •

for every $\operatorname{\overrightarrow{\omega}}$-ordering $\prec$ of
$T_{clause}$, one of $uv,wx,yz$ is backward

  * •

for every two arcs in $uv,wx,yz$, there exists a
$\operatorname{\overrightarrow{\omega}}$-ordering $\prec$ in which these two
arcs are forward

Similarly to Lemma 3.7, this proof relies mainly on computer help and we
proceed by first finding such a tournament with clique number $2$, then
leveraging it thanks to Lemma 3.6.

###### Proof.

Let $T$ be the tournament with the following ordered graph as a backedge
graph:

$1$$2$$3$$4$$5$$6$$7$$8$ Figure 4: The backedge graph corresponding to the
ordering $1\prec 2\prec 3\prec 4\prec 5\prec 6\prec 7\prec 8$

and let $uv=5\rightarrow 6$, $wx=2\rightarrow 4$ and $yz=8\rightarrow 3$.

Note that $T$ is not transitive and the ordering $1\prec 2\prec 2\prec 3\prec
4\prec 5\prec 6\prec 7\prec 8$ is such that $\omega(T^{\prec})=2$, thus
$\operatorname{\overrightarrow{\omega}}(T)=2$.

The ordering $1\prec 2\prec 3\prec 4\prec 5\prec 6\prec 7\prec 8$ is a
$\operatorname{\overrightarrow{\omega}}$-ordering in which $uv$ and $wx$ are
forward. See Figure 4.

The ordering $4\prec 7\prec 5\prec 8\prec 1\prec 2\prec 6\prec 3$ is a
$\operatorname{\overrightarrow{\omega}}$-ordering in which $uv$ and $yz$ are
forward. See Figure 5.

$1$$2$$3$$4$$5$$6$$7$$8$ Figure 5: The backedge graph of $T$ corresponding to
the ordering $4\prec 7\prec 5\prec 8\prec 1\prec 2\prec 6\prec 3$

The ordering $1\prec 2\prec 4\prec 6\prec 7\prec 5\prec 8\prec 3$ is a
$\operatorname{\overrightarrow{\omega}}$-ordering in which $wx$ and $yz$ are
forward. See Figure 6.

$1$$2$$3$$4$$5$$6$$7$$8$ Figure 6: The backedge graph of $T$ corresponding to
the ordering $1\prec 2\prec 4\prec 6\prec 7\prec 5\prec 8\prec 3$

It can be checked that in every
$\operatorname{\overrightarrow{\omega}}$-ordering, at least one of $uv$, $wx$
or $yz$ is backward. See the Python code in Figure 7.

import itertools

T = [ [0,1,1,1,1,0,0,0], [0,0,1,1,0,1,1,0], [0,0,0,1,1,0,1,0],
[0,0,0,0,1,1,1,0], [0,1,0,0,0,1,0,1], [1,0,1,0,0,0,1,1], [1,0,0,0,1,0,0,1],
[1,1,1,1,0,0,0,0], ]

for P in itertools.permutations(range(8)): omega_at_most_two = True for i in
range(8): for j in range(i + 1,8): for k in range(j + 1, 8): if T[P[j]][P[i]]
and T[P[k]][P[j]] and T[P[k]][P[i]]: omega_at_most_two = False if
omega_at_most_two: assert(P.index(5) < P.index(4) or P.index(3) < P.index(1)
or P.index(2) < P.index(7))

Figure 7: Python code to check that in every
$\operatorname{\overrightarrow{\omega}}$-ordering, one of $uv,wx$ or $yz$ is
backward

By Lemma 3.6, there exists a tournament $T_{3}$ such that
$T_{clause}=\Delta(1,T,T_{3})$ satisfies the desired property.

∎

We can then conclude:

######  Theorem 3.9.

$3$-DIOMEGA-ORDERING is NP-complete.

###### Proof.

Clearly, this problem is in NP. Let us now prove it is NP-hard.

We will reduce $3$-SAT to this problem. Let $\varphi$ be a $3$-SAT formula on
variables $v_{i}$ for $i\in\llbracket 1,n\rrbracket$ with clauses
$C_{j}=C_{j,1}\lor C_{j,2}\lor C_{j,3}$ where $C_{j,k}$ are literals. Without
loss of generality, we can suppose no variable appears more than once in the
literals of a clause. For every variable $v_{i}$, we create a copy $A_{i}$ of
$T_{var}$ (as defined in Lemma 3.7). Let $f^{+}_{i}$ and $f^{-}_{i}$ be the
respective copies of $uv$ and $wx$ in $A_{i}$. For every clause $C_{j}$, we
create a copy $B_{j}$ of $T_{clause}$ (as defined in Lemma 3.8). Let
$e^{1}_{j},e^{2}_{j},e^{3}_{j}$ be the respective copies of $uv,wx,yz$ in
$B_{j}$.

Let $T_{3}$ be defined as in Definition 3.4.

We will consider the tournament $T=A_{1}\Rightarrow\dots\Rightarrow
A_{n}\Rightarrow T_{3}\Rightarrow B_{1}\Rightarrow\dots\Rightarrow B_{m}$ in
which we revert some arcs as follows: for every literal $C_{j,k}$
corresponding to variable $v_{i}$ , let $ab=f^{+}_{i}$ if it is a positive
literal and $ab=f^{-}_{i}$ otherwise and let $cd=e^{k}_{j}$. We revert arcs
$ac,ad,bc$ and $bd$ (thus after the reversal, $ca,da,cb,db\in A(T)$).

Let us prove that $\operatorname{\overrightarrow{\omega}}(T)=3$ if and only if
$\varphi$ is satisfiable.

First, suppose $\operatorname{\overrightarrow{\omega}}(T)=3$ and let $\prec$
be a $\operatorname{\overrightarrow{\omega}}$-ordering of $T$. Note that by
Lemma 3.5, for $i\in\llbracket 1,n\rrbracket$ and $j\in\llbracket
1,m\rrbracket$, $V(A_{i})\prec V(B_{j})$. Let $\nu$ be the assignment such
that $\nu(v_{i})$ if and only if the arc $f^{+}_{i}$ is forward or
equivalently, if and only if the arc $f^{-}_{i}$ is backward. We will prove
that $\nu$ is a satisfies $\varphi$. Let $C_{j}$ be a clause. Since $B_{j}$ is
a copy of $T_{clause}$, there exists $k\in\\{1,2,3\\}$ such that
$e^{k}_{j}=cd$ is backward, due to Lemma 3.8. Let $ab=f^{+}_{i}$ if
$C^{k}_{j}$ is a positive literal and $ab=f^{-}_{i}$ otherwise. Then, $ab$
must be forward, for otherwise $\\{a,b,c,d\\}$ would induce a $K_{4}$ in
$T^{\prec}$ since $ca,da,cb$ and $db$ are backward. Thus the literal
$C^{k}_{j}$ is satisfied. Thus every clause is satisfied by $\nu$. Hence
$\varphi$ is satisfiable.

Now, suppose $\varphi$ is satisfiable. We will build an ordering $\prec$ of
$V(T)$ such that $\omega(T^{\prec})=3$. Let $\nu$ be an assignment satisfying
$\varphi$, and for $j\in\llbracket 1,m\rrbracket$, let $k_{j}$ be such that
$C_{j,k_{j}}$ is satisfied. Our ordering $\prec$ will be defined as follows:

  * •

First come vertices of $A_{1}$, ordered following a
$\operatorname{\overrightarrow{\omega}}$-ordering of $V(A_{1})$ in which
$f^{+}_{1}$ is forward if and only if $\nu(v_{1})$

  * •

…

  * •

then come vertices of $A_{n}$, ordered following a
$\operatorname{\overrightarrow{\omega}}$-ordering of $V(A_{n})$ in which
$f^{+}_{n}$ is forward if and only if $\nu(v_{n})$

  * •

then come vertices of $T_{3}$, ordered following a
$\operatorname{\overrightarrow{\omega}}$-ordering of $T_{3}$

  * •

then come vertices of $B_{1}$, ordered following a
$\operatorname{\overrightarrow{\omega}}$-ordering of $V(B_{1})$ in which, for
$k\in\\{1,2,3\\}\setminus\\{k_{1}\\}$, $e^{k}_{1}$ is forward

  * •

…

  * •

then come vertices of $B_{m}$, ordered following a
$\operatorname{\overrightarrow{\omega}}$-ordering of $V(B_{m})$ in which, for
$k\in\\{1,2,3\\}\setminus\\{k_{m}\\}$, $e^{k}_{m}$ is forward

Suppose there exists $K\subset V(T)$ such that $T^{\prec}[K]=K_{4}$. $K$
cannot intersect $V(T_{3})$, since $V(T_{3})$ is anticomplete to
$V(T)\setminus V(T_{3})$ in $T^{\prec}$ and $\omega(T^{\prec}_{3})=3$. $K$
cannot intersect both $V(A_{i})$ and $V(A_{i^{\prime}})$ whenever $i\neq
i^{\prime}$ since $A_{i}$ is anticomplete with $A_{i^{\prime}}$ in
$T^{\prec}$. For the same reason, $K$ cannot intersect both $V(B_{j})$ and
$V(B_{j^{\prime}})$ whenever $j\neq j^{\prime}$. Thus, $K\subset V(A_{i})\cup
V(B_{j})$ for some integers $i\in\llbracket 1,n\rrbracket$ and $j\in\llbracket
1,m\rrbracket$. Since $\omega(A^{\prec}_{i})=3$, $K$ intersect $B_{j}$, and
since $\omega(B^{\prec}_{j})=3$, $K$ intersects $A_{i}$. Since vertices of
$A_{i}$ have at most $2$ inneighbours in $V(B_{j})$ and $V(A_{i})\prec
V(B_{j})$, $K$ intersects $B_{j}$ on at most $2$ vertices. Similarly, since
vertices of $B_{j}$ have at most $2$ outneighbours in $V(A_{i})$ and
$V(A_{i})\prec V(B_{j})$, $K$ intersect $A_{i}$ on at most $2$ vertices. Thus
$K=\\{u,v,w,x\\}$ with $v\prec u$ two distinct vertices of $A_{i}$ and $x\prec
w$ two distinct vertices of $B_{j}$. This is only possible if there exists
$k\in\\{1,2,3\\}$ such that $wx=e^{k}_{j}$ and $uv=f^{+}_{i}$ if $C^{k}_{j}$
is a positive literal and $uv=f^{-}_{i}$ otherwise. Since $e^{k}_{j}$ is
backward, this implies $k=k_{j}$. and thus $uv$ is not backward. Thus,
$T^{\prec}[K]\neq K_{4}$, a contradiction.

∎

Using Lemma 3.6, we directly get:

######  Corollary 3.10.

For any fixed $k\geq 3$, $k$-DIOMEGA-ORDERING is NP-complete.

##  4 A counterexample to a conjecture of Aboulker, Aubian, Charbit and Lopes

In [1], Aboulker, Aubian, Charbit and Lopes proposed the following conjecture,
a tournament version of Gyárfás-Sumner conjecture:

######  Conjecture 4.1.

[Aboulker, Aubian, Charbit, Lopes, 2023] Let $T$ be a tournament whose one
backedge graph is a forest. Let $k\in\mathbb{N}$. Tournaments not containing
$T$ as a subtournament and with clique number at most $k$ have bounded
dichromatic number.

The main result of this section is a disproof of this conjecture:

######  Theorem 4.2.

Conjecture 4.1 is false.

In order to do so, we adapt the construction from Lemma 3.3.

######  Definition 4.3.

Let $T$ be a tournament on $n$ vertices. We define the tournament $\Pi(T)$ and
the ordering $\prec^{\Pi}$ of $V(\Pi(T))$ as follows:

Let $m={{2n-1}\choose n}$. We start from $2m+1$ copies of $T$, denoted as
$A_{1},\dots,A_{m},B,C_{1},\dots,C_{m}$. Let $\varphi\colon\llbracket
1,m\rrbracket\to{{\llbracket 1,2n+1\rrbracket}\choose n}$ be a bijection and,
for $i\in\llbracket 1,m\rrbracket$, let $\psi_{j}\colon V(T)\to\varphi(j)$ be
a bijection. $\Pi(T)$ is defined from $A_{1}\Rightarrow\dots\Rightarrow
A_{m}\Rightarrow B\Rightarrow C_{1}\Rightarrow\dots\Rightarrow C_{m}$ by
reversing arc $uv$ with $u\in V(A_{i}),v\in V(C_{j})$ if and only if
$\psi_{i}(u)=\psi_{j}(v)$. $\prec^{\Pi}$ is defined as the concatenation of
any $\operatorname{\overrightarrow{\omega}}$-orderings of $A_{1}$, then
$A_{2}$, …, then $A_{m}$, then $B$, then $C_{1}$, …and then $C_{m}$.

An easy consequence of Lemma 3.3 is the following lemma:

######  Lemma 4.4.

Let $T$ be a tournament. If $\operatorname{\overrightarrow{\omega}}(T)=2$ then
$\omega(\Pi(T)^{\prec^{\Pi}})=2$.

###### Proof.

Since $T$ contains a directed triangle, $\Pi(T)$ is included in the
construction of $T^{\prime}$ as defined in the proof of Lemma 3.3, which by
Lemma 3.3 has the same clique number as $T$. Since $\Pi(T)$ contains $T$,
$\omega(\Pi(T)^{\prec^{\Pi}})=2$. ∎

Thus $\Pi(T)$ preserves $\operatorname{\overrightarrow{\omega}}$.

######  Lemma 4.5.

Let $T$ be a tournament.
$\operatorname{\overrightarrow{\chi}}(\Pi(T))>\operatorname{\overrightarrow{\chi}}(T)$.

###### Proof.

Suppose this is not the case, and let $X$ be an acyclic subset of $\Pi(T)$
such that
$\operatorname{\overrightarrow{\chi}}(\Pi(T)[\overline{X}])<\operatorname{\overrightarrow{\chi}}(T)$.
Thus $X$ must intersect $A_{1},\dots,A_{m},B,C_{1},\dots,C_{m}$ on at least
one vertex $a_{1},\dots,a_{m},b,c_{1},\dots,c_{m}$. Let
$A=\\{\psi_{i}(a_{i})\mid i\in\llbracket 1,m\rrbracket\\}$ and
$C=\\{\psi_{i}(c_{i})\mid i\in\llbracket 1,m\rrbracket\\}$. $|A|\geq n$ since
every subset $S\in{\llbracket 1,2n-1\rrbracket\choose n}$ intersects $X$ on
vertex $a_{\varphi^{-1}(S)}$. Similarly, $|C|\geq n$, and thus $|A\cap C|\geq
1$. Let $x\in A\cap C$, and let $i,j\in\llbracket 1,m\rrbracket$ be such that
$a_{i}\in X\cap V(A_{i})$, $c_{j}\in X\cap V(C_{j})$ and
$\psi_{i}(a_{i})=\psi_{j}(c_{j})=x$. Then $a_{i}\rightarrow b\rightarrow
c_{j}\rightarrow a_{i}$ is a directed triangle in $C$, a contradiction. ∎

Our counterexample will then be defined recursively as $D_{1}=C_{3}$ and
$D_{k}=\Pi(D_{k-1})$ for $k\geq 2$. We directly get the following result as a
corollary from the previous two theorems:

######  Corollary 4.6.

$\operatorname{\overrightarrow{\chi}}(\\{D_{k}\mid k\geq 1\\})$ is unbounded,
but for any $k\geq 1$, $\operatorname{\overrightarrow{\omega}}(D_{k})=2$.

We will prove that there exists a tournament with a backedge graph that is a
forest which does not appear as a subgraph of any $D_{k}$. In order to do so,
we need this sufficient condition on subtournaments of $\\{D_{k}\mid k\geq
1\\}$.

######  Lemma 4.7.

Let $T$ be a strong tournament that is a subgraph of $D_{k}$ for some $k\geq
1$. Then $T$ admits a $\operatorname{\overrightarrow{\omega}}$-ordering
$\prec$ and a vertex $x$ satisfying the following four rules:

  1. 1.

there exists $y\prec x$

  2. 2.

for any $a,b,c,d$ with $a,b\prec x\preceq c,d$, if $ca,da,cb\in A(T)$ then
$db\in A(T)$

  3. 3.

for any $a\preceq u\prec w\preceq b\prec x\preceq v$, if there is an $ab$-path
in $T^{\prec}[\\{y\mid y\prec x\\}]$, either $uv\in A(T)$ or $wv\in A(T)$

  4. 4.

for any $v\prec x\preceq a\preceq u\prec w\preceq b$ if there is an $ab$-path
in $T^{\prec}[\\{y\mid x\preceq y\\}]$, either $vu\in A(T)$ or $vw\in A(T)$

###### Proof.

Let $k$ be minimum such that there exists $X$ with $D_{k}[X]=T$. It is
straightforward to check the lemma whenever $k=1$, and thus we can suppose
$k\geq 2$. Let $m,n,A_{1},\dots,A_{m},B,C_{1},\dots,C_{m}$ and $\prec^{\Pi}$
be defined as in Definition 4.3. Let $\prec=\prec^{\Pi}_{\mid X}$. $X$ must
intersect one of $(C_{i})_{i\in\llbracket 1,m\rrbracket}$ for $T$ is strong
and $T$ is not a subtournament of any $A_{i}$ nor of $B$. Let $x$ be the
minimum vertex (relative to order $\prec$) in $X\cap\bigcup_{i\in\llbracket
1,m\rrbracket}V(C_{i})$. We will prove that $\prec$ and $x$ satisfy the four
rules. In order to do so, we will first need the following claim:

######  Claim 4.7.1.

Let $w,y\in X$ such that $w\prec x\preceq y$ and $yz\in A(D_{k})$. There exist
$i\in\llbracket 1,m\rrbracket$ such that $w\in V(A_{i})$ and $j\in\llbracket
1,m\rrbracket$ such that $y\in V(C_{j})$.

Proof of Claim :

Since $w\prec x$ and $x$ is the leftmost vertex in
$X\cap\bigcup_{i\in\llbracket 1,m\rrbracket}V(C_{i})$, either $w\in V(B)$ or
$w\in\bigcup_{i\in\llbracket 1,m\rrbracket}V(A_{i})$. Since $x\preceq y$,
there exists $j\in\llbracket 1,m\rrbracket$ such that $y\in V(C_{j})$. This,
combined with the fact that $yw\in A(D_{k})$ implies that $w\notin V(B)$.
Thus, there exists $i\in\llbracket 1,m\rrbracket$ such that $w\in V(A_{i})$.

$\square$

Rule 1:

If there does not exist any $y\prec x$, then either $T$ is not strong or $T$
is a subtournament of some $C_{i}$, a contradiction.

Rule 2:

Let $a,b,c,d\in X$ with $a,b\prec x\preceq c,d$ and $ca,da,cb\in A(D_{k})$. By
Claim 4.7.1, there exists $i,i^{\prime},j,j^{\prime}\in\llbracket
1,m\rrbracket$ such that $a\in V(A_{i}),b\in V_{i^{\prime}},c\in V(C_{j})$ and
$d\in V(C_{j^{\prime}})$. Then, the fact that $ca,da,cb\in A(D_{k})$ implies
that $\psi_{i}(a)=\psi_{j}(c)$, $\psi_{i}(a)=\psi_{j^{\prime}}(d)$ and
$\psi_{j}(c)=\psi_{i^{\prime}}(b)$. Hence
$\psi_{i^{\prime}}(b)=\psi_{j^{\prime}}(d)$, and thus $db\in A(D_{k})$.

Rule 3:

Suppose, by contradiction, that there exist $a,b,u,v,w$ such that there is an
$ab$-path in $T^{\prec}[\\{y\mid y\prec x\\}]$ and $a\preceq u\prec w\preceq
b\prec x\preceq v$, $vu\in A(D_{k})$ and $vw\in A(D_{k})$. By Claim 4.7.1,
there exists $i^{\prime}$ such that $u\in V(A_{i^{\prime}})$ and $j$ such that
$v\in V(C_{j})$. Since $a\preceq u$, there exists $i$ such that $a\in
V(A_{i})$, and since there exists an $ab$-path in $T^{\prec}[\\{y\mid y\prec
x\\}]$, $b\in V(A_{i})$. But vertices of $A_{i}$ are continguous in the
ordering $\prec$, thus $u,w\in V(A_{i})$. Since $vu\in A(D_{k})$,
$\psi_{i}(u)=\psi_{j}(v)$. Since $vw\in A(D_{k})$, $\psi_{i}(w)=\psi_{j}(v)$.
Thus $\psi_{i}(u)=\psi_{i}(w)$, a contradiction to the fact that $\psi_{i}$ is
a bijection.

Rule 4:

Suppose, by contradiction, that there exist $a,b,u,v,w$ such that there is an
$ab$-path in $T^{\prec}[\\{y\mid x\preceq y\\}]$, $v\prec x\preceq a\preceq
u\prec w\preceq b$, $uv\in A(D_{k})$ and $wv\in A(D_{k})$. By Claim 4.7.1,
there exists $i$ such that $v\in V(A_{i})$ and $j^{\prime}$ such that $w\in
V(C_{j^{\prime}})$. Since $w\preceq b$, there there exists $j$ such that $b\in
V(C_{j})$, and since there exists an $ab$-path in $T^{\prec}[\\{y\mid x\preceq
y\\}]$, $a\in V(C_{j})$. But vertices of $C_{j}$ are continguous in the
ordering $\prec$, thus $u,w\in V(C_{j})$. Since $uv\in A(D_{k})$,
$\psi_{i}(v)=\psi_{j}(u)$. Since $vw\in A(D_{k})$, $\psi_{i}(v)=\psi_{j}(w)$.
Thus $\psi_{j}(u)=\psi_{j}(w)$, a contradiction to the fact that $\psi_{j}$ is
a bijection. ∎

Let $R_{5}$ be the tournament of Figure 8:

$1$$2$$3$$4$$5$ Figure 8: $R_{5}$

We can now conclude this section with our main theorem.

######  Theorem 4.8.

Conjecture 4.1 is false.

###### Proof.

We will proceed by proving that $R_{5}$ has a backedge graph that is a forest,
yet is not a subtournament of any $D_{k}$, for $k\geq 1$. In order to do so,
let us first enumerate all backedge graphs of $R_{5}$ using the Python code in
Figure 9 (note that we restrict ourselves to
$\operatorname{\overrightarrow{\omega}}$-orderings in which vertex $1$ stays
at first position, since $R_{5}$ is vertex-transitive).

import itertools

T = [ [0,1,1,0,0], [0,0,1,1,0], [0,0,0,1,1], [1,0,0,0,1], [1,1,0,0,0] ]

for P in itertools.permutations(range(5)): omega_at_most_two = True for i in
range(5): for j in range(i + 1,5): for k in range(j + 1, 5): if T[P[j]][P[i]]
and T[P[k]][P[j]] and T[P[k]][P[i]]: omega_at_most_two = False if P[0] == 0
and omega_at_most_two: print(P)

Figure 9: A Python code enumerating all
$\operatorname{\overrightarrow{\omega}}$-orderings of $R_{5}$.
$1$$2$$3$$4$$5$$1$$2$$4$$3$$5$$1$$2$$4$$5$$3$$1$$3$$2$$4$$5$$1$$3$$4$$2$$5$$1$$3$$4$$5$$2$$1$$4$$2$$3$$5$$1$$4$$2$$5$$3$$1$$4$$5$$2$$3$
Figure 10: All $\operatorname{\overrightarrow{\omega}}$-orderings of $R_{5}$

The list of all such $\operatorname{\overrightarrow{\omega}}$-orderings can be
found in Figure 10. Note that the backedge graph corresponding to the order
$1\prec 2\prec 3\prec 4\prec 5$ is a forest.

$\operatorname{\overrightarrow{\omega}}$-ordering $\prec$ | $x$ | broken rule
---|---|---
$1\prec 2\prec 3\prec 4\prec 5$ | 1 | rule $1$
| 2 | rule $4$ with $a=2,b=5,u=4,v=1$ and $w=5$
| 3 | rule $2$ with $a=1,b=2,c=5$ and $d=4$
| 4 | rule $2$ with $a=1,b=2,c=5$ and $d=4$
| 5 | rule $3$ with $a=1,b=4,u=1,v=5$ and $w=2$
$1\prec 2\prec 4\prec 3\prec 5$ | 1 | rule $1$
| 2 | rule $4$ with $a=2,b=5,u=4,v=1$ and $w=5$
| 3 | rule $3$ with $a=1,b=4,u=1,v=5$ and $w=2$
| 4 | rule $2$ with $a=1,b=2,c=5$ and $d=4$
| 5 | rule $3$ with $a=1,b=4,u=1,v=5$ and $w=2$
$1\prec 2\prec 4\prec 5\prec 3$ | 1 | rule $1$
| 2 | rule $4$ with $a=2,b=5,u=4,v=1$ and $w=5$
| 3 | rule $3$ with $a=1,b=5,u=4,v=3$ and $w=5$
| 4 | rule $2$ with $a=1,b=2,c=5$ and $d=4$
| 5 | rule $3$ with $a=1,b=4,u=1,v=5$ and $w=2$
$1\prec 3\prec 2\prec 4\prec 5$ | 1 | rule $1$
| 2 | rule $4$ with $a=2,b=5,u=4,v=1$ and $w=5$
| 3 | rule $4$ with $a=3,b=5,u=4,v=1$ and $w=5$
| 4 | rule $2$ with $a=1,b=2,c=5$ and $d=4$
| 5 | rule $3$ with $a=1,b=4,u=1,v=5$ and $w=2$
$1\prec 3\prec 4\prec 2\prec 5$ | 1 | rule $1$
| 2 | rule $3$ with $a=1,b=4,u=3,v=2$ and $w=4$
| 3 | rule $4$ with $a=3,b=5,u=4,v=1$ and $w=5$
| 4 | rule $4$ with $a=4,b=5,u=4,v=1$ and $w=5$
| 5 | rule $3$ with $a=1,b=2,u=1,v=5$ and $w=2$
$1\prec 3\prec 4\prec 5\prec 2$ | 1 | rule $1$
| 2 | rule $3$ with $a=1,b=4,u=3,v=2$ and $w=4$
| 3 | rule $4$ with $a=3,b=2,u=4,v=1$ and $w=5$
| 4 | rule $4$ with $a=4,b=2,u=4,v=1$ and $w=5$
| 5 | rule $3$ with $a=1,b=4,u=3,v=2$ and $w=4$
$1\prec 4\prec 2\prec 3\prec 5$ | 1 | rule $1$
| 2 | rule $4$ with $a=2,b=5,u=2,v=4$ and $w=3$
| 3 | rule $3$ with $a=1,b=2,u=1,v=5$ and $w=2$
| 4 | rule $4$ with $a=4,b=5,u=4,v=1$ and $w=5$
| 5 | rule $3$ with $a=1,b=2,u=1,v=5$ and $w=2$
$1\prec 4\prec 2\prec 5\prec 3$ | 1 | rule $1$
| 2 | rule $4$ with $a=2,b=3,u=2,v=4$ and $w=3$
| 3 | rule $3$ with $a=1,b=5,u=4,v=3$ and $w=5$
| 4 | rule $4$ with $a=4,b=5,u=4,v=1$ and $w=5$
| 5 | rule $3$ with $a=1,b=2,u=1,v=5$ and $w=2$
$1\prec 4\prec 5\prec 2\prec 3$ | 1 | rule $1$
| 2 | rule $2$ with $a=4,b=5,c=3$ and $d=2$
| 3 | rule $3$ with $a=1,b=5,u=4,v=3$ and $w=5$
| 4 | rule $4$ with $a=4,b=2,u=4,v=1$ and $w=5$
| 5 | rule $4$ with $a=5,b=3,u=2,v=4$ and $w=3$
Figure 11: For every $\operatorname{\overrightarrow{\omega}}$-ordering of
$R_{5}$ and every choice of vertex $x$, which rule of Lemma 4.7 is broken?

The table in Figure 11 returns, for each
$\operatorname{\overrightarrow{\omega}}$-ordering and each choice of vertex
$x$, a rule of Lemma 4.7 that is broken. By Lemma 4.7, $R_{5}$ is never a
subtournament of $D_{k}$ for $k\geq 1$. Thus there exists a tournament with a
backedge graph that is a forest such that there are tournaments of clique
number $2$ and arbitrarily large dichromatic number not containing it,
contradicting Conjecture 4.1. ∎

##  5 Conclusion and future works

The main problem that remains open is the following conjecture:

######  Conjecture 5.1.

$2$-DIOMEGA-ORDERING is NP-complete.

A way of attacking this problem could be to see it as a problem on strings.
For example, let us consider the following problem:

PERMUTATION-AVOIDING-SMALL-SUBWORDS

Input: A finite set $\Sigma$, and $S\subseteq\Sigma^{\leq 3}$.

Output: Does there exist a permutation $P$ of $\Sigma$ such that no $w\in S$
is a subsequence of $P$?

Given a tournament $T$, one can consider the instance with $\Sigma=V(T)$ and
$S=\\{wvu\mid uv,vw,uw\in A(T)\\}$. Then, a permutations $P$ of $\Sigma$ such
that no $w\in S$ is a subsequence of $P$ are exactly orderings $\prec$ of
$V(T)$ with $\omega(T^{\prec})=2$. Thus if PERMUTATION-AVOIDING-SMALL-SUBWORDS
was solvable in polynomial time, so would be $2$-DIOMEGA-ORDERING.

Unfortunately, one can prove that PERMUTATION-AVOIDING-SMALL-SUBWORDS.
However, one could study slight variations of this problem: for example, we
can assume that if $abc,dbe\in S$ then $abe,dbc\in S$.

Another problem that is mentioned by Nguyen, Scott and Seymour in [11] is the
question of whether $k$-DIOMEGA-ORDERING is in co-NP. This remains open.

While Conjecture 4.1 is now disproved, one could ask which tournaments are
such that the class of tournaments not containing them is
$\operatorname{\overrightarrow{\chi}}$-bounded: we could not find other
counterexamples on $5$ vertices.

#### Acknowledgements

I would like to thank Pierre Aboulker and Pierre Charbit for the precious
discussion that led to considering whether I could modify the construction of
Lemma 3.3 to disprove Conjecture 4.1. I would also like to thank Louis Jachiet
for the idea of the proof that PERMUTATION-AVOIDING-SMALL-SUBWORDS is NP-
complete.

## References

  * [1] Pierre Aboulker, Guillaume Aubian, Pierre Charbit, and Raul Lopes.  Clique number of tournaments, 2023.
  * [2] Jørgen Bang-Jensen and Gregory Gutin.  Classes of Directed Graphs.  Springer Publishing Company, Incorporated, 1st edition, 2018.
  * [3] J.A. Bondy and U.S.R Murty.  Graph Theory.  Springer Publishing Company, Incorporated, 1st edition, 2008.
  * [4] William H. E. Day and David Sankoff.  Computational complexity of inferring phylogenies by compatibility.  Systematic Zoology, 35(2):224–229, 1986.
  * [5] Reinhard Diestel.  Graph Theory (Graduate Texts in Mathematics).  Springer, 2005.
  * [6] P. Erdös.  Graph theory and probability.  Canadian Journal of Mathematics, 11:34–38, 1959.
  * [7] Ilker Hamzaoglu and Janak H. Patel.  Test set compaction algorithms for combinational circuits.  In Proceedings of the 1998 IEEE/ACM International Conference on Computer-Aided Design, ICCAD ’98, page 283–289, New York, NY, USA, 1998. Association for Computing Machinery.
  * [8] Richard M. Karp.  Reducibility among Combinatorial Problems, pages 85–103.  Springer US, Boston, MA, 1972.
  * [9] B. Mohar.  circular colourings of edge-weighted graphs.  Journal of Graph Theory, 43:107–116, 2003.
  * [10] V Neumann-Lara.  The dichromatic number of a digraph.  Journal of Combinatorial Theory, Series B, 33(3):265–270, 1982\.
  * [11] Tung Nguyen, Alex Scott, and Paul Seymour.  Some results and problems on tournament structure, 2023.
  * [12] Nicholas Rhodes, Peter Willett, Alain Calvet, James B. Dunbar, and Christine Humblet.  Clip: Similarity searching of 3d databases using clique detection.  Journal of Chemical Information and Computer Sciences, 43(2):443–448, 2003.  PMID: 12653507.
  * [13] Alex Scott and Paul Seymour.  A survey of $\chi$-boundedness.  Journal of Graph Theory, 95, 08 2020.
  * [14] A. A. Zykov.  On some properties of linear complexes.  Mat. Sb. (N.S.), 24(66):163–188, 1949.