# Heroes in oriented complete multipartite graphs

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.  Pierre Charbit  Université de Paris, CNRS, IRIF, F-75006, Paris,
France.

###### Abstract

The dichromatic number of a digraph is the minimum size of a partition of its
vertices into acyclic induced subgraphs. Given a class of digraphs
$\mathcal{C}$, a digraph $H$ is a hero in $\mathcal{C}$ if $H$-free digraphs
of $\mathcal{C}$ have bounded dichromatic number. In a seminal paper, Berger
at al. give a simple characterization of all heroes in tournaments. In this
paper, we give a simple proof that heroes in quasi-transitive oriented graphs
are the same as heroes in tournaments. We also prove that it is not the case
in the class of oriented multipartite graphs, disproving a conjecture of
Aboulker, Charbit and Naserasr. We also give a full characterisation of heroes
in oriented complete multipartite graphs up to the status of a single
tournament on $6$ vertices.

##  1 Introduction

###  1.1 Definitions and notations

In this paper, we only consider _directed graphs_ (_digraphs_ in short) with
no digons (a cycle on two vertices), loops nor multi-arcs. Let $G$ be a
digraph. We denote by $V(G)$ its set of vertices and by $A(G)$ its set of
arcs. For a vertex $x$ of $G$, we denote by $x^{+}$ (resp. $x^{-}$, $x^{o}$)
the set of its out-neighbours (resp. in-neighbours, non-neighbours). For a
given set of vertices $X\subseteq V$, we denote by $G[X]$ the subgraph of $G$
induced by $X$.

For two disjoint set of vertices $X,Y$, we write $X\Rightarrow Y$ to say that
for every $x\in X$ and for every $y\in Y$, $xy\in A(G)$, 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$.

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 two tournaments $H_{1}$ and $H_{2}$, we
denote by $\Delta(1,H_{1},H_{2})$ the tournament obtained from pairwise
disjoint copies of $H_{1}$ and $H_{2}$ plus a vertex $x$, and all arcs from
$x$ to the copy of $H_{1}$, all arcs from the copy of $H_{1}$ to the copy of
$H_{2}$, and all arcs from the copy of $H_{2}$ to $x$. When $\ell$ and $k$ are
integers, we write $\Delta(1,k,H)$ for $\Delta(1,TT_{k},H)$ and
$\Delta(1,\ell,k)$ for $\Delta(1,TT_{\ell},TT_{k})$. The tournament
$\Delta(1,1,1)$ is also denoted by $C_{3}$ and called a _directed triangle_.

A _$k$ -dicolouring_ of $G$ is a partition of $V(G)$ into $k$ sets
$V_{1},\dots,V_{k}$ such that $G[V_{i}]$ is acyclic for $i=1,\dots,k$. The
_dichromatic number_ of $G$, denoted by
$\operatorname{\overrightarrow{\chi}}(G)$ and introduced by Neuman-Lara [13]
is the minimum integer $k$ such that $G$ admits a $k$-dicolouring. We will
sometimes extend $\operatorname{\overrightarrow{\chi}}$ to subsets of
vertices, using $\operatorname{\overrightarrow{\chi}}(X)$ to mean
$\operatorname{\overrightarrow{\chi}}(G[X])$ where $X\subseteq V$.

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. We denote by $Forb_{ind}(\mathcal{H})$ the class of
$\mathcal{H}$-free digraphs. Given a class of digraphs $\mathcal{C}$, a
digraph $H$ is a _hero_ in $\mathcal{C}$ if every $H$-free digraph in
$\mathcal{C}$ has bounded dichromatic number.

We denote by $\overrightarrow{P}_{3}$ the directed path on $3$ vertices. An
_oriented complete multipartite graph_ is an orientation of a complete
multipartite graph. Given two digraphs $G_{1}$ and $G_{2}$, $G_{1}+G_{2}$ is
the disjoint union of $G_{1}$ and $G_{2}$. We denote by $K_{1}$ the unique
digraph on $1$ vertex. Observe that oriented complete multipartite graphs are
precisely the digraphs in $Forb_{ind}(K_{1}+TT_{2})$.

The main goal of this paper is to identify heroes in oriented complete
multipartite graphs.

###  1.2 Context and results

In a seminal paper, Berger et al. [7] characterized heroes in tournaments:

######  Theorem 1.1 (Berger et al. [7]).

A digraph $H$ is a hero in tournaments if and only if:

  * •

$H=K_{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^{\prime}$ is a hero in tournaments.

Observe that if a class of digraphs $\mathcal{C}$ contains all tournaments,
then a hero in $\mathcal{C}$ must be a hero in tournaments. In [3], it is
conjectured that heroes in oriented complete multipartite graphs are the same
as heroes in tournaments (actually a wider conjecture is proposed, see Section
5). We disprove this conjecture by showing the following:

######  Theorem 1.2.

The digraphs $\Delta(1,2,C_{3})$, $\Delta(1,C_{3},2)$, $\Delta(1,2,3)$ and
$\Delta(1,3,2)$ are not heroes in tournaments.

On the positive side, we prove that:

######  Theorem 1.3.

A digraph $H$ is a hero in oriented complete multipartite graphs if:

  * •

$H=K_{1}$,

  * •

$H=H_{1}\Rightarrow H_{2}$, where $H_{1}$ and $H_{2}$ are heroes in oriented
complete multipartite graphs, or

  * •

$H=\Delta(1,1,H_{1})$ where $H_{1}$ is a hero in oriented complete
multipartite graphs.

Observe that the second bullet of the theorem above implies that a digraph is
a hero in oriented complete multipartite graphs if and only if  each of its
strong connected components are. Indeed, the only if part of the assertion
holds because a subgraph of a hero in any class is a hero in this class.

Since a hero in oriented complete multipartite graphs must be a hero in
tournaments, Theorem 1.1, Theorem 1.2 and Theorem 1.3 imply that, to get a
full characterization of heroes in oriented complete multipartite graphs, it
suffices to decide whether $\Delta(1,2,2)$ is a hero in oriented complete
multipartite graphs or not. If it is not, then heroes in oriented complete
multipartite graphs are precisely the ones described in Theorem 1.3. If it is,
then a digraph $H$ is a hero in oriented complete multipartite graphs if and
only if:

  * •

$H=K_{1}$ or $H=\Delta(1,2,2)$,

  * •

$H=H_{1}\Rightarrow H_{2}$, where $H_{1}$ and $H_{2}$ are heroes in oriented
complete multipartite graphs, or

  * •

$H=\Delta(1,1,H_{1})$ where $H_{1}$ is a hero in oriented complete
multipartite graphs.

######  Question 1.4.

Is $\Delta(1,2,2)$ a hero in oriented complete multipartite graphs?

A digraph $G$ is _quasi-transitive_ if for every triple of vertices $x,y,z$,
if $xy,yz\in A(G)$, then $xz\in A(G)$ or $zx\in A(G)$. Observe that the class
of quasi-transitive digraphs is precisely
$Forb_{ind}(\overrightarrow{P}_{3})$. Our last result is:

######  Theorem 1.5.

Heroes in quasi-transitive digraphs are the same as heroes in tournaments.

Organisation of the paper: We prove in Section 2 that $\Delta(1,2,C_{3})$,
$\Delta(1,C_{3},2)$, $\Delta(1,2,3)$, $\Delta(1,3,2)$ are not heroes in
oriented complete multipartite graphs. We prove in Subsection 3.1 that if
$H_{1}$ and $H_{2}$ are heroes in oriented complete multipartite graphs, then
so is $H_{1}\Rightarrow H_{2}$ and in subsection 3.2 that if $H$ is a hero in
oriented complete multipartite graphs, then so is $\Delta(1,1,H)$. We give
some insight about whether $\Delta(1,2,2)$ should be a hero or not in oriented
complete multipartite graphs in Section 4 and finally, we prove Theorem 1.5,
detail related results and propose some leads for further works in Section 5.

##  2 Digraphs that are not heroes in oriented complete multipartite graphs

The goal of this section is to prove that $\Delta(1,2,C_{3})$,
$\Delta(1,C_{3},2)$, $\Delta(1,2,3)$ and $\Delta(1,3,2)$ are not heroes in
oriented complete multipartite graphs. Since reversing all arcs of a
$\Delta(1,2,C_{3})$-free oriented complete multipartite graph results in a
$\Delta(1,C_{3},2)$-free oriented complete multipartite graph and does not
change the dichromatic number, if $\Delta(1,2,C_{3})$ is not a hero in
oriented complete multipartite graphs then $\Delta(1,C_{3},2)$ is not either.
Similarly, if $\Delta(1,2,3)$ is not a hero in oriented complete multipartite
graphs then $\Delta(1,3,2)$ is not either. Hence, it is enough to prove that
$\Delta(1,2,C_{3})$ nor $\Delta(1,2,3)$ are heroes in oriented complete
multipartite graphs. This is implied by the existence of
$\\{\Delta(1,2,C_{3}),\Delta(1,2,3)\\}$-free oriented complete multipartite
graphs with arbitrarily large dichromatic number. The rest of this section is
dedicated to the description of such digraphs.

A _feedback arc set_ of a given digraph $G$ is a set of arcs $F$ of $G$ such
that their deletion from $G$ yields an acylic digraph. The idea of the
construction comes from the fact that a feedback arc set of
$\Delta(1,2,C_{3})$ or of $\Delta(1,2,3)$ must induce a digraph with at least
one vertex of in- or out-degree at least $2$. We then describe an oriented
complete multipartite graph with large dichromatic number in which every
subtournament has a feedback arc set inducing disjoint directed paths,
implying that it does not contain $\Delta(1,2,C_{3})$ nor $\Delta(1,2,3)$ by
the fact above.

Given an undirected graph $H$, a _$k$ -colouring_ of $H$ is a partition of
$V(G)$ into $k$ independent sets. The _chromatic number_ of $H$ is the minimum
$k$ such that $H$ is $k$-colourable. Let $G$ be a digraph. We denote by
$\chi(G)$ the chromatic number of the underlying graph of $G$. The
(undirected) _line graph_ of $G$ is denoted by $L(G)$ and defined as follows:
its vertex set is $A(G)$, and two of its vertices vertices $ab,cd\in A(G)$ are
adjacent if and only if $b=c$.

Be aware that the next lemma deals with chromatic number and not dichromatic
number. We think it appears for the first time in [9].

######  Lemma 2.1.

[9] For every digraph $G$, we have $\chi(L(G))\geq\log(\chi(G))$.

###### Proof.

Let $G$ be a digraph and assume $L(G)$ admits a $k$-colouring. Observe that a
colouring of $L(G)$ is the same as a colouring of the arcs of $G$ in such a
way that no $\overrightarrow{P}_{3}$ is monochromatic. Consider the following
colouring of $G$: for each $v\in V(G)$, colour $v$ with the set of colours
received be the arcs entering in $v$. This is a $2^{k}$-colouring of $G$
because the colouring of $A(G)$ does not have monochromatic
$\overrightarrow{P}_{3}$. ∎

Let $s\geq 3$ be an integer and let us describe the graph $L(L(TT_{s}))$.
Assuming the vertices of $TT_{s}$ are numbered $v_{1},\dots,v_{s}$ in the
topological ordering (that is, for all $1\leq i<j\leq s$, we have
$v_{i}v_{j}\in A(T)$), for any $i<j<k$, $\\{v_{i},v_{j},v_{k}\\}$ induces a
$\overrightarrow{P}_{3}$ in $TT_{s}$. This way, we get a natural name for the
vertices of $L(L(TT_{s}))$, namely
$V(L(L(TT_{s})))=\\{(v_{i},v_{j},v_{k})\mid\text{ for every }i<j<k\\}$.
Moreover, edges of $L(L(TT_{s}))$ are of the form
$(v_{i},v_{j},v_{k})(v_{j},v_{k},v_{\ell})$ for every $i<j<k<\ell$. For $2\leq
j\leq s-1$, set $V_{j}=\\{(v_{i},v_{j},v_{k})\\}:i<j<k\\}$. So $V_{j}$’s
partition the vertices of $L(L(TT_{s}))$ into stable sets.

