# The 3-dicritical semi-complete digraphs

Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta

► To cite this version:

Frédéric Havet, Florian Hörsch, Lucas Picasarri-Arrieta. The 3-dicritical semi-complete digraphs. 2024. [hal-04471658](https://hal.inria.fr/04471658v1)

HAL Id: hal-04471658

https://inria.hal.science/hal-04471658v1

Preprint submitted on 21 Feb 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The 3-dicritical semi-complete digraphs

Frédéric Havet*,¹, Florian Hörsch†,², and Lucas Picasarri-Arrieta‡,¹

¹ Université Côte d'Azur, CNRS, Inria, I3S, Sophia-Antipolis, France

²CISPA Saarbrücken, Germany

[frederic.havet, lucas.picasarri-arrieta]@inria.fr
florian.hoersch@cispa.de

## Abstract

A digraph is 3-dicritical if it cannot be vertex-partitioned into two sets inducing acyclic digraphs, but each of its proper subdigraphs can. We give a human-readable proof that the number of 3-dicritical semi-complete digraphs is finite. Further, we give a computer-assisted proof of a full characterization of 3-dicritical semi-complete digraphs. There are eight such digraphs, two of which are tournaments. We finally give a general upper bound on the maximum number of arcs in a 3-dicritical digraph.

# 1 Introduction

The purpose of this article is to completely characterize all semi-complete 3-dicritical digraphs, hence aiming to approach an analogue of some results on the maximum density of critical graphs. We first recall a few classical definitions and then give an overview of the previous work and motivation for our work.

## 1.1 Definitions

Our notation follows [4]. In this article, graphs and digraphs contain no parallel edges or arcs, respectively, and no loops. For some positive integer $k$, we use $[k]$ to denote the set $\{1, \dots, k\}$. The order of a graph $G$ (resp. digraph $D$) is denoted by $n(G)$ (resp. $n(D)$) and its number of arcs is denoted by $m(G)$ (resp. $m(D)$).

The path $v_1, \dots, v_n$ is the graph with vertex set $\{v_i \mid i \in [n]\}$ and edge set $\{v_i v_{i+1} \mid i \in [n-1]\}$. The length of a path is its number of edges. A matching is a set of pairwise disjoint edges. A graph $H$ is a subgraph of a graph $G$ if $V(H) \subseteq V(G)$ and $E(H) \subseteq E(G)$ hold. If additionally $V(H) \neq V(G)$ or $E(H) \neq E(G)$, then $H$ is called a proper subgraph of $G$. For some $S \subseteq V(G)$, we define $G[S]$ to be the subgraph of $G$ induced by $S$, that is, the graph whose vertex set is $S$ and whose edge set contains all the edges of $E(G)$ with both end vertices in $S$.

Similarly, a digraph $D'$ is a subdigraph of a digraph $D$ if $V(D') \subseteq V(D)$ and $A(D') \subseteq A(D)$ hold. If additionally $V(D') \neq V(D)$ or $A(D') \neq A(D)$ holds, then $D'$ is called a proper subdigraph of $D$. If $V(D') = V(D)$, then $D$ is called a spanning subdigraph of $D$. For some $S \subseteq V(D)$, we define $D[S]$ to be the subdigraph of $D$ induced by $S$, that is, the digraph whose vertex set is $S$ and whose arc set contains all the arcs of $A(D)$ with both end vertices in $S$. When we say that a digraph $D$ contains another digraph $D'$ as an (induced) subdigraph, we mean that $D$ has an (induced) subdigraph which

<footnote>*Research supported by the research grant DIGRAPHS ANR-19-CE48-0013</footnote>

<footnote>†Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATIC-GRAPH.</footnote>

<footnote>‡Research supported by the research grants DIGRAPHS ANR-19-CE48-0013 and ANR-17-EURE-0004.</footnote>
is isomorphic to $D'$, hence not necessarily maintaining vertex labels. In case we want vertex labels to be maintained, we speak of an (induced) labelled subgraph. For two disjoint sets $X, Y \subseteq V(D)$, we say that $X$ dominates $Y$ (and $Y$ is dominated by $X$) if $xy \in A(D)$ holds for all $x \in X$ and $y \in Y$.

The underlying graph of a digraph $D$, denoted by $UG(D)$, is the graph on the same vertex set which contains an edge linking two vertices if the digraph contains at least one arc linking these two vertices. Given an arc $uv$ in a digraph, we say that $v$ is an out-neighbour of $u$ and that $u$ is an in-neighbour of $v$. The set of out-neighbours of a vertex $u$ in a digraph $D$ is denoted by $N_D^+(u)$, and its set of in-neighbours in $D$ is denoted by $N_D^-(u)$. The out-degree of $u$ in $D$ is its number of out-neighbours, and its in-degree is its number of in-neighbours.

A digon is a pair of arcs in opposite directions linking the same vertices. An arc is called simple if it is not contained in a digon. A digraph in which every arc is contained in a digon is called bidirected. An oriented graph is a digraph with no digon. A digraph $D$ is called semi-complete if for all distinct $u, v \in V(D)$, at least one of the arcs $uv$ and $vu$ exists. A semi-complete digraph with no digon is called a tournament. The directed cycle on $n \ge 2$ vertices is the digraph with vertex set $\{v_1, \dots, v_n\}$ and arc set $\{v_i v_{i+1} \mid i \in [n-1]\} \cup \{v_n v_1\}$. The directed cycle on three vertices is called the directed triangle. A digraph is acyclic if it does not contain any directed cycle. For an acyclic digraph $D$, there is an ordering $v_1, \dots, v_n$ of $V(D)$ such that for every arc $v_i v_j \in A(D)$, we have $i < j$. Such an ordering is called acyclic. An acyclic tournament is called transitive. For some positive integer $n$, we use $TT_n$ to denote the unique transitive tournament on $n$ vertices.

## 1.2 Context

A $k$-colouring of a graph $G$ is a function $\phi: V(G) \to [k]$. It is proper if $\phi(u) \neq \phi(v)$ for every edge $uv \in E(G)$. We say that $G$ is $k$-colourable if it admits a proper $k$-colouring. Colourability of graphs is one of the most deeply studied subjects in graph theory and countless aspects and variations of this parameter have been considered. One easy observation is that if a graph is $k$-colourable, then so is each of its subgraphs. This leads to the study of graphs that are in some way minimal obstructions to $(k-1)$-colourability, which are exactly $k$-critical graphs: a graph $G$ is $k$-critical if $G$ is not $(k-1)$-colourable, but all of its proper subgraphs are. Observe that every $k$-critical graph is $k$-colourable. Dirac [8–11] established the basic properties of critical graphs. For $k=1,2$, the only $k$-critical graph is $K_k$, the complete graph on $k$ vertices, and a graph is $3$-critical if and only if it is an odd cycle. For every $k \ge 4$, there is no $k$-critical graph on $k+1$ vertices and for every $n \ge k+2$, there exists a $k$-critical graph on $n$ vertices. Further, for every $k \ge 4$, the structure of $k$-critical graphs is immensely rich and many aspects of $k$-critical graphs have been studied, concerning both their importance in their own respect and their role when approaching colourability questions.

One feature of particular interest is the density of $k$-critical graphs. For some $n \ge k$, let $g_k(n)$ be the minimum number of edges of a $k$-critical graph of order $n$ with the convention $g_k(k+1) = +\infty$. The sequence $g_k$ is rather well understood due to the following result of Kostochka and Yancey [21].

**Theorem 1 (Kostochka and Yancey [21]).** Let $n$ and $k$ be two integers such that $n > k \ge 4$.

If $G$ is a $k$-critical graph on $n$ vertices, then $m(G) \ge \left\lfloor \frac{(k+1)(k-2)n-k(k-3)}{2(k-1)} \right\rfloor$. In other words,
$$g_k(n) \ge \left\lfloor \frac{(k+1)(k-2)n-k(k-3)}{2(k-1)} \right\rfloor.$$

This lower bound is sharp for a significant amount of values of $n$ and $k$ and close to sharp for all remaining ones, which is certified by $k$-critical graphs that can be obtained from complete graphs using a construction due to Hajós [15]. Theorem 1 confirms a conjecture of Gallai [13] and improves on a collection of earlier results [10, 13, 14, 19, 22]. A more detailed overview can be found in [21].

The girth of a graph $G$ is the minimum length of a cycle in $G$ or $+\infty$ if $G$ is a forest. Kostochka and Steibitz [18] showed that if a $k$-critical $G$ has girth at least 4, then $m(G) \ge (k-o(k))n(G)$. Informally, this means that the minimum average degree of a $k$-critical triangle-free graph is (asymptotically) twice
the minimum average degree of a $k$-critical graph. Liu and Postle [23] showed that the minimum number of edges of a 4-critical graph is significantly larger than $g_4(n)$ if we require the graph to have girth 5. More concretely, they show the existence of constants $c$ and $\varepsilon > 0$ such that every 4-critical graph $G$ of girth at least 5 contains at least $(\frac{5}{3} + \varepsilon)n(G) + c$ edges. Likewise, Postle [27] showed that every 5-critical graph with girth at least 4 satisfies $m(G) \ge (\frac{9}{4} + \varepsilon)n(G) - \frac{5}{4}$ for $\varepsilon = \frac{1}{84}$.

It is also interesting to determine the maximum number of edges in a $k$-critical graph. Erdős [12] asked, for every fixed $k \ge 4$, whether there exists a constant $c_k > 0$ such that there exists arbitrarily large $k$-critical graphs $G$ with at least $c_k \cdot n(G)^2$ edges. This was proved by Dirac [8] when $k \ge 6$ and then by Toft [29] when $k \in \{4, 5\}$. The best current upper bound on such a constant $c_k$ has recently been given by Luo, Ma, and Yang [24], improving on an earlier result of Stiebitz [28].

Several analogues of colouring have been introduced for digraphs. In 1982, Neumann-Lara [25] introduced the one of dicolouring. A $k$-dicolouring of a digraph $D$ is a function $\phi : V(D) \to [k]$ such that $D[\phi^{-1}(i)]$ is acyclic for every $i \in [k]$. We say that $D$ is $k$-dicolourable if it admits a $k$-dicolouring. Dicolourablity is a generalization of colouring to digraphs: indeed there is a trivial one-to-one correspondence between the proper $k$-colourings of a graph $G$ and the $k$-dicolourings of the associated bidirected graph $\overleftrightarrow{G}$ obtained from $G$ by replacing every edge by a digon.

We say that $D$ is $k$-dicritical if $D$ is not $(k-1)$-dicolourable, but all of its proper subdigraphs are. Observe that every $k$-dicritical digraph is $k$-dicolourable. The interest in $k$-dicritical graphs arises in a similar way as the interest in $k$-critical graphs. While the only 1-dicritical digraph is the digraph on one vertex and a graph is 2-dicritical if and only if it is a directed cycle, already 3-dicritical digraphs have a very diverse structure. Analogues of Hajós' construction have been found by Bang-Jensen et al. [3]. Again, for some $n \ge k$, it is natural to consider $d_k(n)$, the minimum number of arcs of a $k$-dicritical digraph of order $n$, with the convention $d_k(n) = +\infty$ if no such digraph exists.

Observe that, for every $k \ge 2$, the digraph obtained from a bidirected complete graph on $k+1$ vertices by removing the arcs of a directed triangle is a $k$-dicritical digraph on $k+1$ vertices. Note also that a graph $G$ is $k$-critical if and only if its associated bidirected graph $\overleftrightarrow{G}$ is $k$-dicritical. Together with the fact that there exist $k$-critical graphs of every order at least $k+2$, this implies that there exists a $k$-dicritical digraph of any order at least $k$. In other words, we have $d_k(n) < +\infty$ for all $n \ge k$. Moreover, it holds $d_k(n) \le 2g_k(n)$ for all $n \ge k$.

Kostochka and Stiebitz [20] conjectured that the bidirected $k$-dicritical digraphs obtained from $k$-critical graphs are the sparsest $k$-dicritical digraphs.

**Conjecture 2** (Kostochka and Stiebitz [20]). Let $n$ and $k$ be two integers such that $n-2 \ge k \ge 4$. Then $d_k(n) = 2g_k(n)$ and the $k$-dicritical digraphs of order $n$ with $d_k(n)$ arcs are the bidirected graphs associated to $k$-critical graphs with $g_k(n)$ edges.

With Theorem 1 this conjecture implies the following slightly weaker one.

**Conjecture 3** (Kostochka and Stiebitz [20]). Let $n$ and $k$ be two integers such that $n > k \ge 4$. If $D$ is a $k$-dicritical digraph on $n$ vertices, then $m(D) \ge \left\lfloor \frac{(k+1)(k-2)n-k(k-3)}{k-1} \right\rfloor$ and all digraphs attaining this bound are bidirected.

In [20], Kostochka and Stiebitz confirmed Conjecture 3 for $k \le 4$.

Similarly to the undirected case, it is expected that the minimum number of arcs in a $k$-dicritical digraph of order $n$ is larger than $d_k(n)$ if we impose this digraph to have no short directed cycles, and in particular if the digraph is an oriented graph. Let $o_k(n)$ denote the minimum number of arcs in a $k$-dicritical oriented graph of order $n$ with the convention $o_k(n) = +\infty$ if there is no $k$-dicritical oriented graph of order $n$. Clearly, we have $o_k(n) \ge d_k(n)$. Kostochka and Stiebitz [20] posed a conjecture suggesting that there is a significant gap between $d_k(n)$ and $o_k(n)$.

**Conjecture 4** (Kostochka and Stiebitz [20]). There exists $\varepsilon > 0$ such that $o_k(n) \ge (1+\varepsilon) \cdot d_k(n)$ for every $k \ge 4$ and sufficiently large $n$.
Observe that this conjecture trivially holds when $o_k(n) = +\infty$. However we do not know the set $N_k$ of integers $n$ for which $o_k(n) < +\infty$, that is, for which there exists a $k$-dicritical oriented graph on $n$ vertices. Already the minimum number $n_k$ of vertices of a $k$-dicritical oriented graph is unknown except for small values of $k$: clearly $n_2 = 3$; Neumann Lara [26] proved $n_3 = 7$ and $n_4 = 11$; Bellitto et al. [5] recently established $n_5 = 19$. As observed by Aboulker et al. [2] using a lemma of Hoshino and Kawarabayashi [17], there exists a smallest integer $p_k$ such that there exists a $k$-dicritical oriented graph on $n$ vertices for any $n \ge p_k$. Moreover, while $p_3 = n_3 = 7$, they showed that $p_4 \ne n_4$ because there is no 4-dicritical oriented graph on 12 vertices.

Conjecture 4 has been confirmed for $k = 3$ by Aboulker et al. [2] and for $k = 4$ by the first and third authors, and Rambaud [16].

We now turn our attention to the maximum density of $k$-dicritical digraphs which is the main subject of the present article. For every $k \ge 3$, Hoshino and Kawarabayashi [17] constructed an infinite family of $k$-dicritical oriented graphs $D$ on $n$ vertices which satisfy $m(D) \ge (\frac{1}{2} - \frac{1}{2^k-1})n^2$, and they conjectured that this bound is tight.

**Conjecture 5** (Hoshino and Kawarabayashi [17]). Let $k \ge 3$ be an integer. If $D$ is a $k$-dicritical oriented graph, then $m(D) \le (\frac{1}{2} - \frac{1}{2^k-1})n^2$.

Aboulker [1] observed that, since a tournament has $\frac{1}{2}n(n-1)$ arcs, this conjecture implies that the number of $k$-dicritical tournaments is finite, and he asked whether this latter statement holds. It trivially does for the case $k = 2$.

## 1.3 Our results

In this paper, we positively answer Aboulker's question in the case $k = 3$ by showing that the collection of 3-dicritical semi-complete digraphs is finite, and hence so is the subcollection of 3-dicritical tournaments.

**Theorem 6.** There is a finite number of 3-dicritical semi-complete digraphs.

While the proof of Theorem 6 is fully human readable, the result is obtained by showing that the number of vertices of any 3-dicritical semi-complete digraph does not exceed a pretty large number which originates from a Ramsey-type argument.

We after use a computer-assisted proof to provide the following characterization of all 3-dicritical semi-complete digraphs.

**Theorem 7.** There are exactly eight 3-dicritical semi-complete digraphs. They are depicted in Figure 1.

In particular, we can characterize all 3-dicritical tournaments.

**Corollary 8.** There are exactly two 3-dicritical tournaments, namely $R(\vec{C}_3, \vec{C}_3)$ and $P_7$.

We finally investigate the maximum density of 3-dicritical digraphs. The *bidirected part* of a digraph $D$ is the graph $B(D)$ with vertex set $V(D)$ in which two vertices are linked by an edge if and only if there is a digon between them in $D$. We prove in Proposition 25 that $B(D)$ is a forest for every 3-dicritical digraph $D$. From this result, one can easily deduce that $m(D) \le \binom{n}{2} + n - 1$ holds for every 3-dicritical digraph $D$ different from $\overrightarrow{K_3}$. We slightly improve this upper bound on $m(D)$ as follows (the digraph $\overrightarrow{W_3}$ is depicted in Figure 1).

**Theorem 9.** If $D$ is a 3-dicritical digraph distinct from $\overrightarrow{K_3}$ and $\overrightarrow{W_3}$, then $m(D) \le \binom{n}{2} + \frac{2}{3}n$.
<figure><img src="image_2.png" /><figcaption>(a) $\vec{K_3}$</figcaption></figure>

<figure><img src="image_3.png" /><figcaption>(b) $\vec{W_3}$</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>(c) $\mathcal{R}(\vec{K_2}, \vec{K_2})$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>(d) $\mathcal{H}_5$</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>(e) $\mathcal{R}(\vec{K_2}, \vec{C_3})$</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>(f) $\mathcal{R}(\vec{C_3}, \vec{K_2})$</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>(g) $\mathcal{R}(\vec{C_3}, \vec{C_3})$</figcaption></figure>

<figure><img src="image_9.png" /><figcaption>(h) $\mathcal{P}_7$</figcaption></figure>

Figure 1: The 3-dicritical semi-complete digraphs, namely the bidirected complete graph $\vec{K_3}$, the directed wheel $\vec{W_3}$, the digraph $\mathcal{H}_5$, the rotative digraphs $\mathcal{R}(H_1, H_2)$ for every $H_1, H_2 \in \{\vec{K_2}, \vec{C_3}\}$ and the Paley tournament on seven vertices $\mathcal{P}_7$. A big arrow linking two sets of vertices indicates that there is exactly one arc from every vertex in the first set to every vertex in the second set.

The rest of this article is structured as follows: In Section 2, we give a collection of preliminary results which will be used in the proofs of Theorems 6, 7, and 9. In Section 3, we prove Theorem 6. In Section 4, we prove Theorem 7, with all code we use being shifted to the appendix. Section 5 is devoted to the proof of Theorem 9. Finally, in Section 6, we conclude our work and give some directions for further research.

## 2 Useful lemmas

In this section, we give a collection of preliminary results we need in the proof of Theorem 6. Most of them will be reused in the proof of Theorem 7. We first describe 2-dicolourings with some important extra properties.

Let $D$ be a digraph and $uv$ be an arc of $D$. A *$uv$-colouring* of $D$ is a 2-colouring $\phi: V(D) \to [2]$ such that:

* $\phi$ is a 2-dicolouring of $D \setminus uv$,
• $\phi(u) = \phi(v) = 1$, and

• $D \setminus uv$, coloured with $\phi$, does not contain any monochromatic directed uv-path.

There is a close relationship between 3-dicritical digraphs and uv-colourings.

**Lemma 10.** Let $D$ be a 3-dicritical digraph and $uv$ be an arc of $D$. Then $D$ admits a uv-colouring.

*Proof.* As $D$ is 3-dicritical, there is a 2-dicolouring $\phi: V(D) \to [2]$ of $D \setminus uv$. By symmetry, we may suppose $\phi(u) = 1$. As $\phi$ is not a 2-dicolouring of $D$, we obtain that $\phi(v) = 1$ and there is a directed vu-path $P$ in $D$ such that $\phi(x) = 1$ for all $x \in V(P)$. If there is also a directed uv-path $Q$ in $D \setminus uv$ such that $\phi(x) = 1$ for all $x \in V(Q)$, then the subdigraph of $D \setminus uv$ induced by $V(P) \cup V(Q)$ contains a monochromatic directed cycle. This contradicts $\phi$ being a 2-dicolouring of $D \setminus uv$. $\square$

The next result showing that every arc of a 3-dicritical semi-complete digraph is contained in a
short directed cycle will play a crucial role in the upcoming proofs.

**Lemma 11.** Let $D$ be a 3-dicritical semi-complete digraph. Then every arc $a \in A(D)$ either belongs to a digon or is contained in an induced directed triangle.

*Proof.* As $D$ is 3-dicritical, there is a 2-dicolouring $\phi$ of $D \setminus a$. As $\phi$ is not a 2-dicolouring of $D$, there exists a directed cycle $C$ in $D$ such that $C$ is monochromatic with respect to $\phi$. We may suppose that $C$ is chosen to be of minimum length with this property. As $D$ is semi-complete, we obtain that $C$ is either a digon or an induced directed triangle. As $C$ is not a monochromatic directed cycle of $D \setminus a$ with respect to $\phi$, we obtain that $a \in A(C)$. $\square$

We define $O_5$ as the oriented graph which consists of a directed triangle $xyz$ and two additional vertices $u, v$, one arc from $u$ to every vertex of the directed triangle, one arc from every vertex of the directed triangle to $v$, and the arc $uv$. An illustration can be found in Figure 2.

<figure><img src="image_10.png" /><figcaption>Figure 2: The oriented graph $O_5$.</figcaption></figure>

The following result is a consequence of Lemma 10.

**Lemma 12.** Let $D$ be a 3-dicritical digraph. Then $D$ does not contain $O_5$ as a subdigraph.

*Proof.* Assume for a contradiction that $D$ contains $O_5$ as a subdigraph and let $V(O_5) = \{u, v, x, y, z\}$ be the labelling depicted in Figure 2. By Lemma 10, there exists a uv-colouring $\phi$ of $D$. Since there exists no monochromatic directed uv-path, we have $\phi(x) = \phi(y) = \phi(z) = 2$. Hence $D \setminus uv$ contains a monochromatic directed triangle with respect to $\phi$, a contradiction. $\square$

Let $S$ be a transitive subtournament of a digraph $D = (V, A)$. We denote by $v_1, \dots, v_s$ the unique acyclic ordering of $S$. For some $i, j \in [s]$, we say that $\{v_i, \dots, v_j\}$ is an *interval* of $S$. Observe that $\emptyset$ is an interval. For $i_0, j_0, i_1, j_1 \in [s]$ with $j_0 < i_1$, we say that the interval $\{v_{i_0}, \dots, v_{j_0}\}$ is *smaller* than the interval $\{v_{i_1}, \dots, v_{j_1}\}$. By convention $\emptyset$ is both smaller and greater than any other interval. A sequence of intervals $P_1, \dots, P_t$ is called *increasing* if $P_i$ is smaller than $P_j$ for all $i, j \in [t]$ with $i < j$.
**Lemma 13.** Let $T$ be a subtournament of a 3-dicritical digraph $D$ and let $S$ be a transitive subtournament of $T$ with acyclic ordering $v_1, \dots, v_s$. For any $x \in V(T) \setminus S$, there is an increasing sequence of intervals $(I_1, I_2, I_3, I_4)$ with $\bigcup_{i=1}^4 I_i = S$ such that, in $T$, $x$ dominates $I_1 \cup I_3$ and is dominated by $I_2 \cup I_4$.

*Proof.* Assume this is not the case. Then there exists an increasing sequence of indices $(i_1, i_2, i_3, i_4)$ such that, in $T$, $x$ is dominated by $v_{i_1}$ and $v_{i_3}$ and dominates $v_{i_2}$ and $v_{i_4}$. Then the subdigraph of $D$ induced by $\{v_{i_1}, v_{i_2}, x, v_{i_3}, v_{i_4}\}$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12. $\square$

We finally need a well-known theorem which can be found in many basic textbooks on graph theory, see for example [7, Theorem 9.1.3].

**Theorem 14 (MULTI-COLOUR RAMSEY THEOREM).** Let $a$ and $b$ be positive integers. There exists a smallest integer $R_a(b)$ such that for $G$ being a copy of $K_{R_a(b)}$ and for every mapping $\psi: E(G) \to [a]$, there is a set $S \subseteq V(G)$ of cardinality $b$ and $i \in [a]$ such that $\psi(e) = i$ for all $e \in E(G[S])$.

### 3 A simple proof for finiteness

In this section, we prove that the number of 3-dicritical semi-complete digraphs is finite. Let us first restate this result.

**Theorem 6.** There is a finite number of 3-dicritical semi-complete digraphs.

*Proof.* Let $D = (V, A)$ be a 3-dicritical semi-complete digraph. We will show that $n(D) \le 12R_6(3)+1$, where $R_6(3)$ refers to the Ramsey number in Theorem 14. Assume for the sake of a contradiction that $n(D) \ge 12R_6(3)+2$. Let $S \subseteq V$ be a maximum set of vertices such that $D[S]$ is acyclic. Let $v_1, \dots, v_s$ be the unique acyclic ordering of $S$. Since $D$ is 3-dicritical, for an arbitrary vertex $x \in V$, we have that $D-x$ is 2-dicolourable. This yields $s \ge \lfloor \frac{n(D)-1}{2} \rfloor \ge 6R_6(3)+1$.

By Lemma 11, for every $i \in [s-1]$, the arc $v_iv_{i+1}$ belongs to a digon or an induced directed triangle. Therefore, since $D[S]$ is acyclic, we know that there exists a vertex $x_i \in V \setminus S$ such that $v_iv_{i+1}x_iv_i$ is an induced directed triangle $C_i$.

Let $T$ be an arbitrary spanning subtournament of $D$. Observe that $T[S] = D[S]$ as $D[S]$ is acyclic. Further, the directed triangle $C_i$ is contained in $T$ for $i \in [s-1]$ as $C_i$ is induced in $D$. For any vertex $x$ in $V \setminus S$ and $i \in [s-1]$, we say that $x$ switches at $i$ if $x$ dominates $v_i$ and is dominated by $v_{i+1}$ in $T$ or $x$ is dominated by $v_i$ and dominates $v_{i+1}$ in $T$.

Let $H$ be the digraph with vertex set $V(H) = [s-1]$ and arc set $A(H) = A_1 \cup A_2$ with $A_1 = \{(i, i+1) \mid i \in [s-2]\}$ and $A_2 = \{(i, j) \mid i \ne j \text{ and } x_i \text{ switches at } j.\}$.

By Lemma 13, for $i \in [s-1]$, we have that $x_i$ switches at at most three indices in $[s-1]$. Further, as $C_i$ is a directed triangle, $x_i$ switches at $i$ which yields that $x_i$ switches at at most two indices in $[s-1] \setminus \{i\}$. Thus every $i \in [s-1]$ is the tail of at most two arcs in $A_2$.

For every subset $J$ of $[s-1]$, observe that $H[J]$ contains at most $|J|-1$ arcs in $A_1$ and at most $2|J|$ arcs in $A_2$, hence at most $3|J|-1$ arcs in total. Thus $\mathrm{UG}(H)[J]$ has a vertex of degree at most 5. Hence $\mathrm{UG}(H)$ is 5-degenerate, and so it is 6-colourable. Therefore $H$ has an independent set $I$ of size $\lceil \frac{1}{6}(s-1) \rceil \ge R_6(3)$.

By definition of $I$, for any $i, j \in I$ with $i \ne j$, we have that $V(C_i)$ and $V(C_j)$ are disjoint. Moreover, either $\{v_j, v_{j+1}\}$ dominates $x_i$ in $T$ or $\{v_j, v_{j+1}\}$ is dominated by $x_i$ in $T$. Hence, if $i < j$, the subdigraph of $T$ induced by $V(C_i) \cup V(C_j)$ is one of the eight tournaments depicted in Figure 3. For $(\alpha) \in \{(a), \dots, (h)\}$, we say that $(i, j)$ is an $(\alpha)$-configuration if $T[V(C_i) \cup V(C_j)]$ is the tournament depicted in Figure 3 $(\alpha)$.

Let us fix a pair $i, j \in I$ with $i < j$. We know that it is not a $(g)$-configuration, for otherwise $D[v_{i+1}, v_j, v_{j+1}, x_j, x_i]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12. We also know
<figure><img src="image_11.png" /></figure>

<figure><img src="image_12.png" /></figure>

<figure><img src="image_13.png" /></figure>

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /></figure>

<figure><img src="image_16.png" /></figure>

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /><figcaption>Figure 3: A listing of all possible configurations for $i, j \in I$ with $i < j$. For the sake of better readability, the arcs in $A(C_i) \cup A(C_j)$ and the arcs from $V(C_j)$ to $V(C_i)$ are solid, and the arcs from $V(C_i)$ to $V(C_j)$ are dashed.</figcaption></figure>

that it is not an (h)-configuration, for otherwise $D[x_j, v_i, v_{i+1}, x_i, v_j]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12.

Since $|I| \ge R_6(3)$, and by definition of $R_6(3)$, we know that there exist $\{i, j, h\} \subseteq I$, $i < j < h$, and $(\alpha) \in \{(a), \dots, (e)\}$ such that the three pairs $(i, j)$, $(j, h)$, $(i, h)$ are $(\alpha)$-configurations. We show that each of the six cases yields a contradiction, implying the result.

* If $(\alpha) = (a)$, let $\phi$ be a $v_{i+1}v_h$-colouring of $D$, the existence of which is guaranteed by Lemma 10. Recall that $\phi(v_{i+1}) = \phi(v_h) = 1$, $\phi$ is a 2-dicolouring of $D \setminus v_{i+1}v_h$ and $D$ coloured with $\phi$ contains no monochromatic directed $v_{i+1}v_h$-path. Then $\phi(v_j) = \phi(v_{j+1}) = 2$ because $\{v_j, v_{j+1}\} \subseteq N_D^+(v_{i+1}) \cap N_D^-(v_h)$. Thus, since $C_j$ is not monochromatic in $\phi$, we have $\phi(x_j) = 1$. We obtain that $\phi(x_i) = \phi(v_i) = 2$, for otherwise $v_{i+1}x_ix_jv_{i+1}$ or $v_iv_hx_jv_i$ is monochromatic. We deduce that $v_iv_jx_iv_i$ is monochromatic, a contradiction.

* If $(\alpha) = (b)$, then $D[x_h, v_j, v_{j+1}, x_j, x_i]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12.

* If $(\alpha) = (c)$, then $D[x_i, v_j, v_{j+1}, x_j, v_h]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12.
• If $(\alpha) = (d)$, then $D[v_i, v_j, v_{j+1}, x_j, x_h]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12.

• If $(\alpha) = (e)$, then $D[v_i, v_j, v_{j+1}, x_j, v_h]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12.

• If $(\alpha) = (f)$, then $D[v_i, v_j, v_{j+1}, x_j, v_h]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12.

□

# 4 The 3-dicritical semi-complete digraphs

This section is devoted to a computer-assisted proof of Theorem 7. It follows a similar line as the one of Theorem 6, but it needs some refined arguments. Further, due to the significant number of necessary computations, several parts of the proof are computer-assisted. We used codes implemented using SageMath. They are available on the third author's GitHub page.

We first restrain the structure of 3-dicritical semi-complete digraphs. To prove Theorem 6, we only needed the fact that $O_5$ does not occur as a subdigraph. To prove Theorem 7, we need to prove that several other digraphs cannot be subdigraphs or induced subdigraphs of a 3-dicritical digraph. One of these digraphs is the transitive tournament of size at least 8. While already parts of this proof are computer-assisted, the most intense computation part is carried out after. We generate all semi-complete digraphs satisfying these properties and check that none of them has dichromatic number 3, except the ones depicted in Figure 1.

Before dealing with the collection of digraphs which are not contained in 3-dicritical semi-complete digraphs as subdigraphs, we first give the following simple observation on matchings in graphs on seven vertices which will prove useful later on.

**Lemma 15.** Let $H$ be a graph that is obtained from a path $w_1...w_7$ by adding the edges of a matching $M$ on $\{w_1, ..., w_7\}$. Then there is a stable set $S \subseteq V(H)$ with $|S| = 3$ and $\{w_1, w_7\} \setminus S \neq \emptyset$.

*Proof.* Suppose otherwise. If $w_1$ is not incident to an edge of $M$, then, as none of $\{w_1, w_3, w_5\}$ and $\{w_1, w_3, w_6\}$ is an independent set, we obtain that $w_3w_5, w_3w_6 \in E(M)$, a contradiction to $M$ being a matching. Hence $M$ contains an edge $e_1$ incident to $w_1$. Similarly, $M$ contains an edge $e_7$ incident to $w_7$. Further, $M$ contains an edge $e_0$ both of whose endvertices are contained in $\{w_2, w_4, w_6\}$. As none of $e_0$ and $e_7$ are contained in one of $\{w_1, w_3, w_6\}$ and $\{w_1, w_3, w_5\}$, we obtain that $e_1$ needs to be contained in both of them. This yields $e_1 = w_1w_3$. Similarly, we obtain $e_7 = w_5w_7$. By symmetry, we may suppose that $e_0 \neq w_4w_6$. But then $\{w_1, w_4, w_6\}$ is an independent set, a contradiction. $\square$

We now start excluding some subdigraphs of 3-dicritical semi-complete digraphs. We first define $O_4$ as the digraph which consists of a copy of $\overleftrightarrow{K_2}$ and two additional vertices $u, v$, one arc from $u$ to every vertex of $\overleftrightarrow{K_2}$, one arc from every vertex of $\overleftrightarrow{K_2}$ to $v$, and the arc $uv$. An illustration can be found in Figure 4.

The digraph $O_4$ plays a similar role as $O_5$. Also, the proof of the following result is similar to the one of Lemma 12.

**Lemma 16.** Let $D$ be a 3-dicritical digraph. Then $D$ does not contain $O_4$ as a subdigraph.

*Proof.* Assume for the purpose of contradiction that $D$ contains $O_4$ as a subdigraph and let $V(O_4) = \{u, v, x, y\}$ be the labelling depicted in Figure 4. By Lemma 10, there exists a 2-dicolouring $\phi$ of $D \setminus uv$ with $\phi(x) = \phi(y)$. Hence $D \setminus uv$ contains a monochromatic digon with respect to $\phi$, a contradiction. $\square$

In the following, let $\overleftrightarrow{S_4}$ be the bidirected star on 4 vertices, see Figure 5. The following result shows that $\overleftrightarrow{S_4}$ cannot be the subdigraph of any large 3-dicritical semi-complete digraph.
<figure><img src="image_19.png" /><figcaption>Figure 4: The digraph $O_4$.</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure 5: The bidirected star on 4 vertices $\overrightarrow{S_4}$.</figcaption></figure>

**Lemma 17.** Let $D$ be a semi-complete digraph containing $\overrightarrow{S_4}$ as a subdigraph. Then $D$ is 3-dicritical if and only if $D$ is $\overrightarrow{W_3}$.

*Proof.* It is easy to see that $\overrightarrow{W_3}$ is 3-dicritical and contains $\overrightarrow{S_4}$. For the other direction, let $D$ be a 3-dicritical semi-complete digraph such that $D$ contains a vertex $u$ linked by digons to three distinct vertices $x, y, z$.

Then, as $D$ is semi-complete, we have that $D[\{x, y, z\}]$ needs to contain $\overrightarrow{C_3}$ or $TT_3$ as a subdigraph. If it is $TT_3$, then $D$ contains $O_4$ as a subdigraph, a contradiction to Lemma 16. Hence $D[\{u, x, y, z\}]$ contains $\overrightarrow{W_3}$ as a subdigraph. Since both $D$ and $\overrightarrow{W_3}$ are 3-dicritical, we have $D = \overrightarrow{W_3}$. $\square$

We now prove a similar result for a collection of four digraphs. Given two digraphs $H_1$ and $H_2$, let $H_1 \Rightarrow H_2$ denote the *directed join* of $H_1$ and $H_2$, that is the digraph obtained from disjoint copies of $H_1$ and $H_2$ by adding all arcs from the copy of $H_1$ to the copy of $H_2$. If we further add all the arcs from $H_2$ to $H_1$, we obtain the *bidirected join* of $H_1$ and $H_2$, denoted by $H_1 \boxplus H_2$. It is straightforward that $\vec{\chi}(H_1 \boxplus H_2) = \vec{\chi}(H_1) + \vec{\chi}(H_2)$, see [3].

**Lemma 18.** Let $H_1, H_2$ be two digraphs in $\{\overrightarrow{K_2}, \overrightarrow{C_3}\}$ and let $D$ be a semi-complete digraph containing $H_1 \Rightarrow H_2$ as a subdigraph. Then $D$ is 3-dicritical if and only if $D$ is exactly $\mathcal{R}(H_1, H_2)$.

*Proof.* It is easy to see that $\mathcal{R}(H_1, H_2)$ is 3-dicritical. For the other direction, let us fix $H_1, H_2 \in \{\overrightarrow{K_2}, \overrightarrow{C_3}\}$ and let $D$ be a 3-dicritical semi-complete digraph containing $H_1 \Rightarrow H_2$.

Let $X = V(H_1)$ and $Y = V(H_2)$. Let us first prove that $V(D) \setminus (X \cup Y) \neq \emptyset$, so assume for a contradiction that $V(D) = X \cup Y$. We claim that there exists a simple arc $uv$ from $X$ to $Y$. If this is not the case, then $D$ is exactly $H_1 \boxplus H_2$, so it has dichromatic number 4, a contradiction. This simple arc $uv$ belongs to an induced directed triangle by Lemma 11. This directed triangle uses an arc from $Y$ to $X$, which is necessarily in a digon, a contradiction since it must be induced. Henceforth we assume that $V(D) \setminus (X \cup Y) \neq \emptyset$.

First suppose that there exists some $v \in V(D) \setminus (X \cup Y)$ having at least one in-neighbour and one out-neighbour in both $X$ and $Y$. Since $H_1$ and $H_2$ are strongly connected, there exist four distinct vertices $x_1, x_2 \in X$ and $y_1, y_2 \in Y$ such that $\{x_1x_2, y_1y_2, x_1v, vx_2, y_1v, vy_2\}$ are all arcs of $D$. Then $D[\{x_1, v, x_2, y_1, y_2\}]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12. Henceforth we may assume that every vertex $v \in V(D) \setminus (X \cup Y)$ has no out-neighbour or no in-neighbour in one of $\{X, Y\}$.
Now suppose that there exists some $v \in V(T) \setminus (X \cup Y)$ that dominates $X$. If $v$ has an out-neighbour $y$ in $Y$, then $D[X \cup \{v, y\}]$ contains $O_4$ as a subdigraph if $H_1 = \overleftrightarrow{K_2}$ and $O_5$ otherwise, a contradiction to Lemma 16 or 12, respectively. Hence $v$ has no out-neighbour in $Y$. Since $D$ is semi-complete, this implies that $Y$ dominates $v$. Hence $D$ contains $\mathcal{R}(H_1, H_2)$, implying that $D$ is exactly $\mathcal{R}(H_1, H_2)$ since both $D$ and $\mathcal{R}(H_1, H_2)$ are 3-dicritical.

Henceforth we assume that for every vertex $v \in V(D) \setminus (X \cup Y)$, there exists in $D$ a simple arc from $X$ to $v$. By directional duality, there exists also a simple arc from $v$ to $Y$. Recall that every vertex $v \in V(D) \setminus (X \cup Y)$ has no out-neighbour or no in-neighbour in one of $\{X, Y\}$. We conclude on the existence of a partition $(V_1, V_2)$ of $V(D) \setminus (X \cup Y)$ such that there is no arc from $V_1$ to $X$ and there is no arc from $Y$ to $V_2$.

By symmetry, we may assume that $V_2$ is non-empty. Let us fix $v_2 \in V_2$ and $y_1 \in Y$. Since $v_2 y_1$ is a simple arc, by Lemma 11, there exists a vertex $v_1$ such that $v_2 y_1 v_1 v_2$ is an induced directed triangle in $D$. Note that $v_1 \notin Y$ since there is no arc from $Y$ to $V_2$. Also note that $v_1 \notin X$ for otherwise $v_2 y_1 v_1 v_2$ is not induced since $X$ dominates $Y$. Further note that $v_1 \notin V_2$ since it is an out-neighbour of $y_1$. This implies $v_1 \in V_1$. As $v_2$ does not dominate $X$, there is some vertex in $X$, say $x_1$ that dominates $v_2$. Note that $x_1$ dominates $v_1$ by definition of $V_1$. Let $y_2$ be the unique out-neighbour of $y_1$ in $Y$.

If $v_1$ dominates $y_2$, we obtain that $D[\{x_1, v_1, v_2, y_1, y_2\}]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12. We may hence suppose that $y_2$ dominates $v_1$. As $Y$ does not dominate $v_1$, this implies that $H_2$ is $\overrightarrow{C_3}$ and the out-neighbour $y_3$ of $y_2$ is dominated by $v_1$. Then $D[\{x_1, v_1, v_2, y_2, y_3\}]$ contains $O_5$ as a subdigraph, a contradiction to Lemma 12. $\square$

The rest of the preparatory results before the main proof of Theorem 7 aims to exclude a collection of tournaments $\mathcal{T}_8$ as induced subdigraphs and another digraph $F$ as a (not necessarily induced) subdigraph. As the proofs of these results contain several common preliminaries, we give them together. While the exact definition of $\mathcal{T}_8$ is postponed, we now give the definition of $F$. Let $F$ be the oriented graph with vertex set $\{u_1, \dots, u_6, x_1, x_2, x_3\}$ such that:

* $\{u_1, \dots, u_6\}$ induces a copy of $TT_6$ the unique acyclic ordering of which is exactly $u_1, \dots, u_6$, and

* for every $i \in [3]$, $F$ contains the arcs $u_{2i}x_i$ and $x_iu_{2i-1}$.

See Figure 6 for an illustration of $F$.

<figure><img src="image_21.png" /><figcaption>Figure 6: The oriented graph $F$.</figcaption></figure>

We let $\mathcal{F}$ be the set of tournaments $T$ with vertex set $V(T) = V(F)$ and such that $A(F) \subseteq A(T)$. Note that $\mathcal{F}$ contains $2^{15}$ tournaments since $F$ has exactly 15 pairs of non-adjacent vertices. Four of them are of special interest and we denote them by $T^1, \dots, T^4$. We give their adjacency matrices in Appendix A.

**Lemma 19.** None of the tournaments in $\mathcal{F} \setminus \{T^1, T^2, T^3, T^4\}$ is a subdigraph of a 3-dicritical semi-complete digraph.
*Proof.* For every tournament $T \in \mathcal{F}$, we check, using the code of Appendix B.1, if it contains $\vec{C}_3 \Rightarrow \vec{C}_3$ as a subdigraph or if it admits no uv-colouring for an arc uv. This is always the case except when $T \in \{T^1, T^2, T^3, T^4\}$. The claim then follows by Lemmas 10 and 18. □

Let $F^+$ be the oriented graph obtained from $F$ by adding a vertex $u_0$ and the arcs of $\{u_0u_i \mid i \in [6]\}$. Analogously, let $F^-$ be the oriented graph obtained from $F$ by adding a vertex $u_7$ and the arcs of $\{u_iu_7 \mid i \in [6]\}$. See Figure 7 for an illustration.

<figure><img src="image_22.png" /><figcaption>Figure 7: The oriented graphs $F^+$ (left) and $F^-$ (right).</figcaption></figure>

**Lemma 20.** Let $D$ be a 3-dicritical semi-complete digraph. Then $D$ does not contain a digraph in $\{F^+, F^-\}$ as a subdigraph.

*Proof.* Observe that the digraph obtained from $F^-$ by reversing all its arcs is isomorphic to $F^+$. As the digraph obtained from a 3-dicritical, semi-complete digraph by reversing all arcs is 3-dicritical and semi-complete, it suffices to prove the statement for $F^+$.

In order to do so, suppose for the sake of a contradiction, that there is a 3-dicritical semi-complete digraph $D$ containing $F^+$. By Lemma 19, $D - u_0$ contains some $T' \in \{T^1, T^2, T^3, T^4\}$. Now consider the collection $\mathcal{T}$ of tournaments on $\{u_0, \dots, u_6, v_1, v_2, v_3\}$ that have one of $T^1, T^2, T^3, T^4$ as a labelled subdigraph and in which $u_0$ dominates $\{u_1, \dots, u_6\}$. Observe that by assumption, $D$ contains a tournament in $\mathcal{T}$ as a spanning subdigraph. Further, $\mathcal{T}$ contains exactly $4 \times 2^3 = 32$ digraphs. Using the code in Appendix B.2, we check that each of them contains $\vec{C}_3 \Rightarrow \vec{C}_3$ or contains an arc uv with no uv-colouring. We conclude that the same holds for $D$, a contradiction to Lemmas 10 or 18. □

We are now ready to show that 3-dicritical semi-complete digraphs do not contain large transitive tournaments as induced subdigraphs.

**Lemma 21.** Let $D$ be a 3-dicritical semi-complete digraph. Then $D$ does not contain $TT_8$ as an induced subdigraph.

*Proof.* For a contradiction, assume that $D = (V, A)$ is a 3-dicritical semi-complete digraph containing $TT_8$ as an induced subdigraph. We will prove that $D$ contains $F^+$ or $F^-$, which is a contradiction to Lemma 20.

Let $S \subseteq V$ be such that $D[S]$ is isomorphic to $TT_8$. Let $v_1, \dots, v_8$ be the unique acyclic ordering of $S$. By Lemma 11, for every $i \in [7]$, there exists a vertex $x_i \in V \setminus S$ such that $v_iv_{i+1}x_iv_i$ forms an induced directed triangle $C_i$.

Let $H$ be the graph with vertex set $V(H) = [7]$ and that contains an edge linking $i$ and $j$ if $V(C_i) \cap V(C_j) \neq \emptyset$. For any $i, j \in [7]$ with $ij \in E(H)$ and $|i-j| \ge 2$, we have $x_i = x_j$. By Lemma 13, there is no set $\{i, j, k\} \subseteq [7]$ such that $x_i = x_j = x_k$. This yields that $H$ is obtained from a path on 7 vertices by adding a matching. We deduce from Lemma 15 that there is a set $I \subseteq [7]$ with $|I| = 3$ such that the following hold:

(a) $\{1, 7\} \setminus I \neq \emptyset$,
(b) $C_i$ and $C_j$ are vertex-disjoint for all $\{i, j\} \subseteq I$.

This shows that $D$ contains $F^+$ or $F^-$, yielding a contradiction to Lemma 20. $\square$

Given an integer $k$ and a semi-complete digraph $D$, a $k$-extension of $D$ is a semi-complete digraph on $n(D)+k$ vertices containing $D$ as an induced subdigraph. Given a set $S$ of semi-complete digraphs, a $k$-extension of $S$ is a semi-complete digraph that is a $k$-extension of some $D \in S$. We are now ready to prove that no 3-dicritical semi-complete digraph contains $F$ as a subdigraph.

**Lemma 22.** Let $D$ be a 3-dicritical semi-complete digraph. Then $D$ does not contain $F$ as a subdigraph.

*Proof.* By Lemma 19, it remains to show that $D$ does not contain a graph in $\{T^1, T^2, T^3, T^4\}$ as a subdigraph. Assume for a contradiction that $D$ contains at least one of $\{T^1, T^2, T^3, T^4\}$ as a subtournament.

We use the code in Appendix B.3. In a first part, we compute the set $\mathcal{L}$ of all semi-complete digraphs $L$ on nine vertices such that each of the following holds:

(i) $L$ contains some $T \in \{T^1, T^2, T^3, T^4\}$ as a subdigraph,

(ii) $L$ does not contain any digraph in $\{\overrightarrow{S_4}, \overrightarrow{K_2} \Rightarrow \overrightarrow{K_2}, \overrightarrow{K_2} \Rightarrow \overrightarrow{C_3}, \overrightarrow{C_3} \Rightarrow \overrightarrow{K_2}, \overrightarrow{C_3} \Rightarrow \overrightarrow{C_3}, O_4, O_5\}$ as a subdigraph,

(iii) $L$ admits a uv-colouring for every arc $uv \in A(L)$, and

(iv) $L$ does not contain $TT_8$ as an induced subdigraph.

By Lemmas 10, 12, 16, 17, and 18, we know that $D$ contains some $L \in \mathcal{L}$ as an induced subdigraph. In the second part of the code, we check that every 2-extension $L'$ of $\mathcal{L}$ does not satisfy at least one of the properties (ii), (iii) and (iv).

This shows, by Lemmas 10, 12, 16 and 18, that either $D \in \mathcal{L}$ or $D$ is a 1-extension of $\mathcal{L}$. Finally, we check that every $L \in \mathcal{L}$ has dichromatic number at most two, and that every 1-extension $L'$ satisfying (ii), (iii) and (iv) has dichromatic number at most two. This yields a contradiction. $\square$

We now give the definition of $\mathcal{T}_8$ and show that no digraph in $\mathcal{T}_8$ can be contained in a 3-dicritical semi-complete digraph as an induced subdigraph. Let $\mathcal{T}_8$ be the set of tournaments obtained from $TT_8$ by reversing exactly one arc. Observe that $TT_8$ belongs to $\mathcal{T}_8$.

**Lemma 23.** Let $D$ be a 3-dicritical semi-complete digraph. Then $D$ does not contain any digraph in $\mathcal{T}_8$ as an induced subdigraph.

*Proof.* Assume for a contradiction that $D$ contains some $T' \in \mathcal{T}_8$ as an induced subtournament. Let $X \subseteq V(T)$ be such that $D[X]$ is isomorphic to $T'$. By definition of $\mathcal{T}_8$, let $x_1, \dots, x_8$ be an ordering of $X$ such that $D$ contains every arc $x_i x_j$ when $i < j$, except for exactly one pair $\{k, \ell\}$, $k < \ell$.

Assume first that $k = \ell - 1$. Then observe that $T'$ is isomorphic to $TT_8$, with the acyclic ordering obtained from $x_1, \dots, x_8$ by swapping $x_\ell$ and $x_{\ell-1}$. This contradicts Lemma 21.

Henceforth assume that $k \le \ell - 2$. If $k \ge 2$ and $\ell \le 7$ then $D[\{x_1, x_k, x_{\ell-1}, x_\ell, x_8\}]$ is isomorphic to $O_5$, a contradiction to Lemma 12. Henceforth we assume that $k = 1$ or $\ell = 8$. By directional duality, we assume without loss of generality that $k = 1$. Let $S$ be the transitive induced subtournament of $D$ on vertices $X \setminus \{x_1, x_2, x_\ell\}$. We denote its acyclic ordering by $y_1, \dots, y_5$, which exactly corresponds to $x_3, \dots, x_{\ell-1}, x_{\ell+1}, \dots, x_8$. By Lemma 11, for every $k \in [4]$, there exists a vertex $z_k$ such that $y_k y_{k+1} z_k y_k$ forms a directed triangle $C_k$. As $S$ is induced, $z_k$ must be in $V \setminus V(S)$. Moreover, $z_k \notin \{x_1, x_2, x_\ell\}$ because both $X \setminus \{x_1\}$ and $X \setminus \{x_\ell\}$ are acyclic.

Let $H$ be the graph with vertex set $V(H) = [4]$ and that contains an edge linking $i$ and $j$ if $V(C_i) \cap V(C_j) \ne \emptyset$. For any $i, j \in [4]$ with $ij \in E(H)$ and $|i-j| \ge 2$, we have $z_i = z_j$. By Lemma 13,
there is no set {$h, i, j$} $\subseteq$ [4] such that $z_i = z_j = z_h$. This yields that $H$ is obtained from a path on 4 vertices by adding a matching containing at most 2 edges. Hence $H$ contains two non-adjacent vertices, corresponding to two disjoint directed triangles $C_i$ and $C_j$ in $D$. Together with the directed cycle $C_h = x_1x_2x_\ell$, we deduce that $D$ contains $F$ as a subdigraph. This contradicts Lemma 22. $\square$

We have now proved all necessary structural properties of 3-dicritical semi-complete digraphs. The following result contains the decisive step of the proof and it requires heavy computation. For every $i \in [7]$, let $\mathcal{D}_i$ be the set of semi-complete digraphs $D$ such that each of the following holds:

* the maximum acyclic set $S \subseteq V(D)$ of $D$ has size exactly $i$,

* for every arc $uv$ of $D$, $D$ admits a $uv$-colouring,

* $D$ does not contain any digraph of $\{\overrightarrow{S_4}, \overrightarrow{K_2} \Rightarrow \overrightarrow{K_2}, \overrightarrow{K_2} \Rightarrow \overrightarrow{C_3}, \overrightarrow{C_3} \Rightarrow \overrightarrow{K_2}, \overrightarrow{C_3} \Rightarrow \overrightarrow{C_3}, O_4, O_5, F\}$ as a subdigraph,

* $D$ does not contain any digraph of $\mathcal{T}_8$ as an induced subdigraph,

**Lemma 24.** The 3-dicritical digraphs in $\bigcup_{i=1}^7 \mathcal{D}_i$ are exactly $\overrightarrow{K_3}, \mathcal{H}_5$, and $\mathcal{P}_7$.

*Proof.* For every $i \in [7]$, we compute $\mathcal{D}_i$ by starting from the singleton $\{TT_i\}$ which is clearly the only digraph in $\mathcal{D}_i$ on at most $i$ vertices. Using the code in Appendix B.4, we first successively compute the digraphs in $\mathcal{D}_i$ on $j \ge i$ vertices by generating every possible 1-extension of the digraphs in $\mathcal{D}_i$ on $j-1$ vertices, and saving only the ones satisfying the conditions on $\mathcal{D}_i$. When $j$ is large enough, it turns out that the set of digraphs in $\mathcal{D}_i$ on $j$ vertices is empty, implying that $\mathcal{D}_i$ is finite.

We then consider every digraph $D \in \mathcal{D}_i$ and check whether $D$ is 2-dicolourable. When it is not, since it admits a $uv$-colouring for every arc $uv$, we conclude that $D$ is 3-dicritical. $\square$

We are now ready to conclude the proof of Theorem 7.

*Proof.* By Lemmas 10, 12, 16, 17, 18, 22, and 23, we have that every 3-dicritical semi-complete digraph that is not contained in $\bigcup_{i=1}^7 \mathcal{D}_i$ is one of $\overrightarrow{W_3}, \mathcal{R}(\overrightarrow{K_2}, \overrightarrow{K_2}), \mathcal{R}(\overrightarrow{K_2}, \overrightarrow{C_3}), \mathcal{R}(\overrightarrow{C_3}, \overrightarrow{K_2})$, and $\mathcal{R}(\overrightarrow{C_3}, \overrightarrow{C_3})$. The statement then follows directly from Lemma 24. $\square$

# 5 Maximum number of arcs in 3-dicritical digraphs

This section is devoted to the proof of Theorem 9. We need a collection of intermediate results. We first show that the bidirected part of a 3-dicritical digraph is a forest unless $D$ is a bidirected odd cycle.

**Proposition 25.** Let $D$ be a 3-dicritical digraph that is not a bidirected odd cycle. Then $B(D)$ is a forest.

*Proof.* Assume for a contradiction that $B(D)$ is not a forest. Then it contains a cycle $C = u_1u_2\dots u_pu_1$. Let $\overleftrightarrow{C}$ be the bidirected cycle in $D$ corresponding to $C$. The cycle $C$ cannot be odd, for otherwise $\overleftrightarrow{C}$ would be a bidirected odd cycle, and $D = \overleftrightarrow{C}$ because a bidirected odd cycle is 3-dicritical, a contradiction. Hence $C$ is an even cycle. By Lemma 10, there exists a 2-dicolouring $\phi$ of $D \setminus \{u_1u_p\}$. Necessarily, $u_1$ and $u_p$ are coloured differently because there is a bidirected path of odd length between $u_1$ and $u_p$. Thus $\phi$ is a 2-dicolouring of $D$, a contradiction. $\square$

For the remainder of this section we need a few specific definitions. Let $T$ be a tree and $V_3(T)$ be the set of vertices of degree at least 3 in $T$. Two vertices $u, v \in V(T)$ form an *odd pair* if they are non-adjacent and $\text{dist}_T(u, v)$ is odd, where $\text{dist}_T(u, v)$ denotes the length of the unique path between
u and v in T. The set of odd pairs of T is denoted by OP(T) and its cardinality is denoted by op(T). We finally define the dearth of T as follows:

$$ \mathrm{dearth}(T) = \sum_{v \in V_3(T)} \frac{1}{6} d(v)(d(v) - 1) + \mathrm{op}(T). $$

We first prove that the dearth of a tree is always at least a fraction of its order.

**Lemma 26.** Let T be a tree on n vertices for some positive integer n. Then dearth(T) ≥ $\frac{1}{3}n - 1$.

*Proof.* For the sake of a contradiction, suppose that T is a counterexample to the statement whose number of vertices is minimum. Clearly, we have $n \ge 4$. The following claim excludes a collection of simple structures of T.

**Claim 27.** T is neither a path nor a tree.

*Proof of the claim.* The statement follows from the following simple case distinction.

**Case 1:** T is a path of even length.

For every odd $i \in \{1, \dots, n-3\}$, as $n \ge 4$, there are exactly i distinct pairs of vertices at distance exactly $n-i$ in T. Hence dearth(T) ≥ op(T) = $\sum_{i=1}^{\frac{n-2}{2}} (2i - 1) = (\frac{n-2}{2})^2 \ge \frac{1}{3}n - 1$.

**Case 2:** T is a path of odd length.

For every odd $i \in \{1, \dots, n-2\}$, as $n \ge 4$, there are exactly i distinct pairs of vertices at distance exactly $n-i$ in T. Hence dearth(T) ≥ op(T) = $\sum_{i=1}^{\frac{n-3}{2}} 2i = (\frac{n-3}{2})(\frac{n-1}{2}) \ge \frac{1}{3}n - 1$.

**Case 3:** T is a star on $n \ge 4$ vertices.

As $n \ge 4$, we obtain that dearth(T) is exactly $\frac{1}{6}(n-1)(n-2)$, and so dearth(T) ≥ $\frac{1}{3}n - 1$.

In either case, we obtain a contradiction to the choice of T.

◇

By Claim 27, we obtain that T is neither a path nor a star. In particular, it follows that T contains an edge uv such that $d_T(u) \ge 2$ and $d_T(v) \ge 3$. Let $v_1, \dots, v_r$ be the neighbours of v in T, where $v_1 = u$ and $r = d_T(v) \ge 3$. For each $i \in [r]$, let $T_i$ be the component of T - v containing $v_i$. By the choice of T, we have dearth($T_i$) ≥ $\frac{1}{3}n(T_i) - 1$. Since the $T_i$s are pairwise disjoint and none of them contains v, and because u has a neighbour in $T_1$ at distance exactly 3 from $v_2, \dots, v_r$ we obtain:

$$ \begin{aligned} \mathrm{dearth}(T) &\ge \sum_{i=1}^{r} \mathrm{dearth}(T_i) + \frac{1}{6}r(r-1) + (r-1) \\ &\ge \frac{1}{3}(n(T)-1) - r + \frac{1}{6}r(r-1) + (r-1) \\ &\ge \frac{1}{3}n(T) - 1, \end{aligned} $$

where in the last inequality we used $r \ge 3$. This contradicts the choice of T.

□

**Lemma 28.** Let D be a 3-dicritical digraph distinct from $\{\overleftrightarrow{K}_3, \overleftrightarrow{W}_3\}$ and $\overleftrightarrow{T}$ be a bidirected tree contained in D. Then we have

$$ |\{\{u, v\} \subseteq V(T) | \{uv, vu\} \cap A(D) = \emptyset\}| \ge \mathrm{dearth}(T). $$
Proof. Set $\mathcal{O} = \{\{u, v\} \subseteq V(T) \mid \{uv, vu\} \cap A(D) = \emptyset\}$. For every vertex $v \in V_3(T)$, let $\mathcal{O}_v = \mathcal{O} \cap (N_T(v) \times N_T(v))$. Finally let $\mathcal{O}_{\text{odd}} = \mathcal{O} \cap \text{OP}(T)$.

Let us first show that these sets are pairwise disjoint. Let $u, v \in V_3(T)$ be two vertices of degree at least 3 in $T$. Since $T$ is a tree, we have that $N_T(u) \cap N_T(v)$ contains at most one vertex, implying that $\mathcal{O}_u \cap \mathcal{O}_v = \emptyset$. Also note that vertices in $N_T(v)$ are at distance exactly 2 from each other, so $\mathcal{O}_v \cap \mathcal{O}_{\text{odd}} = \emptyset$. This implies

$$|\mathcal{O}| \geq \sum_{v \in V_3(T)} |\mathcal{O}_v| + |\mathcal{O}_{\text{odd}}|.$$

Hence it is sufficient to prove $|\mathcal{O}_v| \geq \frac{1}{6}d_T(v)(d_T(v) - 1)$ for every $v \in V_3(T)$ and $\mathcal{O}_{\text{odd}} = \text{OP}(T)$ to prove Lemma 28.

Let $v \in V_3(T)$ and $u, x, z$ be three distinct vertices in $N_T(v)$. We claim that $D[\{u, x, z\}]$ contains at most two arcs. If this is not the case, then $D[\{u, x, z\}]$ contains a digon, a directed triangle or a transitive tournament on three vertices. This implies that $D[\{u, x, z, v\}]$ contains $\overrightarrow{K_3}, \overrightarrow{W_3}$ or $O_4$. By Theorem 7 and Lemma 16, in each case, we obtain a contradiction to the choice of $D$. Since this holds for every choice of three distinct vertices in $N_T(v)$ and each pair of vertices in $N_T(v)$ is contained in $d_T(v) - 2$ triples, we deduce the following inequality

$$m(D[N_T(v)]) \cdot (d_T(v) - 2) = \sum_{\substack{X \subseteq N_T(v), \\ |X|=3}} m(D[X]) \leq 2 \cdot \binom{d_T(v)}{3},$$

implying that $m(D[N_T(v)]) \leq \frac{1}{3}d_T(v)(d_T(v) - 1)$. Therefore, we obtain $|\mathcal{O}_v| = \binom{d_T(v)}{2} - m(D[N_T(v)]) \geq \frac{1}{6}d_T(v)(d_T(v) - 1)$ as desired.

To show $\mathcal{O}_{\text{odd}} = \text{OP}(T)$, it is sufficient to show that if $\{u, v\}$ is an odd pair then $\{uv, vu\} \cap A(D) = \emptyset$. Assume this is not the case, then by Lemma 10 $D' = D \setminus \{uv, vu\}$ admits a 2-dicolouring $\phi$ in which $\phi(u) = \phi(v)$, a contradiction since $u$ and $v$ are connected by a bidirected odd path in $D'$. This shows the claim. $\square$

We are now ready to prove Theorem 9 that we first restate here for convenience.

**Theorem 9.** If $D$ is a 3-dicritical digraph distinct from $\overrightarrow{K_3}$ and $\overrightarrow{W_3}$, then $m(D) \leq \binom{n}{2} + \frac{2}{3}n$.

Proof. Let $D$ be such a digraph. If $D$ is a bidirected odd cycle, we have $n \geq 5$ and hence $D$ has $2n \leq \binom{n}{2} + \frac{2}{3}n$ arcs, so the result trivially holds. Henceforth assume $D$ is not a bidirected cycle. Then, by Proposition 25, $B(D)$ is a forest. Let $T_1, \dots, T_s$ be the connected components of $B(D)$. For every $i \in [s]$, the number of digons in $D[V(T_i)]$ is exactly $n(T_i) - 1$, whereas the number of pairs of non-adjacent vertices is at least $\text{dearth}(T_i)$ by Claim 28. Hence, since there is no digon between the $T_i$s, we obtain

$$ \begin{align*} m(D) &\leq \binom{n}{2} + \sum_{i=1}^{s} ((n(T_i) - 1) - \text{dearth}(T_i)) \\ &\leq \binom{n}{2} + \sum_{i=1}^{s} \left( (n(T_i) - 1) - \left(\frac{1}{3}n(T_i) - 1\right) \right) \quad \text{by Claim 26} \\ &= \binom{n}{2} + \frac{2}{3}n, \end{align*} $$

which concludes the proof. $\square$
# 6 Conclusion

In this paper, we showed that the number of 3-dicritical semi-complete digraphs is finite and with a computer-assisted proof, we gave a full characterization of them. This result seems to be only the tip of an iceberg, and natural generalizations in several directions can be considered.

First, the conjecture of Hoshino and Kawarabayashi on the maximum density of 3-dicritical oriented graphs remains widely open.

We believe that almost all 3-dicritical digraphs are sparser than tournaments. We thus propose the following conjecture which would imply Theorem 6 and asymptotically improve on Theorem 9.

**Conjecture 29.** There is only a finite number of 3-dicritical digraphs $D$ on $n$ vertices that satisfy $m(D) \ge \binom{n}{2}$.

It is an interesting challenge to generalize the results obtained in this article to $k \ge 4$. In particular, we would be interested in a confirmation of the following statement.

**Conjecture 30.** For every $k \ge 4$, there is only a finite number of $k$-dicritical semi-complete digraphs.

Finally, it is also natural to consider a different notion of criticality. A digraph $D$ is called 3-vertex-dicritical if $D$ is not 3-dicolourable, but $D - v$ is for all $v \in V(D)$. Observe that every 3-dicritical digraph is 3-vertex-dicritical, but the converse is not necessarily true. One can hence wonder whether an analogue of Theorem 6 is true for 3-vertex-dicritical digraphs. However, this turns out not to be the case. Chen et al. proved in [6] that it is NP-hard to decide whether a given tournament is 2-dicolourable. An infinite collection of 3-vertex-dicritical tournaments can easily be derived from their proof.

# References

[1] P. Aboulker. Personal communication, 2023.

[2] P. Aboulker, T. Bellitto, F. Havet, and C. Rambaud. On the minimum number of arcs in $k$-dicritical oriented graphs. *arXiv preprint arXiv:2207.01051*, 2022.

[3] J. Bang-Jensen, T. Bellitto, T. Schweser, and M. Stiebitz. Hajós and Ore constructions for digraphs. *The Electronic Journal of Combinatorics*, 27(1), Mar. 2020.

[4] J. Bang-Jensen and G. Z. Gutin. *Digraphs: Theory, Algorithms and Applications*. Springer-Verlag, London, 2nd edition, 2009.

[5] T. Bellitto, N. Bousquet, A. Kabela, and T. Pierron. The smallest 5-chromatic tournament. *Mathematics of Computation*, 93(345):443–458, 2024.

[6] X. Chen, X. Hu, and W. Zang. A min-max theorem on tournaments. *SIAM Journal on Computing*, 37(3):923–937, Jan. 2007.

[7] R. Diestel. *Graph Theory*. Graduate texts in mathematics. Springer, Berlin, Germany, 5th edition, June 2017.

[8] G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. *Journal of the London Mathematical Society*, s1-27(1):85–92, 1952.

[9] G. A. Dirac. Circuits in critical graphs. *Monatshefte für Mathematik*, 59(3):178–187, 1955.
[10] G. A. Dirac. A theorem of R. L. Brooks and a conjecture of H. Hadwiger. *Proceedings of the London Mathematical Society*, s3-7(1):161-195, 1957.

[11] G. A. Dirac. On the structure of k-chromatic graphs. *Mathematical Proceedings of the Cambridge Philosophical Society*, 63(3):683-691, 1967.

[12] P. Erdos. Problems and results in chromatic graph theory. *Proof techniques in graph theory*, pages 27-35, 1969.

[13] T. Gallai. Kritische Graphen I. *Publications of the Mathematical Institute of the Hungarian Academy of Sciences*, 8:165-192, 1963.

[14] T. Gallai. Kritische Graphen II. *Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei*, 8:373-395, 1963.

[15] G. Hajós. Über eine Konstruktion nicht $n$-farbbarer Graphen. *Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg. Mathematisch-Naturwissenschaftliche Reihe*, 10:116-117, 1961.

[16] F. Havet, L. Picasarri-Arrieta, and C. Rambaud. On the minimum number of arcs in 4-dicritical oriented graphs. *arXiv preprint arXiv:2306.10784*, 2023.

[17] R. Hoshino and K.-i. Kawarabayashi. The edge density of critical digraphs. *Combinatorica*, 35(5):619-631, 2015.

[18] A. V. Kostochka and M. Stiebitz. On the number of edges in colour-critical graphs and hypergraphs. *Combinatorica*, 20(4):521-530, Apr. 2000.

[19] A. V. Kostochka and M. Stiebitz. A new lower bound on the number of edges in colour-critical graphs and hypergraphs. *Journal of Combinatorial Theory, Series B*, 87(2):374-402, 2003.

[20] A. V. Kostochka and M. Stiebitz. The minimum number of edges in 4-critical digraphs of given order. *Graphs and Combinatorics*, 36(3):703-718, May 2020.

[21] A. V. Kostochka and M. Yancey. Ore's conjecture on color-critical graphs is almost true. *Journal of Combinatorial Theory, Series B*, 109:73-101, Nov. 2014.

[22] M. Krivelevich. On the minimal number of edges in color-critical graphs. *Combinatorica*, 17(3):401-426, 1997.

[23] C.-H. Liu and L. Postle. On the minimum edge-density of 4-critical graphs of girth five. *Journal of Graph Theory*, 86(4):387-405, 2017.

[24] C. Luo, J. Ma, and T. Yang. On the maximum number of edges in k-critical graphs. *Combinatorics, Probability and Computing*, 32(6):900-911, July 2023.

[25] V. Neumann-Lara. The dichromatic number of a digraph. *Journal of Combinatorial Theory, Series B*, 33(3):265-270, 1982.

[26] V. Neumann-Lara. The 3 and 4-dichromatic tournaments of minimum order. *Discrete Mathematics*, 135(1):233-243, 1994.

[27] L. Postle. On the minimum number of edges in triangle-free 5-critical graphs. *European Journal of Combinatorics*, 66:264-280, 2017. Selected papers of EuroComb15.

[28] M. Stiebitz. Subgraphs of colour-critical graphs. *Combinatorica*, 7:303-312, 1987.

[29] B. Toft. On the maximal number of edges of critical $k$-chromatic graphs. *Studia Scientiarum Mathematicarum Hungarica*, 5:461-470, 1970.
A The tournaments $T^1, \dots, T^4$

We give the adjacency matrices of $T^1, T^2, T^3$ and $T^4$.

$$ T^1: \quad \begin{array}{c} \begin{array}{ccccccccc} u_1 & u_2 & u_3 & u_4 & u_5 & u_6 & x_1 & x_2 & x_3 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \end{array} \\ \begin{array}{c} u_1 \\ u_2 \\ u_3 \\ u_4 \\ u_5 \\ u_6 \\ x_1 \\ x_2 \\ x_3 \end{array} \end{array} $$

$$ T^2: \quad \begin{array}{c} \begin{array}{ccccccccc} u_1 & u_2 & u_3 & u_4 & u_5 & u_6 & x_1 & x_2 & x_3 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 \end{array} \\ \begin{array}{c} u_1 \\ u_2 \\ u_3 \\ u_4 \\ u_5 \\ u_6 \\ x_1 \\ x_2 \\ x_3 \end{array} \end{array} $$

$$ T^3: \quad \begin{array}{c} \begin{array}{ccccccccc} u_1 & u_2 & u_3 & u_4 & u_5 & u_6 & x_1 & x_2 & x_3 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 \end{array} \\ \begin{array}{c} u_1 \\ u_2 \\ u_3 \\ u_4 \\ u_5 \\ u_6 \\ x_1 \\ x_2 \\ x_3 \end{array} \end{array} $$

$$ T^4: \quad \begin{array}{c} \begin{array}{ccccccccc} u_1 & u_2 & u_3 & u_4 & u_5 & u_6 & x_1 & x_2 & x_3 \\ \hline 0 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 1 \end{array} \\ \begin{array}{c} u_1 \\ u_2 \\ u_3 \\ u_4 \\ u_5 \\ u_6 \\ x_1 \\ x_2 \\ x_3 \end{array} \end{array} $$
# B Code used in the proof of Theorem 7

This appendix contains the code used in the proof of Theorem 7. In Appendix B.0, we give a collection of useful subroutines we use in the main part of the code. In Appendices B.1, B.2, B.3, and B.4, we give the code use in the proofs of Lemmas 19 and 20, and Lemmas 22 and 24, respectively.

## B.0 Preliminaries for the code

In the following code, we give a collection of subroutines we use in our code.

```python
1 # The following function displays a progress bar
2 def printProgressBar(iteration, total):
3     percent = ("{0:.1f}").format(100 * (iteration / float(total)))
4     filledLength = int(50 * iteration // total)
5     bar = "#" * filledLength + "-" * (50 - filledLength)
6     print(f"\rProcess: |{bar}| {percent}% Complete", end="\r")
7 # Print New Line on Complete
8     if iteration == total:
9         print()
10
11 # k,n : integers such that k < 3**n
12 # Returns: the decomposition of k in base 3 of length n
13 def ternary(k,n):
14     b = 3**(n-1)
15     res=""
16     for i in range(n):
17         if(k >= 2*b):
18             k -= 2*b
19             res = res + "2"
20         elif(k >= b):
21             k -= b
22             res = res + "1"
23         else:
24             res = res + "0"
25     b /= 3
26     return res
27
28 # d: DiGraph
29 # u: vertex
30 # v: vertex
31 # Returns: True if and only if d contains a directed path from u to v
def contains_directed_path(d,u,v):
33     to_be_treated = [u]
34     i=0
35     while(len(to_be_treated) != i):
36         x = to_be_treated[i]
37         if(x==v):
38             return True
39         for y in d_neighbors_out(x):
40             if (not y in to_be_treated):
41                 to_be_treated.append(y)
42     i+=1
43     return False
44
45 # d: DiGraph
```
```python
# u: vertex of d
# v: vertex of d
# currentColouring: partial 2-dicounting with colours {0,1} of d such that
currentColouring[u] = currentColouring[v] = 0
# Returns: True if and only if currentColouring can be extended into a 2-
dicounting of d with no monochromatic directed path from u to v.
def can_be_subgraph_of_3_dicritical_aux(d, u, v, currentColouring):
    #build the colour classes
colours = {}
colours[0] = []
colours[1] = []

for (x, i) in currentColouring.items():
    colours[i].append(x)

#check whether both colour classes are acyclic
for i in range(2):
    d_i = d.subgraph(colours[i])
    if(not d_i.is_directed_acyclic):
        return False

#check whether there is a monochromatic directed path from u to v
d_0 = d.subgraph(colours[0])
if(contains_directed_path(d_0, u, v)):
    return False

#check whether currentColouring is partial
if(len(currentColouring) == d.order):
    return True

else:
    #find a vertex x that is not coloured yet
    x = len(currentColouring)
    while(x in currentColouring):
        x-=1
        #check recursively whether currentColouring can be extended to x
        for i in range(2):
            currentColouring[x] = i
            if还可以在下面的if语句中添加更多的if语句:
                if还可以在下面的if语句中添加更多的if语句:
                    return True
            currentColouring.pop(x, None)
        return False

# d: DiGraph
# forbidden_subtournaments: list of DiGraphs
# Returns: True if and only if d is {forbidden_subdigraphs}-free, {forbidden_induced_subdigraphs}-free and, for every arc (u,v) of d, d admits a uv-colouring.
def can_be_subgraph_of_3_dicritical(d, forbidden_subdigraphs,
                                     forbidden_induced_subdigraphs):
    #check whether d contains a forbidden subgraph
    for T in forbidden_subdigraphs:
        if(d.subgraph_search(T, False) != None):
            return False

    #check whether d contains a forbidden induced subgraph
    for T in forbidden_induced_subdigraphs:
        if(d.subgraph_search(T, True) != None):
            return False

    #check for every arc uv if d admits a uv-colouring.
    for e in dEdges():
```
```python
d_aux = DiGraph(len(d vertices))
d_aux.add_edges(d_edges())
d_aux.delete_edge(e)
current colouring = {}
current colouring [e [0]] = 0
current colouring [e [1]] = 0
if (not can be subgraph of 3 dicritical_aux (d_aux, e [0], e [1]) ,
current colouring ):
    return False
return True

# d: DiGraph
# Returns: True if and only if d is 2-dicolourable
def is_two_dicolourable (d):
    n = d.order()
    for bipartition in range (2**n):
        #build the binary word corresponding to the bipartition
        binary = bin (bipartition) [2:]
        while (len (binary) <(n)):
            binary = "0" + binary
        #build the bipartition
        V1 = []
        V2 = []
        for v in range (n):
            if (binary [v] == '0'):
                V1.append (v)
            else:
                V2.append (v)
        #check whether (V1, V2) is actually a dicolouring
        d1 = d.subgraph (V1)
        d2 = d.subgraph (V2)
        if (d1.is_directed_acyclic () and d2.is_directed_acyclic ()):
            return True
        return False

#C3_C3 is the digraph made of two disjoint directed triangles, the vertices
# of one dominating the vertices of the other
C3_C3 = DiGraph (6)
for i in range (3):
    C3_C3.add_edge (i, (i+1)%3)
    C3_C3.add_edge (i+3, ((i+1)%3)+3)
for j in range (3, 6):
    C3_C3.add_edge (i, j)

#F is the digraph on nine vertices made of a TT6 u1,...,u6 and the arcs of
# the directed triangles u1u2x1u1, u3u4x2u3, u5u6x3u5.
F = DiGraph (9)
for i in range (6):
    for j in range (i):
        F.add_edge (j, i)
F.add_edge (6, 0)
F.add_edge (1, 6)
F.add_edge (7, 2)
F.add_edge (3, 7)
F.add_edge (8, 4)
```
F.add_edge(5,8)

#TT8 is the transitive tournament on 8 vertices
TT8 = DiGraph(8)
for i in range(8):
    for j in range(i):
        TT8.add_edge(j,i)

#reversed_TT8 is the set of tournaments, up to isomorphism, obtained from TT8
by reversing exactly one arc
reversed_TT8 = []
for e in TT8edges():
    rev = DiGraph(8)
    rev.add_edges(TT8edges())
    rev.delete_edge(e)
    rev.add_edge(e[1],e[0])
    check = True
    for T in reversed_TT8:
        check = check and (not T.is_isomorphic(rev))
    if (check):
        reversed_TT8.append(rev)

#K2 is the complete digraph on 2 vertices
K2 = DiGraph(2)
K2.add_edge(0,1)
K2.add_edge(1,0)

#S4 is the bidirected star on 4 vertices
S4 = DiGraph(4)
for i in range(1,4):
    S4.add_edge(i,0)
    S4.add_edge(0,i)

#C3_K2 is the digraph with a directed triangle dominating a digon.
C3_K2 = DiGraph(5)
for i in range(3):
    C3_K2.add_edge(i,(i+1)%3)
    for j in range(3,5):
        C3_K2.add_edge(i,j)
    C3_K2.add_edge(3,4)
    C3_K2.addEdge(4,3)

#K2_C3 is the digraph with a digon dominating a directed triangle
K2_C3 = DiGraph(5)
for i in range(3):
    K2_C3.add_edge(i,(i+1)%3)
    for j in range(3,5):
        K2_C3.add_edge(j,i)
    K2_C3.addEdge(3,4)
    K2_C3.addEdge(4,3)

#K2_K2 is the digraph with a digon dominating a digon
K2_K2 = DiGraph(4)
for i in range(2):
    K2_K2.add_edge(i,(i+1)%2)
```
202 K2_K2.add_edge(i+2, ((i+1)/2)+2)
203 for j in range(2,4):
204     K2_K2.add_edge(i,j)
205
206 #04 and 05 are the obstructions described in the paper.
207 04 = DiGraph(4)
208 for i in range(1,4):
209     04.add_edge(0,i)
210 for i in range(1,3):
211     04.add_edge(i,3)
212 04.add_edge(1,2)
213 04.add_edge(2,1)
214
215 05 = DiGraph(5)
216 for i in range(1,5):
217     05.add_edge(0,i)
218 for i in range(1,4):
219     05.add_edge(i,4)
220 05.add_edge(1,2)
221 05.add_edge(2,3)
222 05.add_edge(3,1)
```

## B.1 The proof of Lemma 19

We here give the code used in the proof of Lemma 19.

*Proof.* For every tournament $T \in \mathcal{F}$, we check, using the following code, if it contains $\vec{C}_3 \Rightarrow \vec{C}_3$ as a subdigraph or if it admits no uv-colouring for an arc uv. This is always the case except when $T \in \{T^1, T^2, T^3, T^4\}$. The Claim then follows by Lemmas 10 and 18. □

```
1 load("tools.sage")
2
3 # binary_code: a string of fifteen characters '0' and '1'
4 # Returns: a tournament of \mathcal{F}. The orientations of the fifteen non-
5 forced arcs correspond to the characters of binary_code.
6 def digraph_blowup_TT3(binary_code):
7     iterator_binary_code = iter(binary_code)
8     d = DiGraph(9)
9     #the vertices 0,...,8 correspond respectively to u_1,...,u_6,x_1,x_2,x_3
10    #add the arcs of the TT_6
11    for i in range(6):
12        for j in range(i):
13            d.add_edge(j,i)
14
15    #add the arcs of the directed triangles
16    for i in range(3):
17        d.add_edge(6+i, 2*i)
18        d.add_edge(2*i+1, 6+i)
19
20    missing_edges=[(6,2),(6,3),(6,4),(6,5),(6,7),(6,8),(7,0),(7,1),(7,4)
21    , (7,5),(7,8),(8,0),(8,1),(8,2),(8,3)]
22    #we orient the missing_edges according to binary_code
23    for e in missing_edges:
```
```python
23 if (next(iterator_binary_code) == '0')):
24     d.add_edge(e[0], e[1])
25 else:
26     d.add_edge(e[1], e[0])
27 return d
28
29 print("Computing all possible candidates of \mathcal{F} for being a
30       subtournament of a 3-dicritical semi-complete digraph...")
31 list_candidates = []
32 list_forbidden_induced_subdigraphs = [C3_C3]
33
34 #print progress bar
35 printProgressBar(0, 2**15)
36
37 for i in range(2**15):
38     binary_value = bin(i)[2:]
39     while (len(binary_value) < 15):
40         binary_value = '0' + binary_value
41     d = digraph_blowup_TT3(binary_value)
42     if (can_be_subgraph_of_3_dicritical(d, [],
43                                     list_forbidden_induced_subdigraphs)):
44         list_candidates.append(d)
45     #update progress bar
46     printProgressBar(i + 1, 2**15)
47
48 print("Number of candidates: ", len(list_candidates), ".")
49 for i in range(len(list_candidates)):
50     print("Candidate ", i+1, ": ")
51     list_candidates[i].export_to_file("T"+str(i+1)+".pajek")
52     print(list_candidates[i].adjacency_matrix())
```

Running this code produces the following output after roughly 2 minutes of execution on a standard desktop computer:

```
1 Computing all possible candidates of \mathcal{F} for being a subtournament of
   a 3-dicritical semi-complete digraph...
2 Process: | ###########################################| 100.0% Complete
3 Number of candidates: 4.
4 Candidate 1 :
5 [0 1 1 1 1 1 0 1 1]
6 [0 0 1 1 1 1 1 1 1]
7 [0 0 0 1 1 1 0 0 0]
8 [0 0 0 0 1 1 0 1 0]
9 [0 0 0 0 0 1 0 1 0]
10 [0 0 0 0 0 0 1 1 1]
11 [1 0 1 1 1 0 0 0 1]
12 [0 0 1 0 0 0 1 0 1]
13 [0 0 1 1 1 0 0 0 0]
14 Candidate 2 :
15 [0 1 1 1 1 1 0 1 1]
16 [0 0 1 1 1 1 1 1 1]
17 [0 0 0 1 1 1 1 0 0]
18 [0 0 0 0 1 1 0 1 0]
19 [0 0 0 0 0 1 0 1 0]
20 [0 0 0 0 0 0 0 1 1]
21 [1 0 0 1 1 1 0 1 0]
22 [0 0 1 0 0 0 0 0 1]
```
23 [0 0 1 1 1 0 1 0 0]
24 Candidate 3 :
25 [0 1 1 1 1 1 0 0 0]
26 [0 0 1 1 1 1 1 0 1]
27 [0 0 0 1 1 1 1 0 1]
28 [0 0 0 0 1 1 1 1 1]
29 [0 0 0 0 0 1 0 0 0]
30 [0 0 0 0 0 0 0 0 1]
31 [1 0 0 0 1 1 0 1 1]
32 [1 1 1 0 1 1 0 0 0]
33 [1 0 0 0 1 0 0 1 0]
34 Candidate 4 :
35 [0 1 1 1 1 1 0 0 1]
36 [0 0 1 1 1 1 1 0 1]
37 [0 0 0 1 1 1 1 0 1]
38 [0 0 0 0 1 1 1 1 0]
39 [0 0 0 0 0 1 0 0 0]
40 [0 0 0 0 0 0 0 0 1]
41 [1 0 0 0 1 1 0 1 0]
42 [1 1 1 0 1 1 0 0 1]
43 [0 0 0 1 1 0 1 0 0]

The graphs in the output are exactly $T_1, T_2, T_3$, and $T_4$.

## B.2 The proof of Lemma 20

We here give the code used in the proof of Lemma 20.

```python
import networkx
load("tools.sage")

list_candidates = []
list_forbidden_induced_subdigraphs = [C3_C3]

# import T1, T2, T3 and T4
for i in range(1,5):
    candidate = DiGraph(9)
    nx = networkx.read_pajek("T"+str(i)+".pajek")
    for e in nxEdges():
        candidate.add_edge(int(e[0]), int(e[1]))
    list_candidates.append candidate

print("We start from the ", len(list_candidates), " candidates on 9 vertices.")

# We want to prove that a 3-dicritical semi-complete digraph does not contain a digraph in {F+,F-}. By directional duality, it is sufficient to prove that it does not contain F+.
# For each candidate computed above, we try to add a new vertex that dominates the transitive tournament, and then we build every possible orientation between this vertex and the three other vertices.
print("Computing for F+...")
list_Fp = []
printProgressBar(0, 8)
for orientation in range(2**3):
    binary = bin(orientation)[2:]
```
```python
while (len(binary) < 3):
    binary = '0' + binary

for T9 in list_candidates:
    iterator = iter(binary)
    T10 = DiGraph(10)
    T10.add_edges(T9_edges())
    for v in range(6):
        T10.add_edge(9, v)
    for v in range(6, 9):
        if (nextupto iterator) == '0'):
            T10.add_edge(v, 9)
        else:
            T10.add_edge(9, v)
    check = can_be_subgraph_of_3_dicritical(T10, [],
                                              list_forbidden_induced_subdigraphs)
    if (check):
        list_Fm.append(T2)
    printProgressBar(orientation + 1, 8)

print("Number of 1-extensions of {T1,T2,T3,T4} containing F+: ", len(list_Fp))
```

Running this code produces the following output after roughly 1 second of execution on a standard desktop computer:

```
We start from the 4 candidates on 9 vertices.
Computing for F+...
Process: |chapter 1 of 100.0% Complete|
Number of 1-extensions of {T1,T2,T3,T4} containing F+: 0
```

## B.3 The proof of Lemma 22

We here give the code used in the proof of Lemma 22.

```python
import networkx
load("tools.sage")

all_candidates = []
current_candidates = []
next_candidates = []

list_forbidden_subdigraphs = [S4, K2_K2, O4, O5, K2_C3, C3_K2, C3_C3]
list_forbidden_induced_subdigraphs = [TT8]

# import the candidates T1, ..., T4 on 9 vertices:
for i in range(1, 5):
    candidate = DiGraph(9)
    nx = networkx.read_pajek("T" + str(i) + ".pajek")
    for e in nx_edges():
        candidate.add_edge(int(e[0]), int(e[1]))
    current_candidates.append candidate

print("We start from the tournaments {T^1,T^2,T^3,T^4} on 9 vertices, and
look for every possible completion of them that is potentially a
subdigraph of a larger 3-dicritical semi-complete digraphs.\n")

all_candidates.extend(current_candidates)
```
```python
22 #completions of T1, ..., T4
23 while(len(current_candidates)>0):
24     for old_D in current_candidates:
25         for e in old_D_edges():
26             #we try to complete old_D by replacing e by a digon. It actually
27             makes sense only if e is not already in a digon.
28             if(not (e[1],e[0],None) in old_D_edges()):
29                 new_D = DiGraph(9)
30                 new_D.add_edges(old_D_edges())
31                 new_D.add_edge(e[1],e[0])
32             #we check whether this completion of old_D is potentially a
33             subdigraph of a larger 3-dicritical semi-complete digraph.
34             check = can_be_subgraph_of_3_dicritical(new_D,
35             list_forbidden_subdigraphs, list_forbidden_induced_subdigraphs)
35             for D in next_candidates:
36                 check = check and (not D.is_isomorphic(new_D))
37             if(check):
38                 next_candidates.append(new_D)
39             all_candidates.append(next_candidates)
40         current_candidates = next_candidates
41     next_candidates = []
42
43 print("--------------------------------")
44 print("There are",len(all_candidates),"possible completions (up to
45 isomorphism) of {T1,T2,T3,T4} that are potentially subdigraphs of a
46 larger 3-dicritical semi-complete digraphs.\n")
47
48 count dic_3 = 0
49 for D in all_candidates:
50     if(not is_two_dicolourable(D)):
51         count dic_3 += 1
52     print(count dic_3, " of them have dichromatic number at least 3. In
53         particular,".count dic_3,"of them are 3-dicritical.\n")
54
55 current_candidates = all_candidates
56 next_candidates = []
57 for n in range(10,12):
58     #computes the extensions on n vertices of {T1,T2,T3,T4}
59     print("--------------------------------")
60     print("Computing "+str(n-9)+"-extensions of the candidates on 9 vertices
61         that are potentially subtournaments of 3-dicritical tournaments (up to
62         isomorphism).")
63     printProgressBar(0, 3**(n-1))
64
65 for orientation in range(3**(n-1)):
66     ternary_code = ternary(orientation,n-1)
67     #build every 1-extension of current_candidates
68     for old_D in current_candidates:
69         new_D = DiGraph(n)
70         new_D.add_edges(old_D_edges())
71     for v in range(n-1):
72         if(ternary_code[v] == '0'):
73             new_D.add_edge(v,n-1)
74         elif(ternary_code[v] == '1'):
```
```python
new_D.add_edge(n-1, v)
else:
    new_D.add_edge(v, n-1)
    new_D.add_edge(n-1, v)
check = can_be_subgraph_of_3_dicritical(new_D,
    list_forbidden_subdigraphs, list_forbidden_induced_subdigraphs)
    for D in next_candidates:
        check = check and (not new_D.is_isomorphic(D))
        if (check):
            next_candidates.append(new_D)
    printProgressBar(orientation+1, 3**(n-1))

print("Number of ", n-9, "-extensions up to isomorphism: ", len(
    next_candidates))
#check if one of the candidates has dichromatic number at least 3.
count dic_3 = 0
for D in next_candidates:
    if (not is_two_dicolourable(D)):
        count dic_3 += 1
print(count dic_3, " of them have dichromatic number at least 3. In
    particular, ", count dic_3, "of them are 3-dicritical. \n")
current_candidates = next_candidates
next_candidates = []
```

Running this code produces the following output after roughly 12 minutes of execution on a standard desktop computer:

1 We start from the tournaments ${T^1, T^2, T^3, T^4}$ on 9 vertices, and look for every possible completion of them that is potentially a subdigraph of a larger 3-dicritical semi-complete digraphs.

2
3
There are 14 possible completions (up to isomorphism) of ${T^1, T^2, T^3, T^4}$ that are potentially subdigraphs of a larger 3-dicritical semi-complete digraphs.

4
5
0 of them have dichromatic number at least 3. In particular, 0 of them are 3-dicritical.

7
8
Computing 1-extensions of the candidates on 9 vertices that are potentially
subtournaments of 3-dicritical tournaments (up to isomorphism).
Process: |########## Complete | 100.0% Complete
10
11
Number of 1-extensions up to isomorphism: 34
12
0 of them have dichromatic number at least 3. In particular, 0 of them are
3-dicritical.

13
14
Computing 2-extensions of the candidates on 9 vertices that are potentially
subtournaments of 3-dicritical tournaments (up to isomorphism).
Process: |########## Complete | 100.0% Complete

15
16
0 of them have dichromatic number at least 3. In particular, 0 of them are
3-dicritical.

18
19
Computing 2-extensions of the candidates on 9 vertices that are potentially
subtournaments of 3-dicritical tournaments (up to isomorphism).
Process: |########## Complete | 100.0% Complete

20
21
Number of 2-extensions up to isomorphism: 0
22
0 of them have dichromatic number at least 3. In particular, 0 of them are
3-dicritical.
## B.4 The proof of Lemma 24

We here give the code used in the proof of Lemma 24.

```python
load("tools.sage")
```

```python
def possible_completions(graph_to_complete, nbVertices,
                         list_forbidden_subdigraphs, list_forbidden_induced_subdigraphs, progress
                         =0):
```

```python
    if (progress == nbVertices - 1):
```

```python
        return [graph_to_complete]
```

```python
else:
```

```python
    result = []
```

```python
    for i in range(3):
```

```python
        # we make a copy of the graph_to_complete
        new_D = DiGraph nbVertices)
```

```python
        new_D.add_edges(graph_to_complete .edges())
```

```python
        # we consider every possible orientation between the vertices (
        nbVertices - 1) and (progress)
```

```python
    if (i==0):
```

```python
        new_D.add_edge nbVertices - 1, progress)
```

```python
    elif (i==1):
```

```python
        new_D.add_edge (progress, nbVertices - 1)
```

```python
    else:
```

```python
        new_D.add_edge (nbVertices - 1, progress)
```

```python
        new_D.add_edge (progress, nbVertices - 1)
```

```python
        # for each of the 3 possible orientations, we check whether the
        obtained digraph is already an obstruction. If it is not, we compute all
        possible completions recursively
```

```python
    if (can_be_subgraph_of_3_dicritical(new_D,
                                     list_forbidden_subdigraphs, list_forbidden_induced_subdigraphs)):
```

```python
        result.extend(possible_completions(new_D, nbVertices,
                                           list_forbidden_subdigraphs, list_forbidden_induced_subdigraphs, progress
                                           +1))
```

```python
    return result
```

```python
    for tt in range(1, 8):
```

```python
        transitive_tournament = DiGraph (tt)
```

```python
    for i in range (tt):
```

```python
        for j in range (i):
```

```python
            transitive_tournament .add_edge (j, i)
```

```python
        next_transitive_tournament = DiGraph (tt + 1)
```

```python
    for i in range (tt + 1):
```

```python
        for j in range (i):
```

```python
            next_transitive_tournament .add_edge (j, i)
```

```python
        list_forbidden_subdigraphs = [S4, K2_K2, O4, O5, K2_C3, C3_K2, C3_C3, F]
```

```python
        list_forbidden_induced_subdigraphs = []
```

```python
    if (tt < 7):
```

```python
        list_forbidden_induced_subdigraphs = [next_transitive_tournament]
```

```python
    else:
```

```python
        list_forbidden_induced_subdigraphs = reversed_TT8
```
```python
print("\n------------------------------------------\n")
print("Generating all 3-dicritical semi-complete digraphs with maximum
acyclic induced subdigraph of size exactly " + str.tt) + ".")
```

```python
n=tt+1
candidates = [transitive_tournament]
next_candidates = []
while (len(candidates)>0):
    print("\nComputing candidates on " + str(n) + " vertices.")
    printProgressBar(0, len(candidates))
    for i in range(len(candidates)):
        old_D = candidates[i]
        new_D = DiGraph(n)
        new_D.add_edges(old_D_edges())
        all_posible_completions_new_D = possible_completions(new_D, n,
                                                        list_forbidden_subdigraphs, list_forbidden_induced_subdigraphs)
        for candidate in all_posible_completions_new_D:
            check = True
            for D in next_candidates:
                check = not D.is_isomorphic candidate)
                if (not check):
                    break
            if (check):
                next_candidates.append candidate)
    printProgressBar(i + 1, len(candidates))
```

```python
#check the candidates that are actually 3-dicritical.
print("We found", len(next_candidates), "candidates on " + str(n) + "
vertices.")
dicriticals = []
for D in next_candidates:
    if (not is_two_dicolourable (D)):
        dicriticals.append(D)
    print(len(dicriticals), " of them are actually 3-dicritical.\n")
for D in dicriticals:
    print("adjacency matrix of a 3-dicritical digraph that we found:")
    print(D adjacency_matrix())

candidates = next_candidates
next_candidates = []
n+=1
```

Running this code produces the following output after roughly 2 hours of execution on a standard desktop computer:

```
Generating all 3-dicritical semi-complete digraphs with maximum acyclic
induced subdigraph of size exactly 1.

Computing candidates on 2 vertices.

Process: |########## Complete | 100.0%
We found 1 candidates on 2 vertices.
0 of them are actually 3-dicritical.
```
Computing candidates on 3 vertices.
Process: | ########################################### | 100.0% Complete
We found 1 candidates on 3 vertices.
1 of them are actually 3-dicritical.

adjacency matrix of a 3-dicritical digraph that we found:
[0 1 1]
[1 0 1]
[1 1 0]

Computing candidates on 4 vertices.
Process: | ########################################### | 100.0% Complete
We found 0 candidates on 4 vertices.
0 of them are actually 3-dicritical.

Generating all 3-dicritical semi-complete digraphs with maximum acyclic
induced subdigraph of size exactly 2.

Computing candidates on 3 vertices.
Process: | ########################################### | 100.0% Complete
We found 5 candidates on 3 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 4 vertices.
Process: | ########################################### | 100.0% Complete
We found 5 candidates on 4 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 5 vertices.
Process: | ########################################### | 100.0% Complete
We found 0 candidates on 5 vertices.
0 of them are actually 3-dicritical.

Generating all 3-dicritical semi-complete digraphs with maximum acyclic
induced subdigraph of size exactly 3.

Computing candidates on 4 vertices.
Process: | ########################################### | 100.0% Complete
We found 13 candidates on 4 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 5 vertices.
Process: | ########################################### | 100.0% Complete
We found 37 candidates on 5 vertices.
1 of them are actually 3-dicritical.
adjacency matrix of a 3-dicritical digraph that we found:
[0 1 1 0 0]
[0 0 1 0 1]
[0 0 0 1 1]
[1 1 0 0 1]
[1 0 1 1 0]
Computing candidates on 6 vertices.
Process: | ########################################### | 100.0% Complete
We found 8 candidates on 6 vertices.
0 of them are actually 3-dicritical.
Computing candidates on 7 vertices.
Process: | ########################################### | 100.0% Complete
We found 1 candidates on 7 vertices.
1 of them are actually 3-dicritical.
adjacency matrix of a 3-dicritical digraph that we found:
[0 1 1 0 0 0 1]
[0 0 1 0 1 1 0]
[0 0 0 1 0 1 1]
[1 1 0 0 0 1 0]
[1 0 1 1 0 0 0]
[1 0 0 0 1 0 1]
[0 1 0 1 1 0 0]
Computing candidates on 8 vertices.
Process: | ########################################### | 100.0% Complete
We found 0 candidates on 8 vertices.
0 of them are actually 3-dicritical.
Generating all 3-dicritical semi-complete digraphs with maximum acyclic induced subdigraph of size exactly 4.
Computing candidates on 5 vertices.
Process: | ########################################### | 100.0% Complete
We found 27 candidates on 5 vertices.
0 of them are actually 3-dicritical.
Computing candidates on 6 vertices.
Process: | ########################################### | 100.0% Complete
We found 116 candidates on 6 vertices.
0 of them are actually 3-dicritical.
Computing candidates on 7 vertices.
Process: | ########################################### | 100.0% Complete
We found 10 candidates on 7 vertices.
0 of them are actually 3-dicritical.
Computing candidates on 8 vertices.
Process: | ########################################### | 100.0% Complete
We found 0 candidates on 8 vertices.
0 of them are actually 3-dicritical.

Generating all 3-dicritical semi-complete digraphs with maximum acyclic
induced subdigraph of size exactly 5.

Computing candidates on 6 vertices.
Process: | ########################################### | 100.0% Complete
We found 49 candidates on 6 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 7 vertices.
Process: | ########################################### | 100.0% Complete
We found 266 candidates on 7 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 8 vertices.
Process: | ########################################### | 100.0% Complete
We found 20 candidates on 8 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 9 vertices.
Process: | ########################################### | 100.0% Complete
We found 0 candidates on 9 vertices.
0 of them are actually 3-dicritical.

Generating all 3-dicritical semi-complete digraphs with maximum acyclic
induced subdigraph of size exactly 6.

Computing candidates on 7 vertices.
Process: | ########################################### | 100.0% Complete
We found 80 candidates on 7 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 8 vertices.
Process: | ########################################### | 100.0% Complete
We found 500 candidates on 8 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 9 vertices.
Process: | ###########################################| 100.0% Complete
We found 39 candidates on 9 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 10 vertices.
Process: | ###########################################| 100.0% Complete
We found 0 candidates on 10 vertices.
0 of them are actually 3-dicritical.

Generating all 3-dicritical semi-complete digraphs with maximum acyclic
induced subdigraph of size exactly 7.

Computing candidates on 8 vertices.
Process: | ###########################################| 100.0% Complete
We found 110 candidates on 8 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 9 vertices.
Process: | ###########################################| 100.0% Complete
We found 459 candidates on 9 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 10 vertices.
Process: | ###########################################| 100.0% Complete
We found 16 candidates on 10 vertices.
0 of them are actually 3-dicritical.

Computing candidates on 11 vertices.
Process: | ###########################################| 100.0% Complete
We found 0 candidates on 11 vertices.
0 of them are actually 3-dicritical.

The adjacency matrices in the output are exactly those of the digraphs $\vec{K}_3$, $\mathcal{H}_5$ and $\mathcal{P}_7$.