We now define the digraph $D_{s}$ from $L(L(TT_{s}))$ as follows. The vertices
of $D_{s}$ are the same as the vertices of $L(L(TT_{s}))$ and $D_{s}$ is an
oriented complete multipartite graph with parts $(V_{2},V_{3},\dots,V_{s-1})$
and we orient the arcs as follow: given $j<k$, the edges of $L(L(TT_{s}))$ are
oriented from $V_{j}$ to $V_{k}$ and all the other arcs are oriented from
$V_{k}$ to $V_{j}$. This complete the description of $D_{s}$.

The arcs $v_{i}v_{j}$ such that $i<j$ are called the _forward arcs_ of
$D_{s}$, and the other arcs the _backward arcs_ of $D_{s}$. Observe that the
underlying graph of the graphs induced by the forward arcs of $D_{s}$ is
$L(L(TT_{s}))$.

The following remark is the crucial feature of $D_{s}$.

######  Remark 2.2.

Given a vertex $(v_{i},v_{j},v_{k})$ of $D_{s}$, the forwards arcs going out
$(v_{i},v_{j},v_{k})$ are included in $V_{k}$ and the forward arcs going in
$(v_{i},v_{j},v_{k})$ are included in $V_{i}$.

An _out-star_ (resp. _in-star_) is a connected digraph made of one vertex of
in-degree $0$ (resp. of out-degree $0$) and vertices of in-degree $1$ (resp.
out-degree $1$). Observe that a digraph that does not contain
$\overrightarrow{P}_{3}$ as a subgraph is a disjoint union of in- and out-
stars.

######  Lemma 2.3.

For every integer $s$,
$\operatorname{\overrightarrow{\chi}}(D_{s})\geq\frac{1}{2}\log(\log(s))$.

###### Proof.

Let $V_{2},\dots,V_{s-1}$ be the partition of $D_{s}$ as in the definition.
Recall that $V(D_{s})=\\{(v_{i},v_{j},v_{k}):1\leq i<j<k\leq s\\}$. Denote by
$F_{s}$ the digraph induced by the forward arcs of $D_{s}$. So the underlying
graph of $F_{s}$ is $L(L(TT_{s}))$ and by Lemma 2.1, $\chi(F_{s})\geq
log(log(s))$.

Let $R$ be an acyclic induced subgraph of $D_{s}$. Observe that a directed
path on $3$ vertices in $D_{s}$ using only arcs in $F_{s}$ must be of the form
$(v_{i_{1}},v_{i_{2}},v_{i_{3}})\rightarrow(v_{i_{2}},v_{i_{3}},v_{i_{4}})\rightarrow(v_{i_{3}},v_{i_{4}},v_{i_{5}})$
where $1\leq i_{1}<i_{2}<i_{3}<i_{4}<i_{5}\leq s$ and is thus contained in a
directed triangle of $D_{s}$ (because
$(v_{i_{1}},v_{i_{2}},v_{i_{3}})(v_{i_{3}},v_{i_{4}},v_{i_{5}})$ is not an
edge of $L(L(TT_{s}))$, and thus is not an arc of $F_{s}$, and thus
$(v_{i_{3}},v_{i_{4}},v_{i_{5}})(v_{i_{1}},v_{i_{2}},v_{i_{3}})$ is an arc of
$D_{s}$). Hence, $A(R)\cap A(F_{s})$ does not contain $\overrightarrow{P}_{3}$
as a subgraph and is thus a disjoint union of out- and in-stars. So $A(R)\cap
A(F_{s})$ can be partitioned into two stable sets of $F_{s}$. Hence, a
$t$-dicolouring of $D_{s}$ implies a $2t$-(undirected) colouring of $F_{s}$.
As we have that $\chi(F_{s})\geq log(log(s))$, the result follows. ∎

######  Lemma 2.4.

If $T$ is a tournament contained in $D_{s}$, then $T$ has a feedback arc set
formed by disjoint union of directed paths.

###### Proof.

Let $T$ be a subgraph of $D_{s}$ inducing a tournament. Then each vertex of
$T$ belongs to a distinct $V_{i}$ and thus, by Remark 2.2, the forward arcs of
$D_{s}$ that are in $T$ induce a disjoint union of directed paths (i.e. every
vertex have in- and out-degree at most $1$) and clearly form a feedback arc
set of $T$. ∎

######  Lemma 2.5.

For every $s\geq 1$, $D_{s}$ does not contain $\Delta(1,2,C_{3})$ nor
$\Delta(1,2,3)$.

###### Proof.

Observe that the two digraphs $\Delta(1,2,C_{3})$ and $\Delta(1,2,3)$ only
differ on the orientation of one arc: reversing an arc of the copy of $C_{3}$
in $\Delta(1,2,C_{3})$ leads to $\Delta(1,2,3)$ and reversing an arc of the
copy of $TT_{3}$ in $\Delta(1,2,3)$ leads to $\Delta(1,2,C_{3})$. Our argument
does not make any use of the orientations between the vertices inside this
oriented $K_{3}$. Let $H$ be one of $\Delta(1,2,C_{3})$ or $\Delta(1,2,2)$,
and let $x$ be the vertex in the copy of $K_{1}$, and $y_{1}$ and $y_{2}$ the
vertices in the copy of $TT_{2}$. See Figure 1.

Thanks to Lemma 2.4, it is enough to prove that in every feedback arc set of
$H$, there exists a vertex with in- or out-degree at least $2$. Let $F$ be a
feedback arc set of $H$ and assume for contradiction that it induces a
disjoint union of directed paths. Then both $xy_{1}$ and $xy_{2}$ cannot
belong to $F$. So we may assume without loss of generality that $xy_{1}\notin
F$. But then $F$ must intersect the three disjoint paths of length $2$ that go
from $y_{1}$ to $x$, which necessarily implies that $F$ contains either two
arcs coming out of $y_{1}$ or two arcs coming in $x$. ∎

$x$$y_{1}$$y_{2}$$z_{1}$$z_{2}$$z_{3}$ Figure 1:  whatever the orientations of
blue edges, $D_{s}$ does not contain this tournament and hence does not
contain $\Delta(1,2,C_{3})$ nor $\Delta(1,2,3)$.

By Lemma 2.3 and Lemma 2.5, $\Delta(1,2,C_{3})$ and $\Delta(1,2,3)$ are not
heroes in oriented complete multipartite graphs.

##  3 Heroes in oriented complete multipartite graphs

###  3.1 Strong components

The goal of this subsection is to prove the following:

######  Theorem 3.1.

If $H_{1}$ and $H_{2}$ are heroes in $Forb_{ind}(K_{1}+TT_{2})$, then so is
$H_{1}\Rightarrow H_{2}$.

We actually prove the following stronger result:

######  Theorem 3.2.

Let $H_{1}$, $H_{2}$ and $F$ be digraphs such that $H_{1}\Rightarrow H_{2}$ is
a hero in $Forb_{ind}(F)$ and $H_{1}$ and $H_{2}$ are heroes in
$Forb_{ind}(K_{1}+F)$. Then $H_{1}\Rightarrow H_{2}$ is a hero in
$Forb_{ind}(K_{1}+F)$.

To see that Theorem 3.2 implies Theorem 3.1, take $F=TT_{2}$ and observe that
$Forb_{ind}(TT_{2})$ is the class of digraphs with no arc and thus every
digraph is a hero in $Forb_{ind}(TT_{2})$. We explain why such a stronger
version can be of interest for future works in section 5

Note also that by taking $F=K_{1}$, we have that $Forb_{ind}(F)$ is empty and
that $Forb_{ind}(K_{1}+F)$ is the class of tournaments, so Theorem 3.2 yields
the result of [7] (see (3.1)) stating that $H$ is a hero in tournaments if and
only if all of its strong components are. Then, by induction, we get the same
result for the class of digraphs with bounded independence number, reproving
Theorem 1.4 of [11].

The rest of this subsection is devoted to the proof of Theorem 3.2, which is
inspired but simpler (we got rid of the intricate notion of _$r$ -mountain_)
than the analogous result for tournaments in [7], even though our result is
more general.

We start with a few definitions and notations. First, in order to simplify
statements of the lemmas, we assume $H_{1}$, $H_{2}$ and $F$ are fixed all
along the subsection and are as in the statement of Theorem 3.2. So there
exists constants $c$ and $h$ such that:

  * •

$H_{1}$ and $H_{2}$ have at most $h$ vertices,

  * •

digraphs in $Forb_{ind}(F,H_{1}\Rightarrow H_{2})$ have dichromatic number at
most $c$,

  * •

for $i=1,2$, digraphs in $Forb_{ind}(K_{1}+F,H_{i})$ have dichromatic number
$c$.

If $G$ is a digraph and $uv\in E$, we set $C_{uv}=v^{+}\cap u^{-}$, that is
the of vertices that form a directed triangle with $u$ and $v$. Finally, for
$t\in\mathbb{N}$, we say that a digraph $K$ is a _$t$ -cluster_ if
$\chi(K)\geq t$ and $|V(K)|\leq f(t)$, where $f(t)$ is the function defined
recursively by $f(1)=1$ and $f(t)=1+f(t-1)(1+f(t-1))$.

The structure of the proof is very simple, we prove that digraphs in
$Forb_{ind}(K_{1}+F,H_{1}\Rightarrow H_{2})$ that do not contain a $t$-cluster
for some $t$ has bounded dichromatic number (Lemma 3.3), and then that the
ones that contains a $t$-cluster for some $t$ also have bounded dichromatic
number (Lemma 3.4).

######  Lemma 3.3.

There exists a function $\phi$ such that if $t$ is an integer and $G$ is a
digraph in $Forb_{ind}(K_{1}+F,H_{1}\Rightarrow H_{2})$ which contains no
$t$-cluster as a subgraph, then
$\operatorname{\overrightarrow{\chi}}(G)\leq\phi(c,h,t)$

###### Proof.

We prove this by induction on $t$. For $t=1$ the result is trivial as a
$1$-cluster is simply a vertex. Assume the existence of $\phi(c,h,t-1)$, and
assume $G$ is a digraph in $Forb_{ind}(K_{1}+F,H_{1}\Rightarrow H_{2})$ which
contains no $t$-cluster. Say an arc $uv$ is _heavy_ if $C_{e}$ contains a
$(t-1)$-cluster, and _light_ otherwise. For a vertex $u$ we define
$h(u)=\\{v\in V(G)\mid\text{ $uv$ or $vu$ is a heavy arc}\\}$.

######  Claim 3.3.1.

For any vertex $u$, $h(u)$ contains no $(t-1)$-cluster.

Proof. Assume by contradiction that $K$ is a $(t-1)$-cluster in $h(u)$. By
definition of $h(u)$, for every $v\in V(K)$, there exists a $(t-1)$-cluster
$K_{v}$ in $C_{uv}$ or $C_{vu}$ (depending on which of $uv$ or $vu$ is an
arc). Let $K^{\prime}=\\{u\\}\cup V(K)\cup(\cup_{v\in K}V(K_{v}))$. We claim
that $K^{\prime}$ is a $t$-cluster. First note that the number of vertices of
$K^{\prime}$ is at most $1+f(t-1)+f(t-1)\cdot f(t-1)=f(t)$. We need to prove
that $K^{\prime}$ is not $(t-1)$-colourable, so let us consider for
contradiction a $(t-1)$-colouring of its vertices, and without loss of
generality assume $u$ gets colour $1$. Because $K$ is a $(t-1)$-cluster, some
vertex $v$ in $K$ must also receive colour $1$, and since $K_{v}$ is also a
$(t-1)$-cluster, some vertex $w$ in $K_{v}$ must also receive colour $1$,
which produces a monochromatic directed triangle. So $K^{\prime}$ is indeed a
$t$-cluster, a contradiction. $\blacklozenge$

######  Claim 3.3.2.

For any vertex $u$,
$\min(\operatorname{\overrightarrow{\chi}}(u^{-}),\operatorname{\overrightarrow{\chi}}(u^{+}))\leq(h+1)\cdot(\phi(c,h,t-1)+c)$.

Proof. Let $u\in V(G)$. By the previous claim and the induction hypothesis,
$h(u)$ induces a digraph of dichromatic number at most $\phi(c,h,t-1)$, so it
is enough to prove that one of the sets $u^{-}_{\ell}:=(u^{-}\setminus h(u))$
and $u^{+}_{\ell}:=(u^{+}\setminus h(u))$ induces a digraph with dichromatic
number at most $h\cdot\phi(c,h,t-1)+c\cdot(h+1)$.

If $u^{+}_{\ell}$ induces a $H_{2}$-free digraph, then it has dichromatic
number at most $c<h\cdot\phi(c,h,t-1)+c\cdot(h+1)$, so we can assume that
there exists $V_{2}\subseteq u^{+}_{\ell}$ such that $G[V_{2}]=H_{2}$. We now
partition $u^{-}_{\ell}$ into three sets $A,B,C$, each of which will have
bounded dichromatic number.

Let $A=u^{-}_{\ell}\cap(\cup_{v\in V_{2}}v^{+})=u^{-}_{\ell}\cap(\cup_{v\in
V_{2}}C_{uv})$. For every $v\in V_{2}$, $uv\in E$ is light (because
$V_{2}\subseteq u_{l}^{-}$), so $G[C_{uv}\cap A]$ does not contain a
$(t-1)$-cluster and is thus $\phi(c,h,t-1)$-colourable by induction. Now,
since $H_{2}$ contains at most $h$ vertices, we get
$\operatorname{\overrightarrow{\chi}}(A)\leq h\cdot\phi(c,h,t-1)$.

Let $B=u^{-}_{\ell}\cap(\cup_{v\in V_{2}}v^{0})$. Since $G$ is
$(K_{1}+F,H_{1}\Rightarrow H_{2})$-free, for every $v\in V_{2}$, $v^{0}$ is
$(F,H_{1}\Rightarrow H_{2})$-free and thus
$\operatorname{\overrightarrow{\chi}}(G[v^{0}])\leq c$. Hence,
$\operatorname{\overrightarrow{\chi}}(B)\leq c\cdot h$.

Finally, consider $C=u^{-}_{\ell}\setminus(A\cup B)$. By definition of $A$ and
$B$, we get $C\Rightarrow V_{2}$. Since $G$ is $H_{1}\Rightarrow H_{2}$-free,
$G[C]$ is $H_{1}$-free, and therefore
$\operatorname{\overrightarrow{\chi}}(C)\leq c$.

All together, we get $\operatorname{\overrightarrow{\chi}}(x^{-}_{\ell})\leq
h\cdot\phi(c,h,t-1)+c\cdot(h+1)$ as desired. $\blacklozenge$

By the previous claim, we can partition the set of vertices into the two sets
$V^{-}$ and $V^{+}$ defined by:

$\displaystyle V^{-}=\\{u\in
V\mid\operatorname{\overrightarrow{\chi}}(u^{-})\leq(h+1)\cdot(c+\phi(c,h,t-1))\\}$
$\displaystyle V^{+}=\\{u\in
V\mid\operatorname{\overrightarrow{\chi}}(u^{+})\leq(h+1)\cdot(c+\phi(c,h,t-1))\\}$

If $G[V^{-}]$ is $H_{1}$-free and $G[V^{+}]$ is $H_{2}$-free, then
$\operatorname{\overrightarrow{\chi}}(G)\leq 2c<\phi(c,h,t)$ and we are done.
Assume that there exists $V_{1}\subseteq V^{-}$ such that $G[V_{1}]=H_{1}$
(the case where $V^{+}$ contains an induced copy of $H_{2}$ is symmetrical).

We now partition $V(G)\setminus V_{1}$ into three sets of vertices depending
on their relation with $V_{1}$ and prove that each of these set induces a
digraph with bounded dichromatic number.

Let $A=\bigcup_{v\in V_{1}}v^{-}$. By definition of $V^{-}$ and since
$V_{1}\subseteq V^{-}$, for every $v\in V_{1}$, $v^{-}$ has dichromatic number
at most $(h+1)(c+\phi(c,h,t-1))$, and since $H_{1}$ has $h$ vertices we get
that $\operatorname{\overrightarrow{\chi}}(A)\leq
h\cdot(h+1)\cdot(c+\phi(c,h,t-1))$.

Let $B=\bigcup_{v\in V_{1}}v^{0}$. Since $G$ is $(K_{1}+F,H_{1}\Rightarrow
H_{2})$-free, for every $v\in V_{1}$, $v^{0}$ is $(F,H_{1}\Rightarrow
H_{2})$-free and thus $\operatorname{\overrightarrow{\chi}}(G[v^{0}])\leq c$.
Hence, $\operatorname{\overrightarrow{\chi}}(B)\leq c\cdot h$.

Finally, let $C=V(G)\setminus(A\cup B\cup V_{1})$. By definition of $A$ and
$B$, we have $V_{1}\Rightarrow C$, hence $C$ is $H_{2}$-free and thus
$\operatorname{\overrightarrow{\chi}}(C)\leq c$.

All together, we get that $\operatorname{\overrightarrow{\chi}}(G)\leq
h+h\cdot(h+1)\cdot(c+\phi(c,h,t-1))+ch+c:=\phi(c,h,t)$.

∎

The proof of the theorem will follow from the second lemma below.

######  Lemma 3.4.

If $G\in\mathcal{C}$ contains a $(3c+1)$-cluster, then
$\operatorname{\overrightarrow{\chi}}(G)\leq c\cdot 2^{f(3c+1)+1}$.

###### Proof.

Let $K$ be a $(3c+1)$-cluster in $G$. Assume there exists a vertex $u\in V(G)$
such that $u^{-}\cap V(K)$ is $H_{1}$-free and $u^{+}\cap V(K)$ is
$H_{2}$-free. Since $u^{0}\cap V(K)$ is by assumption $(F,H_{1}\Rightarrow
H_{2})$-free, we get a partition of $V(K)$ into three sets that induce
digraphs with dichromatic number at most $c$, a contradiction (this still
holds if $u\in K$ as we can add it to any of the sets without increasing the
dichromatic number).

So, for every $u\in V(G)$, either $u^{-}\cap V(K)$ contains a copy of $H_{1}$,
or $u^{+}\cap V(K)$ contains a copy of $H_{2}$. Now for every $V_{1}\subseteq
V(K)$ such that $G[V_{1}]$ is isomorphic to $H_{1}$, the set of vertices $u$
such that $V_{1}\subset u^{-}$ is $H_{2}$-free and therefore has dichromatic
number at most $c$. Similarly, for every $V_{2}\subset V(K)$ such that
$G[V_{2}]$ is isomorphic to $H_{2}$, the set of vertices $u$ such that
$V_{2}\subset u^{+}$ is $H_{1}$-free and therefore has dichromatic number at
most $c$. By doing this for every possible copy of $H_{1}$ or $H_{2}$ inside
$V(K)$ we can cover every vertex of $V(G)$. Moreover, the number of subsets of
$V(K)$ that induces a copy of $H_{1}$ (resp. of $H_{2}$) is at most
$2^{f(3c+1)}$. Hence, we get that $\operatorname{\overrightarrow{\chi}}(G)\leq
c\cdot 2^{f(3c+1)+1}$. ∎

###### of Theorem 3.2.

By Lemma 3.3 and Lemma 3.4, we get that every digraph in
$Forb_{ind}(K_{1}+F,H_{1}\Rightarrow H_{2})$ has dichromatic number at most
$\max(\phi(c,h,3c+1),2^{f(3c+1)+1}c)$, which proves Theorem 3.2. ∎

######  Remark 3.5.

Let $K(c,h)$ an integer such that digraphs in $Forb_{ind}(F,H_{1}\Rightarrow
H_{2})$ have dichromatic number at most $K(c,h)$. From the proof above we can
deduce that taking

$K(c,h)=\max((2h\cdot(h+1))^{5c+1},2^{2^{2\cdot 3^{3c+1}}+1}\cdot c)$

works (proving as intermediate steps that for every integer $t$, we can take
$f(t)\leq 2^{2\cdot 3^{t}}$ and $\phi(c,h,t)\leq(2h\cdot(h+1))^{2c+t}$).

###  3.2 Growing a hero

The goal of this subsection is to prove the following theorem:

######  Theorem 3.6.

If $H$ is a hero in oriented complete multipartite graphs, then so is
$\Delta(1,H,1)$.

The next lemma is proved in [7] (see (4.2)) for tournaments but actually holds
for every digraphs.

######  Lemma 3.7.

Let $G$ a digraph and let $(X_{1},\dots,X_{n})$ a partition of $V(G)$. Suppose
that $d$ is an integer such that:

  * •

$\forall\,1\leq i\leq n\ \operatorname{\overrightarrow{\chi}}(X_{i})\leq d$ ,

  * •

$\forall\,1\leq i<j\leq n$ , if there is an arc $uv$ with $u\in X_{j}$ and
$v\in X_{i}$, then $\operatorname{\overrightarrow{\chi}}(X_{i+1}\cup
X_{i+2}\cup\dots\cup X_{j})\leq d$

Then $\operatorname{\overrightarrow{\chi}}(G)\leq 2d$.

###### Proof.

Define a sequence $s_{0}<s_{1}<...<s_{t}=n$ defined recursively as follows:
$s_{0}=0$ and

$s_{k}=\max\\{j>s_{k-1}\mid\operatorname{\overrightarrow{\chi}}(\bigcup_{s_{k-1}<i\leq
j}X_{i})\leq d\\}$

For $k=1\ldots t$, and $Y_{k}=\bigcup_{s_{k-1}<i\leq s_{k}}X_{i}$. By
definition of the sequence $s_{k}$,
$\operatorname{\overrightarrow{\chi}}(Y_{k})\leq d$ for $k=1,\dots,t$ and
$\operatorname{\overrightarrow{\chi}}(Y_{k}\cup X_{s_{k}+1})>d$ for
$k=1,\dots,t-1$, so by the assumption of the lemma, there cannot be an arc
from $Y_{j}$ to $Y_{i}$ whenever $i\leq j-2$. Hence, $\bigcup_{i\ even}Y_{i}$
and $\bigcup_{i\ odd}Y_{i}$ both have dichromatic number at most $d$, and thus
$\operatorname{\overrightarrow{\chi}}(G)\leq 2d$. ∎

The following is an adaptation of (4.4) in [7] with oriented complete
multipartite graphs instead of tournaments (note also that their proof is
concerned with $\Delta(1,k,H)$ while ours is concerned with $\Delta(1,1,H)$).

######  Lemma 3.8.

Let $G$ be a $\Delta(1,1,H)$-free oriented complete multipartite graph given
with a partition $(X_{1},\dots,X_{n})$ of its vertex set $V(G)$. Suppose that
$c$ is an integer such that:

  * •

$H$-free oriented complete multipartite graphs have dichromatic number at most
$r$,

  * •

$\forall\,1\leq i\leq n\ \operatorname{\overrightarrow{\chi}}(X_{i})\leq r$,

  * •

$\forall\,1\leq i\leq n\ \forall v\in X_{i}\
\operatorname{\overrightarrow{\chi}}(v^{+}\cap(X_{1}\cup\dots\cup
X_{i-1}))\leq r$,

  * •

$\forall\,1\leq i\leq n\ \forall v\in X_{i}\
\operatorname{\overrightarrow{\chi}}(v^{-}\cap(X_{i+1}\cup\dots\cup
X_{n}))\leq r$.

Then $\operatorname{\overrightarrow{\chi}}(G)\leq 8r+4$.

###### Proof.

We are going to prove that $G$ satisfies the hypothesis of Lemma 3.7 with
$d=4r+2$, which implies the result. Let $uv$ be an edge such that $u\in X_{j}$
and $v\in X_{i}$ where $1\leq i<j\leq n$. We want to prove that
$\operatorname{\overrightarrow{\chi}}(X_{i+1}\cup X_{i+2}\cup\dots\cup
X_{j})\leq 4r+2$. Let $W=X_{i+1}\cup\dots\cup X_{j-1}$. Let $Q=v^{+}\cap
u^{-}\cap W$. If $Q$ contains a copy of $H$, then together with $u$ and $v$ it
forms a $\Delta(1,H,1)$, a contradiction. So $Q$ is $H$-free and thus is
$r$-colourable. Now, each vertex in $W\setminus Q$ is in $u^{+}\cup v^{-}\cup
u^{o}\cup v^{o}$. By hypothesis,
$\operatorname{\overrightarrow{\chi}}(v^{+}\cap W)$ and
$\operatorname{\overrightarrow{\chi}}(v^{-}\cap W)$ are both $r$-colourable,
and since $G$ is an oriented complete multipartite graph, $u^{o}$ and $v^{o}$
are stable sets. Finally, by hypothesis,
$\operatorname{\overrightarrow{\chi}}(X_{j})\leq r$. All together, we get that
$\operatorname{\overrightarrow{\chi}}(X_{i+1}\cup\dots\cup X_{j})\leq 4r+2$ as
announced.

∎

###### of Theorem 3.6.

Let $H$ be a hero in oriented complete multipartite graphs and let $h=|V(H)|$.
By applying Theorem 3.1 with $H_{1}=H_{2}=H$, we get that $H\Rightarrow H$ is
a hero in oriented complete multipartite graphs. So there exists a constant
$c$ such that every $(H\Rightarrow H)$-free oriented complete multipartite
graphs have dichromatic number at most $c$. Note that it also implies that
every $H$-free oriented complete multipartite graphs have dichromatic number
at most $c$.

Let $G$ be a $\Delta(1,1,H)$-free oriented complete multipartite graph. Set
$r=12c\cdot h^{2}+4c\cdot h+3c+18h$. We are going to prove that
$\operatorname{\overrightarrow{\chi}}(G)\leq 8r+4$ using Lemma 3.7

We say that $J\subseteq V(G)$ is a _$H$ -jewel_ if $G[J]$ is isomorphic to
$H\Rightarrow H$. The important feature about an $H$-jewel $J$ in an oriented
complete multipartite graph is that, for any vertex $x$ not in $J$, either
$x^{+}\cap J$ or $x^{-}\cap J$ contains a copy of $H$, or $x$ has both an in-
and an out-neighbour in $J$. A _$H$ -jewel-chain_ of length $n$ is a sequence
$(J_{1},\dots,J_{n})$ of pairwise disjoint $H$-jewels such that for
$i=1,\dots,n-1$, $J_{i}\Rightarrow J_{i+1}$ , and for every $1\leq i<j\leq n$,
$J_{i}\rightarrow J_{j}$. Both notions of $H$-jewel and $H$-jewel-chain exist
in [7], the ones we give here are slightly different, but are morally similar.

Consider a $H$-jewel-chain $(J_{1},\dots,J_{n})$ of maximum length $n$. Set
$J=J_{1}\cup\dots\cup J_{n}$ and $W=V(G)-J$. To simplify statements, we also
consider sets $J_{i}$ for $i\leq 0$ and $i\geq n+1$, that are assumed to be
empty.

The easy but key properties of an $H$-jewel-chain are stated in the following
claim.

######  Claim 3.8.1.

For every $w\in W$ and $1\leq j\leq n$:

  * •

$w^{+}\cap J_{j}\neq\emptyset\,\Rightarrow\,w^{+}\cap J_{j+1}\neq\emptyset$

  * •

$w^{-}\cap J_{j}\neq\emptyset\,\Rightarrow\,w^{-}\cap J_{j-1}\neq\emptyset$.

Proof. Assume $w^{+}\cap J_{j}\neq\emptyset$. Then since $J_{j}\Rightarrow
J_{j+1}$, it is not possible that $G[w^{-}\cap J_{j+1}]$ contains a copy of
$H$ for it would create a $\Delta(1,H,1)$. Since $G[J_{j+1}]$ is isomorphic to
$H\Rightarrow H$, and since $w$ cannot have a non neighbour in both copies of
$H$ (because $G$ is an oriented complete multipartite graph), this implies
that $w$ has at least one out-neighbour in $J_{j+1}$. The proof of the second
item is identical up to reversal of the arcs. $\blacklozenge$

For every $w\in W$, let $c(w)$ be the smallest integer $j$ such that
$w^{+}\cap J_{j}\neq\emptyset$ if such an integer exists, and $c(w)=n+1$ if no
such integer exists. For $j=1,\dots,n+1$, set $W_{j}=\\{w:c(w)=j\\}$ and
$X_{j}=J_{j}\cup W_{j}$. Note that, by definition of the $W_{j}$’s, if $w\in
W_{j}$, then $J_{i}\rightarrow w$ for every $i\leq j-1$.

######  Claim 3.8.2.

$\operatorname{\overrightarrow{\chi}}(X_{j})\leq 4c\cdot h^{2}+c+6h$ for
$j=1,\dots,n+1$.

Proof. Let $1\leq j\leq n+1$. We have
$\operatorname{\overrightarrow{\chi}}(J_{j})\leq|J_{j}|\leq 2h$.

For each pair of vertices $a\in J_{j}$ and $b\in J_{j+1}$, set $A_{ab}=\\{w\in
W_{j}:bw,\,wa\in A(G)\\}$. Since $ab\in A(G)$ (because $J_{j}\Rightarrow
J_{j+1}$), and $G$ is $\Delta(1,H,1)$-free, $A_{ab}$ must be $H$-free and thus
is $c$-colourable for every choice of $a$ and $b$. Setting $A=\bigcup_{a,b\in
J_{j}\times J_{j+1}}A_{ab}$, we get that
$\operatorname{\overrightarrow{\chi}}(A)\leq 4h^{2}\cdot c$. Moreover, since
every vertex in $W_{j}$ has an out-neighbour in $J_{j}$, we have $A=\\{w\in
W_{j}:w^{-}\cap J_{j+1}\neq\emptyset\\}$

Let $B=\\{w\in W_{j}:w^{o}\cap J_{j-1}\neq\emptyset\text{ or }w^{o}\cap
J_{j+1}\neq\emptyset\\}$, in other words $B$ is the set of vertices in $W_{j}$
with at least one non-neighbour in $J_{j-1}$ or $J_{j+1}$. Since $G$ is an
oriented complete multipartite graph, we have
$\operatorname{\overrightarrow{\chi}}(B)\leq|J_{j-1}|+|J_{j+1}|\leq 4h$.

Let $C=W_{j}\setminus(A\cup B)$. By definition of $W_{j}$, for every $i\leq
j-1$, $J_{i}\rightarrow C$. Since $C$ is disjoint from $A$, we have
$C\rightarrow J_{j+1}$, and thus, by claim 3.8.1 (second bullet), we have
$C\rightarrow J_{k}$ for every $k\geq j+1$. Finally, since $C$ is disjoint
from $B$, we have furthermore $J_{j-1}\Rightarrow C$ and $C\Rightarrow
J_{j+1}$. Now, if $C$ contains a $H$-jewel-chain
$(J^{\prime}_{1},J^{\prime}_{2})$ of length $2$, then
$(J_{1},\dots,J_{j-1},J^{\prime}_{1},J^{\prime}_{2},J_{j+1},\dots,J_{n})$ is a
$H$-jewel-chain of size $n+1$, contradicting the maximality of $n$. Hence, $C$
does not contain a jewel-chain of size $2$ and thus
$\operatorname{\overrightarrow{\chi}}(C)\leq c$.

All together, we get that $\operatorname{\overrightarrow{\chi}}(X_{j})\leq
4c\cdot h^{2}+c+6h$. $\blacklozenge$

######  Claim 3.8.3.

For $j=1,\dots,n$ and for every $u\in J_{j}$,

  * •

$\operatorname{\overrightarrow{\chi}}\big{(}u^{+}\cap(X_{1}\cup\dots\cup
X_{j-1})\big{)}\leq 4c\cdot h^{2}+2c\cdot h+c+6h$, and

  * •

$u^{-}\cap(X_{j+1}\cup\dots\cup X_{n+1})=\emptyset$

Proof. Let $1\leq j\leq n$ and let $u\in J_{j}$. We first prove the first
bullet. By definition of an $H$-jewel-chain, $u$ has no out-neighbor in any
$J_{i}$ for $i\leq j-1$ and by Claim 3.8.2,
$\operatorname{\overrightarrow{\chi}}(X_{j-1})\leq 4c\cdot h^{2}+c+6h$. So it
is enough to prove that $A=u^{+}\cap(W_{1}\cup\dots\cup W_{j-2})$ has
dichromatic number at most $2c\cdot h$. By Claim 3.8.1, every vertex of
$W_{1}\cup\dots\cup W_{j-2}$ has an out-neighbour in $J_{j-1}$. Moreover, for
every $v\in J_{j-1}$, we have $vu\in A(G)$ (because $J_{j-1}\Rightarrow
J_{j}$) and $v^{-}\cap A$ is $H$-free, for otherwise a copy of $H$ in
$v^{-}\cap A$ would form, together with $v$ and $u$, a $\Delta(1,H,1)$. So
$\operatorname{\overrightarrow{\chi}}(A)\leq|J_{j}|\cdot c=2c\cdot h$ as
needed.

To prove the second bullet, observe that for every $k\geq j+1$, since $J$ is a
jewel-chain, $u$ has no in-neighbour in $J_{k}$ and by definition of $W_{k}$,
$u$ has no in-neighbour in $W_{k}$. $\blacklozenge$

######  Claim 3.8.4.

For $j=1,\dots,n+1$ and for every $w\in W_{j}$,

  * •

$\operatorname{\overrightarrow{\chi}}\big{(}w^{+}\cap(X_{1}\cup\dots\cup
X_{j-1})\big{)}<8c\cdot h^{2}+2c\cdot h+2c+12h$, and

  * •

$\operatorname{\overrightarrow{\chi}}\big{(}w^{-}\cap(X_{j+1}\cup\dots\cup
X_{n+1})\big{)}\leq 8c\cdot h^{2}+2c+12h$

Proof. Let $1\leq j\leq n+1$ and let $w\in W_{j}$.

We first prove the first bullet. By definition of $W_{j}$, $w$ has no out-
neighbor in any of the $J_{i}$ for $i\leq j-1$ and by Claim 3.8.2
$\operatorname{\overrightarrow{\chi}}(W_{j-2}\cup W_{j-1})\leq 8c\cdot
h^{2}+2c+12h$. So it is enough to prove that
$A=w^{+}\cap\big{(}W_{1}\cup\dots\cup W_{j-3}\big{)}$ has dichromatic number
at most $2c\cdot h$. Again by definition of $W_{j}$ we have
$J_{j-2}\rightarrow w$ and $J_{j-1}\rightarrow w$, and since $J_{j-2}\cup
J_{j-1}$ induces a tournament and $G$ is $(K_{1}+TT_{2})$-free, $w$ has at
most one non-neighbour in $J_{j-2}\cup J_{j-1}$. So there exists
$s\in\\{j-2,j-1\\}$ such that $J_{s}\Rightarrow w$. For every $v\in J_{s}$, if
$v^{-}\cap A$ contains a copy of $H$, then it would form, together with $v$
and $w$, a $\Delta(1,1,H)$, a contradiction. So, for every $v\in J_{s}$,
$v^{-}\cap A$ is $H$-free and is thus $c$-colourable. Finally, by claim 3.8.1
every vertex in $A$ has an out-neighbour in $J_{s}$. So we get that
$\operatorname{\overrightarrow{\chi}}(A)\leq 2c\cdot h$.

We now prove the second bullet. If $j\geq n-1$, then by claim 3.8.2
$\operatorname{\overrightarrow{\chi}}(X_{n}\cup X_{n+1})\leq 8c\cdot
h^{2}+2c+12h$ and we are done. So we may assume that $j\leq n-2$ By claim
3.8.2, $\operatorname{\overrightarrow{\chi}}(X_{j+1})\leq 4c\cdot h^{2}+8h+c$,
so we may assume that $j\leq n-2$. Set $B=w^{-}\cap\big{(}X_{j+2}\cup\dots\cup
X_{n+1}\big{)}$. By Claim 3.8.1, $w$ has an out-neighbour $v\in J_{j+1}$. For
$i\geq j+2$, by definition of an $H$-jewel-chain, $v\rightarrow J_{i}$ and by
definition of $W_{i}$, $v\rightarrow W_{i}$. So $v\rightarrow B$ and since $G$
is an oriented complete multipartite graph $B\setminus(v^{+}\cap B)$ is a
stable set. Now, $v^{+}\cap B$ is $H$-free, as otherwise $G$ would contain an
$\Delta(1,H,1)$. So $v^{+}\cap B$ is $c$-colourable and thus
$\operatorname{\overrightarrow{\chi}}(B)\leq c+1$ and thus
$\operatorname{\overrightarrow{\chi}}\big{(}w^{-}\cap(X_{j+1}\cup\dots\cup
X_{n+1})\big{)}\leq\operatorname{\overrightarrow{\chi}}(X_{j+1})+c+1\leq
4c\cdot h^{2}+3c+6h+1$ by claim 3.8.2. $\blacklozenge$

By Claims 3.8.2, 3.8.3 and 3.8.4, we can apply Lemma 3.7 with $r=12c\cdot
h^{2}+4c\cdot h+3c+18h$ to get $\operatorname{\overrightarrow{\chi}}(G)\leq
8r+4$. ∎

##  4 Some insights about $\Delta(1,2,2)$-free oriented complete multipartite
graphs

In [4] Axenovich et al. tried to characterize patterns that must appear in
every ordering of the vertices of graphs with large chromatic number. An
(undirected) graph $G$ is (what we call) _non-interlaced_ if there exists an
ordering $(x_{1},\dots,x_{n})$ on its vertices such that for every
$i_{1}<i_{2}<i_{3}<i_{4}<i_{5}$,
$\\{x_{i_{1}}x_{i_{3}},x_{i_{3}}x_{i_{5}},x_{i_{2}}x_{i_{4}}\\}\subsetneq
E(G)$. See Figure 2. They left as an open question whether non-interlaced
graphs have bounded chromatic number or not. The goal of this section is to
show that if $\Delta(1,2,2)$ is a hero in oriented complete multipartite
graphs, then non-interlaced graphs have bounded chromatic number. See Theorem
4.2.

$x_{i_{1}}$$x_{i_{2}}$$x_{i_{3}}$$x_{i_{4}}$$x_{i_{5}}$ Figure 2:  A graph is
non-interlaced if there is an ordering of its vertices that avoids the above
pattern as a subgraph.

Given an oriented complete multipartite graph D together with an ordering
$(V_{1},\dots,V_{n})$ on its parts, the arcs going from $V_{i}$ to $V_{j}$ are
called _forward arcs_ if $i<j$, and _backward arcs_ otherwise. Moreover, given
$i<j$, we say that $u<v$ for every $u\in V_{i}$ and every $v\in V_{j}$.
Finally, we say that an oriented complete multipartite graph $D$ is _flat_ if
it admits an ordering $(V_{1},\dots,V_{n})$ on its parts such that for every
vertex $v$ of $D$, the backward arcs going out from (resp. going in) $v$ are
included in a single part of $D$. Such an ordering is called a _flat
ordering_.

$v_{3}$$v_{1}$$v_{4}$$v_{2}$$v_{5}$ (a) $\Delta(1,2,2)$

$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$ (b) A drawing of $\Delta(1,2,2)$ where the
backward arcs (coloured in red) induce the forbidden pattern of non-interlaced
graphs.

Figure 3: Two drawings of $\Delta(1,2,2)$.

######  Lemma 4.1.

Let $D$ be an oriented complete multipartite graph with parts
$V_{1},\dots,V_{n}$ where $(V_{1},\dots,V_{n})$ is a flat ordering. If $D$
contains a copy of $\Delta(1,2,2)$, naming its vertices as in Figure 3, we
must have $v_{1}<v_{2}<v_{3}<v_{4}<v_{5}$.

###### Proof.

Suppose that $D$ contains a copy of $\Delta(1,2,2)$ and name its vertices as
in Figure 3. Since $\Delta(1,2,2)$ is a tournament, $v_{i}$’s are contained in
pairwise distinct parts of $D$, and thus are totally ordered. Since
$(V_{1},\dots,V_{n})$ is a flat ordering, the smallest vertex among
$\\{v_{1},v_{2},v_{3},v_{4},v_{5}\\}$ must have in-degree at most $1$ in
$\Delta(1,2,2)$, and hence must be $v_{1}$. Similarly, since $v_{5}$ is the
only vertex with out-degree $1$ in $\Delta(1,2,2)$, $v_{5}$ must be the
largest of the $v_{i}$. If $v_{3}<v_{2}$, then $v_{3}<v_{2}<v_{5}$ and the
arcs $v_{2}v_{3}$ and $v_{5}v_{3}$ contradicts the fact that
$(V_{1},\dots,V_{n})$ is a flat ordering, so $v_{2}<v_{3}$. Similarly, if
$v_{4}<v_{3}$, then $v_{4}<v_{3}<v_{5}$ and the arcs $v_{3}v_{4}$ and
$v_{5}v_{3}$ contradicts the fact that $(V_{1},\dots,V_{n})$ is a flat
ordering, so $v_{3}<v_{4}$ and thus $v_{1}<v_{2}<v_{3}<v_{4}<v_{5}$. ∎

######  Theorem 4.2.

If $\Delta(1,2,2)$ is a hero in oriented complete multipartite graphs, then
every non-interlaced graph has bounded chromatic number.

###### Proof.

Assume that $\Delta(1,2,2)$ is a hero in oriented complete multipartite
graphs. Let $\mathcal{F}$ be the class of flat $\Delta(1,2,2)$-free oriented
complete multipartite graphs. Since $\Delta(1,2,2)$ is a hero in oriented
complete multipartite graphs, there exists a constant $r$ such that every
digraph in $\mathcal{F}$ has dichromatic number at most $r$. Let
$R\in\mathcal{F}$ such that $\operatorname{\overrightarrow{\chi}}(R)=r$ and
recall that $R$ has a flat ordering. We are going to prove that every non-
interlaced graph has chromatic number at most $2^{2^{r}}$.

Let $G$ be a non-interlaced (undirected) graph and $(x_{1},\dots,x_{n})$ the
ordering on $V(G)$ given by the definition of non-interlaced graphs (that is
an ordering that avoids the patter in Figure 2). We construct an oriented
complete multipartite graph $D^{\prime}(G)$ as follow. For each $x_{i}$, we
create a stable set $V_{i}$ in $D^{\prime}(G)$ of size $n^{2}$ and we assume
the vertices of $V_{i}$ are organised as an $n\times n$ matrix. The $V_{i}$
are the parts of $D^{\prime}(G)$. Let us now explain how we orient the arcs.
Given $i<j$, if $x_{i}x_{j}\in E(G)$, we orient the arcs from each vertex of
the $i^{th}$ line of $V_{j}$ to each vertex of the $j^{th}$ column of $V_{i}$.
Every other arc are oriented from $V_{j}$ to $V_{i}$. This complete the
construction of $D^{\prime}(G)$.

Let $v\in V_{i}$ and assume $v$ is in the $j^{th}$ line and the $k^{th}$
column of $V_{i}$. Then either $x_{j}x_{i}\notin E(G)$ and no backward arcs
goes out from $v$, or $x_{j}x_{i}\in E(G)$ and all backward arcs going out
from $v$ are included in $V_{j}$ (more precisely, they goes from $v$ to the
vertices of the $j^{th}$ column of $V_{j}$). Similarly, either
$x_{k}x_{i}\notin E(G)$ and no backward arc goes in $v$, or $x_{i}x_{k}\in
E(G)$ and all backward arcs going in $v$ are included in $V_{k}$ (more
precisely, they goes from the $i^{th}$ line of $V_{k}$ to $v$). Hence,
$D^{\prime}(G)$ is flat and $(V_{1},\dots,V_{n})$ is a flat ordering of
$D^{\prime}(G)$.

We now construct another oriented complete multipartite graph $D(G)$ from
$D^{\prime}(G)$ by introducing, for $j=1,\dots,n-1$, a copy of $R$ between
$V_{j}$ and $V_{j+1}$ that is seen by all vertices in $\cup_{i\leq j}V_{j}$
and sees all vertices in $\cup_{k\geq i+1}V_{k}$. This complete the
construction of $D(G)$.

It is clear that $D(G)$ is an oriented complete multipartite graph and by
inserting the flat ordering of each copy of $R$ between each consecutive
$V_{j}$, we get a natural ordering of the parts of $D(G)$. In the rest of the
proof, we speak about backward and forward arcs of $D(G)$ with respect to this
ordering.

We are going to prove that $D(G)\in\mathcal{F}$ (so
$\operatorname{\overrightarrow{\chi}}(D(G))\leq r$) and that $\chi(G)\leq
2^{2^{\operatorname{\overrightarrow{\chi}}(D(G))}}$, which together implies
the result.

In order to help in our analysis, we will say that the vertices of $D(G)$ that
comes from $D^{\prime}(G)$ are green.

The following claim is straightforward by construction.

######  Claim 4.2.1.

If $uv$ is a backward arc of $D(G)$, then either both $u$ and $v$ are green,
or $u$ and $v$ are both contained in one of the copies of $R$.

######  Claim 4.2.2.

If $v_{1},v_{2},v_{3},v_{4},v_{5}$ are vertices of $D(G)$ such that
$v_{1}<v_{2}<v_{3}<v_{4}<v_{5}$, then
$\\{v_{3}v_{1},v_{5}v_{3},v_{4}v_{2}\\}\subsetneq A(D(G))$.

Proof. For otherwise $\\{x_{1}x_{3},x_{3}x_{5},x_{2}x_{4}\\}\subseteq E(G)$, a
contradiction. $\blacklozenge$

Let us first prove that $D(G)\in\mathcal{F}$. By claim 4.2.1, $D(G)$ is flat
and the ordering we consider is a flat ordering. Assume that $D(G)$ contains a
copy of $\Delta(1,2,2)$ and name its vertices as in Figure 3. By Lemma 4.1, we
have that the $v_{i}$ are in pairwise distinct parts of $D(G)$ and
$v_{1}<v_{2}<v_{3}<v_{4}<v_{5}$. If $v_{3}$ is in a copy of $R$, since
$v_{3}v_{1}$ and $v_{5}v_{3}$ are backward arcs of $D(G)$, we get by claim
4.2.1 that $v_{1}$ and $v_{5}$ are in the same copy of $R$ as $v_{3}$. By
construction, since $v_{1}<v_{2}<v_{3}<v_{4}<v_{5}$, we get that $v_{2}$ and
$v_{4}$ are also in this same copy of $R$, a contradiction with the fact that
$R$ is $\Delta(1,2,2)$-free. So we may assume that $v_{3}$ is green, and so
are $v_{1}$ and $v_{5}$ by claim 4.2.1. Now, if $v_{2}$ is in a copy of $R$,
then by claim 4.2.1 $v_{4}$ is in the same copy of $R$, and since
$v_{2}<v_{3}<v_{4}$, $v_{3}$ must be in that same copy of $R$, a contradiction
with the fact that $v_{3}$ is green. Hence, $v_{2}$ is green and by claim
4.2.1 so is $v_{4}$. Thus, every $v_{i}$ is green, a contradiction to claim
4.2.2. This proves that $D(G)\in\mathcal{F}$.

Since $D(G)$ contains copies of $R$, it has dichromatic number at least $r$,
and since $D(G)\in\mathcal{F}$, we get that
$\operatorname{\overrightarrow{\chi}}(D(G))=r$. Consider a dicolouring
$\overrightarrow{\varphi}$ of $D(G)$ with $r$ colours We define a coloring
$\varphi$ of $V(G)$ from $\overrightarrow{\varphi}$ as follows: for
$i=1,\dots,n$, $\varphi(v_{i})$ is the set of sets of colours used by each
line of $V_{i}$. This gives us a colouring of $V(G)$ with at most $2^{2^{r}}$
colours. Let us prove that it is a proper colouring of $G$ that is, each
colour class is an independent set.

Assume for contradiction that there exists $x_{i}x_{j}\in E(G)$ such that
$\varphi(x_{i})=\varphi(x_{j})$ and assume without loss of generality that
$i<j$. Let us first prove that $D(G)$ has a monochromatic backward arc.
Consider the set of colours used in the $i^{th}$ line of $V_{j}$. The same set
of colours is used by the vertices of some line of $V_{i}$, say the $k^{th}$.
Now, the $j^{th}$ vertex of the $k^{th}$ line of $V_{i}$ is seen by every
vertex of the $i^{th}$ line of $V_{j}$, which implies the existence of a
monochromatic backward arc as announced. Let $uv$ be this monochromatic
backward arc, with $v\in V_{i}$ and $u\in V_{j}$. Since $i<j$, there is a copy
of $R$ between $V_{i}$ and $V_{j}$. Since
$\operatorname{\overrightarrow{\chi}}(R)=r$, one of the vertex $x$ of $R$ is
coloured with $\overrightarrow{\varphi}(u)$. By construction of $D(G)$, $ux$
and $xv$ are arcs of $D(G)$ and thus $\\{u,x,v\\}$ induces a monochromatic
directed triangle, a contradiction.

∎

##  5 Related and further works

Heroes in orientations of chordal graphs was recently fully characterized in
[2].

A _star_ is an undirected tree with at most one non-leaf vertex. An _oriented
forest_ (resp. _oriented star_) is an orientation of a forest (resp. of a
star). In [3], the authors initiated a systematic study of heroes in
$Forb_{ind}(F)$ for a fixed digraph $F$. We now summarize the known results in
this direction and explain how our results fit in the big picture.

First observe that $K_{1}$ and $TT_{2}$ are heroes in every class of digraphs.
A result in [12] implies that no digraph except for $K_{1}$ and $TT_{2}$ is a
hero in $Forb_{ind}(F)$ whenever the underlying graph of $F$ contains a cycle.
We now distinguish cases depending on whether $F$ is an oriented forest, an
oriented star or a disjoint union of at least two oriented stars.

###  5.1 Heroes in $Forb_{ind}(F)$ when $F$ is an oriented forest

It is proved in [3] that if $F$ is not a disjoint union of oriented stars,
then the only possible heroes in $Forb_{ind}(F)$ are transitive tournaments.
In the same paper the authors venture to conjecture the following (which can
be seen as an oriented analogue of the well-known Gyárfás-Sumner conjecture
[10, 15]):

######  Conjecture 5.1 ([3]).

For every oriented forest $F$, every transitive tournament is a hero in
$Forb_{ind}(F)$.

In [14] it is proved that it is enough to prove the conjecture for trees, the
conjecture have been proved to be true for oriented stars [8].

###  5.2 Heroes in $Forb_{ind}(F)$ when $F$ is an oriented star

When $F$ is an oriented star, it is still possible that heroes in
$Forb_{ind}(F)$ are the same as heroes in tournaments. As said in the previous
subsection, it is proved in [8] that for every oriented star $F$, all
transitive tournaments are heroes in $Forb_{ind}(F)$. The only other known
result so far is concerned with $\overrightarrow{K}_{1,2}$ (the oriented star
on $3$ vertices, with one vertex of out-degree $2$ and two vertices of in-
degree $1$): it is proved in [1, 14] that $K_{1}\Rightarrow C_{3}$ (and thus
$C_{3}$ too) is a hero in $Forb_{ind}(\overrightarrow{K}_{1,2})$. Note that
$\overrightarrow{P}_{3}$ is an oriented star. We now give an easy proof that
all heroes in tournaments are heroes in $Forb_{ind}(\overrightarrow{P}_{3})$.

Recall that a digraph $G$ is _quasi-transitive_ if for every triple of
vertices $x,y,z$, if $xy,yz\in A(G)$, then $xz\in A(G)$ or $zx\in A(G)$ and
observe that the class of quasi-transitive digraphs is precisely
$Forb_{ind}(\overrightarrow{P}_{3})$.

Given two digraphs $G_{1}$ and $H_{1}$ with disjoint vertex sets, a vertex
$u\in G_{1}$, and a digraph $G$, we say that $G$ is obtained by substituting
$H_{1}$ for $u$ in $G_{1}$, provided that the following hold:

  * •

$V(G)=(V(G_{1})\setminus u)\cup V(H_{1})$,

  * •

$G[V(G_{1})\setminus u]=G_{1}\setminus u$,

  * •

$G[V(H_{1})]=H_{1}$

  * •

for all $v\in V(G_{1})\setminus u$ if $v$ sees (resp. is seen by, resp. is
non-adjacent to) $u$ in $G_{1}$, then $v$ sees (resp. is seen by, resp. is
non-adjacent with) every vertex in $V(G_{2})$ in $G$.

Let $\mathcal{T}$ be the class of tournaments and $\mathcal{A}$ the class of
acyclic digraphs. Let $(\mathcal{A}\cup\mathcal{T})^{*}$ be the closure of
$\mathcal{A}\cup\mathcal{T}$ under taking substitution, that is to say
digraphs in $(\mathcal{A}\cup\mathcal{T})^{*}$ are the digraphs obtained from
a vertex by repeatedly substituting vertices by digraphs in
$\mathcal{A}\cup\mathcal{T}$. A classic result of Bang-Jensen and Huang [6]
(see also Proposition 8.3.5 in [5]), implies that quasi-transitive digraphs
are all in $(\mathcal{A}\cup\mathcal{T})^{*}$.

######  Theorem 5.2.

Heroes in $(\mathcal{A}\cup\mathcal{T})^{*}$ are the same as heroes in
tournaments. In particular, heroes in $Forb_{ind}(\overrightarrow{P}_{3})$ are
the same as heroes in tournaments.

###### Proof.

Let $H$ be a hero in tournaments and $c$ be the maximum dichromatic number of
an $H$-free tournament. We prove by induction on the number of vertices that
$H$-free digraphs in $(\mathcal{A}\cup\mathcal{T})^{*}$ are also
$c$-dicolourable. Let $G\in\mathcal{(}\mathcal{A}\cup\mathcal{T})^{*}$ on
$n\geq 2$ vertices and assume that all digraphs in
$\mathcal{(}\mathcal{A}\cup\mathcal{T})^{*}$ on at most $n-1$ vertices are
$c$-dicolourable.

There exist $G_{1},\dots,G_{s}$, $H_{1},\dots,H_{s-1}$ and vertices
$v_{1}\dots,v_{s-1}$ such that the $G_{i}$’s and the $H_{i}$’s are digraphs of
$\mathcal{A}\cup\mathcal{T}$ with at least two vertices, $G_{1}=K_{1}$,
$G_{s}=G$, $v_{i}\in V(G_{i})$ and for $i=1,\dots s-1$,
$G_{i+1}=G_{i}(v_{i}\leftarrow H_{i})$.

If all $H_{i}$ are tournaments, then $G$ is a tournament and is thus
$c$-dicolourable. So we may assume that there exists $1\leq i\leq s-1$ such
that $H_{i}$ is an acyclic digraph. Let $x_{1},\dots,x_{t}$ be the vertices of
$H_{i}$. There exist $t$ digraphs $X_{1},\dots,X_{t}$ in
$\mathcal{(}\mathcal{A}\cup\mathcal{T})^{*}$ such that $G$ is obtained from
$G_{i+1}$ by substituting $x_{1}$ by $X_{1}$, $x_{2}$ by $X_{2}$, $\dots,$
$x_{t}$ by $X_{t}$ and some vertices of
$V(G_{i+1})\setminus\\{x_{1},\dots,x_{t}\\}$ by digraphs in
$(\mathcal{A}\cup\mathcal{T})^{*}$. Note that the order in which these
substitutions are performed does not matter.

Let $X=\cup_{1\leq i\leq t}V(X_{i})$. So $V(G)\setminus X$ can be partitioned
into $3$ sets $S^{+}$, $S^{-}$, $S^{0}$ such that for every $v\in X$, $v$ sees
all vertices of $S^{+}$, is seen by all vertices of $S^{-}$ and is non-
adjacent with all vertices of $S^{0}$.

For $i=1,\dots,t$, let $D_{i}=G[G_{i}\setminus(X\setminus X_{i})]$. By
induction, the $D_{i}$’s are $c$-dicolourable. For $i=1,\dots,t$, let
$\phi_{i}$ be a $c$-dicolouring of $D_{i}$. Assume without loss of generality
that $|\phi_{1}(X_{1})|\geq|\phi_{i}(X_{i})|$ for $1\leq i\leq t$. In
particular $\operatorname{\overrightarrow{\chi}}(X_{i})\leq|\phi_{1}(X_{1})|$
for $i=1,\dots,t$. Extend $\phi_{1}$ to a $c$-dicolouring of $D$ by
dicolouring each $X_{i}$ (independently) with colours from $\phi_{1}(X_{1})$.
We claim that this gives a $c$-dicolouring of $G$.

Let $C$ be an induced directed cycle of $G$. If $C$ is included in $X$ or
$V(G)\setminus X$, then $C$ is not monochromatic. So we may assume that $C$
intersects both $V(G)\setminus X$ and $X$. Since vertices in $X$ share the
same neighborhood outside $X$ and $C$ is induced, $C$ must intersect $X$ on
exactly one vertex, and this vertex can be chosen to be any vertex of $X$. In
particular we may assume that it is in $X_{1}$. Hence $C$ is not
monochromatic. ∎

Note that the proof of the previous theorem actually works for the following
stronger statement:

######  Theorem 5.3.

Let $\mathcal{C}$ be a class of digraphs closed under taking substitution and
let $(\mathcal{A}\cup\mathcal{C})^{*}$ be the closure of
$\mathcal{A}\cup\mathcal{C}$ under taking substitution. Then heroes in
$(\mathcal{A}\cup\mathcal{C})^{*}$ are the same as heroes in $\mathcal{C}$.

###  5.3 Heroes in $Forb_{ind}(F)$ when $F$ is a disjoint union of at least
two oriented star

When $F$ is a disjoint union of stars, as mentioned in the introduction, the
authors of [3] conjectured that heroes in $Forb_{ind}(F)$ were the same as
heroes in tournaments, and one of the main result of this paper disproves this
conjecture.

Since $Forb_{ind}(F_{1})\subseteq Forb_{ind}(F_{2})$ whenever $F_{1}$ is an
induced subgraph of $F_{2}$, and given our knowledge on heroes in
$Forb_{ind}(F)$ when $F$ is an oriented star, let us focus on disjoint union
of stars where each connected component is $K_{1}$, $TT_{2}$ or
$\overrightarrow{P}_{3}$.

We denote by $\mkern 1.7mu\overline{\mkern-1.7muK\mkern-1.7mu}\mkern
1.7mu_{t}$ the digraph on $t$ vertices with no arc (this is a disjoint union
of stars, where each connected component is $K_{1}$). Observe that
$Forb_{ind}(\mkern 1.7mu\overline{\mkern-1.7muK\mkern-1.7mu}\mkern 1.7mu_{2})$
is the class of tournaments. In [11], it is proved that heroes in
$Forb_{ind}(\mkern 1.7mu\overline{\mkern-1.7muK\mkern-1.7mu}\mkern 1.7mu_{t})$
are the same as heroes in tournaments. The proof of this result is quite hard,
and shows that knowing heroes in $Forb_{ind}(F)$ does not necessarily help in
understanding heroes in $Forb_{ind}(K_{1}+F)$. Even worse, it is clear that
every digraph is a hero in $Forb_{ind}(K_{1})$ and in $Forb_{ind}(TT_{2})$,
while our result shows that only very few digraphs are heroes in
$Forb_{ind}(K_{1}+TT_{2})$.

Theorem 3.2 suggests that the heroes in $Forb_{ind}(K_{1}+TT_{2})$ could be
the same as heroes in $Forb_{ind}(F)$ where $F=\mkern
1.7mu\overline{\mkern-1.7muK\mkern-1.7mu}\mkern 1.7mu_{t}+TT_{2}$ or $F=\mkern
1.7mu\overline{\mkern-1.7muK\mkern-1.7mu}\mkern
1.7mu_{t}+\overrightarrow{P}_{3}$. In order to prove it (up to the status of
$\Delta(1,2,2)$), it would be enough to answer by the affirmative to the
following question:

######  Question 5.4.

Let $H$ and $F$ be digraphs such that $\Delta(1,1,H)$ is a hero in
$Forb_{ind}(F)$ and $H$ is a hero in $Forb_{ind}(K_{1}+F)$. Then
$\Delta(1,1,H)$ is a hero in $Forb_{ind}(K_{1}+F)$.

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

## References

  * [1] Pierre Aboulker, Guillaume Aubian, and Pierre Charbit.  Decomposing and colouring some locally semicomplete digraphs.  ArXiv, abs/2103.07886, 2021.
  * [2] Pierre Aboulker, Guillaume Aubian, and Raphael Steiner.  Heroes in orientations of chordal graphs.  ArXiv, abs/2202.09191, 2022.
  * [3] Pierre Aboulker, Pierre Charbit, and Reza Naserasr.  Extension of Gyárfás-Sumner conjecture to digraphs.  The Electronic Journal of Combinatorics, May 2021.
  * [4] Maria Axenovich, Jonathan Rollin, and Torsten Ueckerdt.  Chromatic number of ordered graphs with forbidden ordered subgraphs.  Comb., 38(5):1021–1043, 2018.
  * [5] Jørgen Bang-Jensen and Gregory Gutin.  Classes of Directed Graphs.  Springer Publishing Company, Incorporated, 1st edition, 2018.
  * [6] Jørgen Bang-Jensen and Jing Huang.  Quasi-transitive digraphs.  Journal of Graph Theory, 20(2):141–161, 1995.
  * [7] 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.
  * [8] Maria Chudnovsky, Alex Scott, and Paul Seymour.  Induced subgraphs of graphs with large chromatic number. xi. orientations.  European Journal of Combinatorics, 76:53–61, 2019.
  * [9] Paul Erdős and Andras hajnal.  “on chromatic number of infinite graph.  Theory of Graphs (Proc. Coll. Tihany 1966, P. Erdőos and G. Katona, eds.), pages 61–99, 1966.
  * [10] 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.
  * [11] Ararat Harutyunyan, Tien-Nam Le, Alantha Newman, and Stéphan Thomassé.  Coloring dense digraphs.  Electronic Notes in Discrete Mathematics, 61:577–583, 2017.  The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’17).
  * [12] Ararat Harutyunyan and Bojan Mohar.  Two results on the digraph chromatic number.  Discrete Mathematics, 312(10):1823–1826, 2012.
  * [13] V Neumann-Lara.  The dichromatic number of a digraph.  Journal of Combinatorial Theory, Series B, 33(3):265–270, 1982\.
  * [14] Raphael Steiner.  On coloring digraphs with forbidden induced subgraphs.  ArXiv, abs/2103.04191, 2021.
  * [15] 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.