Frédéric Havet
email: frederic.havet@inria.fr

Florian Hörsch
email: florian.hoersch@cispa.de

Lucas Picasarri-Arrieta
email: lucas.picasarri-arrieta@inria.fr

The 3-dicritical semi-complete digraphs

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.

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.

Definitions

Our notation follows [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF]. 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, . . . , 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 , . . . , v n is the graph with vertex set {v i | i ∈ [n]} and edge set {v i v i+1 | i ∈ [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) ⊆ V (G) and E(H) ⊆ E(G) hold. If additionally V (H) = V (G) or E(H) = E(G), then H is called a proper subgraph of G. For some S ⊆ 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 endvertices in S.

Similarly, a digraph

D ′ is a subdigraph of a digraph D if V (D ′ ) ⊆ V (D) and A(D ′ ) ⊆ A(D) hold. If additionally V (D ′ ) = V (D) or A(D ′ ) = 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 ⊆ 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 endvertices 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 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 ⊆ V (D), we say that X dominates Y (and Y is dominated by X) if xy ∈ A(D) holds for all x ∈ X and y ∈ 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 ∈ 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 ≥ 2 vertices is the digraph with vertex set {v 1 , . . . , v n } and arc set {v i v i+1 | i ∈ [n -1]} ∪ {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 , . . . , v n of V (D) such that for every arc v i v j ∈ 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 T T n to denote the unique transitive tournament on n vertices.

Context

A k-colouring of a graph G is a function φ : V (G) → [k]. It is proper if φ(u) = φ(v)
for every edge uv ∈ 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 [START_REF] Dirac | A property of 4-chromatic graphs and some remarks on critical graphs[END_REF][START_REF] Dirac | Circuits in critical graphs[END_REF][START_REF] Dirac | A theorem of R. L. Brooks and a conjecture of H. Hadwiger[END_REF][START_REF] Dirac | On the structure of k-chromatic graphs[END_REF] 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 ≥ 4, there is no k-critical graph on k + 1 vertices and for every n ≥ k + 2, there exists a k-critical graph on n vertices. Further, for every k ≥ 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 ≥ 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) = +∞. The sequence g k is rather well understood due to the following result of Kostochka and Yancey [START_REF] Kostochka | Ore's conjecture on color-critical graphs is almost true[END_REF].

Theorem 1 (Kostochka and Yancey [START_REF] Kostochka | Ore's conjecture on color-critical graphs is almost true[END_REF]). Let n and k be two integers such that n > k ≥ 4.

If G is a k-critical graph on n vertices, then m(G) ≥ (k+1)(k-2)n-k(k-3) 2(k-1)
. In other words,

g k (n) ≥ (k+1)(k-2)n-k(k-3) 2(k-1)
. 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 [START_REF] Hajós | Über eine Konstruktion nicht n-farbbarer Graphen[END_REF]. Theorem 1 confirms a conjecture of Gallai [START_REF] Gallai | Kritische Graphen I[END_REF] and improves on a collection of earlier results [START_REF] Dirac | A theorem of R. L. Brooks and a conjecture of H. Hadwiger[END_REF][START_REF] Gallai | Kritische Graphen I[END_REF][START_REF] Gallai | Kritische Graphen II[END_REF][START_REF] Kostochka | A new lower bound on the number of edges in colour-critical graphs and hypergraphs[END_REF][START_REF] Krivelevich | On the minimal number of edges in color-critical graphs[END_REF]. A more detailed overview can be found in [START_REF] Kostochka | Ore's conjecture on color-critical graphs is almost true[END_REF].

The girth of a graph G is the minimum length of a cycle in G or +∞ if G is a forest. Kostochka and Stiebitz [START_REF] Kostochka | On the number of edges in colour-critical graphs and hypergraphs[END_REF] showed that if a k-critical G has girth at least 4, then m(G) ≥ (ko(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 [START_REF] Liu | On the minimum edge-density of 4-critical graphs of girth five[END_REF] 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 ε > 0 such that every 4-critical graph G of girth at least 5 contains at least ( 53 + ε)n(G) + c edges. Likewise, Postle [27] showed that every 5-critical graph with girth at least 4 satisfies m(G) ≥ ( 94 + ε)n(G) -5 4 for ε = 1 84 . It is also interesting to determine the maximum number of edges in a k-critical graph. Erdős [START_REF] Erdos | Problems and results in chromatic graph theory[END_REF] asked, for every fixed k ≥ 4, whether there exists a constant c k > 0 such that there exists arbitrarily large k-critical graphs G with at least c k • n(G) 2 edges. This was proved by Dirac [START_REF] Dirac | A property of 4-chromatic graphs and some remarks on critical graphs[END_REF] when k ≥ 6 and then by Toft [START_REF] Toft | On the maximal number of edges of critical k-chromatic graphs[END_REF] when k ∈ {4, 5}. The best current upper bound on such a constant c k has recently been given by Luo, Ma, and Yang [START_REF] Luo | On the maximum number of edges in k-critical graphs[END_REF], improving on an earlier result of Stiebitz [START_REF] Stiebitz | Subgraphs of colour-critical graphs[END_REF].

Several analogues of colouring have been introduced for digraphs. In 1982, Neumann-Lara [START_REF] Neumann-Lara | The dichromatic number of a digraph[END_REF] introduced the one of dicolouring

. A k-dicolouring of a digraph D is a function φ : V (D) → [k] such that D[φ -1 (i)] is acyclic for every i ∈ [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 ← → 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. [START_REF] Bang-Jensen | Hajós and Ore constructions for digraphs[END_REF]. Again, for some n ≥ 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) = +∞ if no such digraph exists.
Observe that, for every k ≥ 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 ← → 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) < +∞ for all n ≥ k. Moreover, it holds d k (n) ≤ 2g k (n) for all n ≥ k.
Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF] conjectured that the bidirected k-dicritical digraphs obtained from k-critical graphs are the sparsest k-dicritical digraphs.

Conjecture 2 (Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF]). Let n and k be two integers such that n -2 ≥ k ≥ 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 sligthtly weaker one. [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF]). Let n and k be two integers such that n

Conjecture 3 (Kostochka and Stiebitz

> k ≥ 4. If D is a k-dicritical digraph on n vertices, then m(D) ≥ (k+1)(k-2)n-k(k-3) k-1
and all digraphs attaining this bound are bidirected.

In [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF], Kostochka and Stiebitz confirmed Conjecture 3 for k ≤ 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) = +∞ if there is no k-dicritical oriented graph of order n. Clearly, we have o k (n) ≥ d k (n). Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF] posed a conjecture suggesting that there is a significant gap between d k (n) and o k (n). [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF]). There exists ε > 0 such that o k (n) ≥ (1 + ε) • d k (n) for every k ≥ 4 and sufficiently large n.

Conjecture 4 (Kostochka and Stiebitz

Observe that this conjecture trivially holds when o k (n) = +∞. However we do not know the set N k of integers n for which o k (n) < +∞, 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 [START_REF] Neumann-Lara | The 3 and 4-dichromatic tournaments of minimum order[END_REF] proved n 3 = 7 and n 4 = 11 ; Bellitto et al. [START_REF] Bellitto | The smallest 5-chromatic tournament[END_REF] recently established n 5 = 19. As observed by Aboulker et al. [START_REF] Aboulker | On the minimum number of arcs in kdicritical oriented graphs[END_REF] using a lemma of Hoshino and Kawarabayashi [START_REF] Hoshino | The edge density of critical digraphs[END_REF], there exists a smallest integer p k such that there exists a k-dicritical oriented graph on n vertices for any n ≥ p k . Moreover, while p 3 = n 3 = 7, they showed that p 4 = 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. [START_REF] Aboulker | On the minimum number of arcs in kdicritical oriented graphs[END_REF] and for k = 4 by the first and third authors, and Rambaud [START_REF] Havet | On the minimum number of arcs in 4-dicritical oriented graphs[END_REF].

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 ≥ 3, Hoshino and Kawarabayashi [START_REF] Hoshino | The edge density of critical digraphs[END_REF] constructed an infinite family of k-dicritical oriented graphs D on n vertices which satisfy m(D) ≥ ( 1 2 -1 2 k -1 )n 2 , and they conjectured that this bound is tight.

Conjecture 5 (Hoshino and Kawarabayashi [START_REF] Hoshino | The edge density of critical digraphs[END_REF]). Let k ≥ 3 be an integer.

If D is a k-dicritical oriented graph, then m(D) ≤ ( 1 2 -1 2 k -1 )n 2 .
Aboulker [1] observed that, since a tournament has 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.

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. In particular, we can characterize all 3-dicritical tournaments.

Corollary 8. There are exactly two 3-dicritical tournaments, namely R( -→ C 3 , -→ 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) ≤ n 2 + n -1 holds for every 3-dicritical digraph D different from ← → K 3 . We slightly improve this upper bound on m(D) as follows (the digraph -→ W 3 is depicted in Figure 1).

Theorem 9. If D is a 3-dicritical digraph distinct from ← → K 3 and -→ W 3 , then m(D) ≤ n 2 + 2 3 n. (a) ← → K 3 (b) -→ W 3 ⇒ ⇒ ⇒ (c) R( ← → K 2 , ← → K 2 ) (d) H 5 ⇒ ⇒ ⇒ (e) R( ← → K 2 , -→ C 3 ) ⇒ ⇒ ⇒ (f) R( -→ C 3 , ← → K 2 ) ⇒ ⇒ ⇒ (g) R( -→ C 3 , -→ C 3 ) (h) P 7
Figure 1: The 3-dicritical semi-complete digraphs, namely the bidirected complete graph ← → K 3 , the directed wheel -→ W 3 , the digraph H 5 , the rotative digraphs R(H 1 , H 2 ) for every

H 1 , H 2 ∈ { ← → K 2 , -→ C 3
} and the Paley tournament on seven vertices 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.

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 φ : V (D) -→ [START_REF] Aboulker | On the minimum number of arcs in kdicritical oriented graphs[END_REF] such that:

• φ is a 2-dicolouring of D \ uv, • φ(u) = φ(v) = 1,

and

• D \ uv, coloured with φ, 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 φ : V (D) → [START_REF] Aboulker | On the minimum number of arcs in kdicritical oriented graphs[END_REF] of D \ uv. By symmetry, we may suppose φ(u) = 1. As φ is not a 2-dicolouring of D, we obtain that φ(v) = 1 and there is a directed vu-path P in D such that φ(x) = 1 for all x ∈ V (P ). If there is also a directed uv-path Q in D \ uv such that φ(x) = 1 for all x ∈ V (Q), then the subdigraph of D \ uv induced by V (P ) ∪ V (Q) contains a monochromatic directed cycle. This contradicts φ being a 2-dicolouring of D \ uv.

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 ∈ 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 φ of D \ a. As φ is not a 2-dicolouring of D, there exists a directed cycle C in D such that C is monochromatic with respect to φ. 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 \ a with respect to φ, we obtain that a ∈ A(C).

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. 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 φ of D. Since there exists no monochromatic directed uv-path, we have φ(x) = φ(y) = φ(z) = 2. Hence D \ uv contains a monochromatic directed triangle with respect to φ, a contradiction.

Let S be a transitive subtournament of a digraph D = (V, A). We denote by v 1 , . . . , v s the unique acyclic ordering of S. For some i, j ∈ [s], we say that {v i , . . . , v j } is an interval of S. Observe that ∅ is an interval. For i 0 , j 0 , i 1 , j 1 ∈ [s] with j 0 < i 1 , we say that the interval {v i0 , . . . , v j0 } is smaller than the interval {v i1 , . . . , v j1 }. By convention ∅ is both smaller and greater than any other interval. A sequence of intervals P 1 , . . . , P t is called increasing if P i is smaller than P j for all i, j ∈ [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 , . . . , v s . For any x ∈ V (T ) \ S, there is an increasing sequence of intervals (I 1 , I 2 , I 3 , I 4 ) with 4 i=1 I i = S such that, in T , x dominates I 1 ∪ I 3 and is dominated by

I 2 ∪ 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 i1 and v i3 and dominates v i2 and v i4 . Then the subdigraph of D induced by {v i1 , v i2 , x, v i3 , v i4 } contains O 5 as a subdigraph, a contradiction to Lemma 12.

We finally need a well-known theorem which can be found in many basic textbooks on graph theory, see for example [START_REF] Diestel | Graph Theory[END_REF]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 Ra(b) and for every mapping

ψ : E(G) → [a], there is a set S ⊆ V (G) of cardinality b and i ∈ [a] such that ψ(e) = i for all e ∈ E(G[S]).

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) ≤ 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)

≥ 12R 6 (3) + 2. Let S ⊆ V be a maximum set of vertices such that D[S] is acyclic. Let v 1 , . . . , v s be the unique acyclic ordering of S. Since D is 3-dicritical, for an arbitrary vertex x ∈ V , we have that D -x is 2-dicolourable. This yields s ≥ n(D)-1 2 ≥ 6R 6 (3) + 1.
By Lemma 11, for every i ∈ [s -1], the arc v i v 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 ∈ V \ S such that v i v i+1 x i v 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 ∈ [s -1] as C i is induced in D. For any vertex x in V \ S and i ∈ [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 ∪ A 2 with A 1 = {(i, i + 1) | i ∈ [s -2]} and A 2 = {(i, j) | i = j and x i switches at j.}.
By Lemma 13, for i ∈ [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] \ {i}. Thus every i ∈ [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 UG(H)[J] has a vertex of degree at most 5. Hence UG(H) is 5-degenerate, and so it is 6-colourable. Therefore H has an independent set I of size 1 6 (s -1) ≥ R 6 [START_REF] Bang-Jensen | Hajós and Ore constructions for digraphs[END_REF]. By definition of I, for any i, j ∈ I with i = 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 ) ∪ V (C j ) is one of the eight tournaments depicted in Figure 3. For (α) ∈ {(a), . . . , (h)}, we say that (i, j) is an (α)-configuration if T [V (C i )∪V (C j )] is the tournament depicted in Figure 3 (α).

Let us fix a pair i, j ∈ 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

v i+1 v i x i v j+1 v j x j (a) v i+1 v i x i v j+1 v j x j (b) v i+1 v i x i v j+1 v j x j (c) v i+1 v i x i v j+1 v j x j (d) v i+1 v i x i v j+1 v j x j (e) v i+1 v i x i v j+1 v j x j (f ) v i+1 v i x i v j+1 v j x j (g) v i+1 v i x i v j+1 v j
x j (h) Figure 3: A listing of all possible configurations for i, j ∈ I with i < j. For the sake of better readability, the arcs in A(C i ) ∪ 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.
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| ≥ R 6 (3), and by definition of R 6 (3), we know that there exist {i, j, h} ⊆ I, i < j < h, and (α) ∈ {(a), . . . , (e)} such that the three pairs (i, j), (j, h), (i, h) are (α)-configurations. We show that each of the six cases yields a contradiction, implying the result.

• If (α) = (a), let φ be a v i+1 v h -colouring of D, the existence of which is guaranteed by Lemma 10. Recall that φ(v i+1 ) = φ(v h ) = 1, φ is a 2-dicolouring of D\v i+1 v h and D coloured with φ contains no monochromatic directed v i+1 v h -path. Then φ(v j ) = φ(v j+1 ) = 2 because {v j , v j+1 } ⊆ N + D (v i+1 ) ∩ N - D (v h ). Thus, since C j is not monochromatic in φ, we have φ(x j ) = 1. We obtain that φ(x i ) = φ(v i ) = 2, for otherwise v i+1 x i x j v i+1 or v i v h x j v i is monochromatic. We deduce that v i v j x i v i is monochromatic, a contradiction. • If (α) = (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 (α) = (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 (α) = (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 (α) = (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 (α) = (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.

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 ⊆ V (H) with |S| = 3 and {w 1 , w 7 } \ S = ∅.

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 3 w 5 , w 3 w 6 ∈ 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 1 w 3 . Similarly, we obtain e 7 = w 5 w 7 . By symmetry, we may suppose that e 0 = w 4 w 6 . But then {w 1 , w 4 , w 6 } is an independent set, a contradiction.

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 ← → K 2 and two additional vertices u, v, one arc from u to every vertex of ← → K 2 , one arc from every vertex of ← → 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. We now prove a similar result for a collection of four digraphs. Given two digraphs H 1 and H 2 , let H 1 ⇒ 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 ⊞ H 2 . It is straightforward that χ(H 1 ⊞ H 2 ) = χ(H 1 ) + χ(H 2 ), see [3]. Lemma 18. Let H 1 , H 2 be two digraphs in { ← → K 2 , -→ C 3 } and let D be a semi-complete digraph containing H 1 ⇒ H 2 as a subdigraph. Then D is 3-dicritical if and only if D is exactly R(H 1 , H 2 ). Proof. It is easy to see that R(H 1 , H 2 ) is 3-dicritical. For the other direction, let us fix H 1 , H 2 ∈ { ← → K 2 , -→ C 3 } and let D be a 3-dicritical semi-complete digraph containing H 1 ⇒ H 2 . Let X = V (H 1 ) and Y = V (H 2 ). Let us first prove that V (D) \ (X ∪ Y ) = ∅,
so assume for a contradiction that V (D) = X ∪ 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 ⊞ 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) \ (X ∪ Y ) = ∅.
First suppose that there exists some v ∈ V (D) \ (X ∪ 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 ∈ X and y 1 , y 2 ∈ Y such that {x 1 x 2 , y 1 y 2 , x 1 v, vx 2 , y 1 v, 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 ∈ V (D) \ (X ∪ Y ) has no out-neighbour or no in-neighbour in one of {X, Y }. Henceforth we assume that for every vertex v ∈ V (D) \ (X ∪ 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 ∈ V (D) \ (X ∪ 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) \ (X ∪ Y ) such that there is no arc from V 1 to X and there is no arc from Y to V 2 .

Now suppose that there exists some

v ∈ V (T ) \ (X ∪ Y ) that dominates X. If v has an out- neighbour y in Y , then D[X ∪ {v, y}] contains O 4 as a subdigraph if H 1 = ← → K 2 and
By symmetry, we may assume that V 2 is non-empty. Let us fix v 2 ∈ V 2 and y 1 ∈ Y . Since v 2 y 1 is a simple arc, by Lemma 11, there exists a vertex v The rest of the preparatory results before the main proof of Theorem 7 aims to exclude a collection of tournaments 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 T 8 is postponed, we now give the definition of F . Let F be the oriented graph with vertex set {u 1 , . . . , u 6 , x 1 , x 2 , x 3 } such that:

1 such that v 2 y 1 v 1 v 2 is an induced directed triangle in D. Note that v 1 / ∈ Y since there is no arc from Y to V 2 . Also note that v 1 / ∈ X for otherwise v 2 y 1 v 1 v 2 is not induced since X dominates Y . Further note that v 1 / ∈ V 2 since it is an out-neighbour of y 1 . This implies v 1 ∈ 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 ,
• {u 1 , . . . , u 6 } induces a copy of T T 6 the unique acyclic ordering of which is exactly u 1 , . . . , u 6 , and

• for every i ∈ [START_REF] Bang-Jensen | Hajós and Ore constructions for digraphs[END_REF], F contains the arcs u 2i x i and x i u 2i-1 .

See Figure 6 for an illustration of F . We let F be the set of tournaments T with vertex set V (T ) = V (F ) and such that A(F ) ⊆ A(T ). Note that 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 , . . . , T 4 . We give their adjacency matrices in Appendix A.

u 1 u 2 u 3 u 4 u 5 u 6 x 1 x 2 x 3

Lemma 19. None of the tournaments in

F \ {T 1 , T 2 , T 3 , T 4 } is a subdigraph of a 3-dicritical semi- complete digraph.
Proof. For every tournament T ∈ F , we check, using the code of Appendix B.1, if it contains -→ C 3 ⇒ -→ C 3 as a subdigraph or if it admits no uv-colouring for an arc uv. This is always the case except when T ∈ {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 0 u i | i ∈ [6]}. Analogously, let F -be the oriented graph obtained form F by adding a vertex u 7 and the arcs of {u i u 7 | i ∈ [6]}. See Figure 7 for an illustration. Lemma 20. Let D be a 3-dicritical semi-complete digraph. Then D does not contain a digraph in {F + , F -} as a subdigraph.

u 0 u 1 u 2 u 3 u 4 u 5 u 6 x 1 x 2 x 3 u 1 u 2 u 3 u 4 u 5 u 6 u 7 x 1 x 2 x 3
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, Du 0 contains some T ′ ∈ {T 1 , T 2 , T 3 , T 4 }. Now consider the collection T of tournaments on {u 0 , . . . , 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 , . . . , u 6 }. Observe that by assumption, D contains a tournament in T as a spanning subdigraph. Further, T contains exactly 4 × 2 3 = 32 digraphs. Using the code in Appendix B.2, we check that each of them contains -→ C 3 ⇒ -→ 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 T T 8 as an induced subdigraph.

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

Let S ⊆ V be such that D[S] is isomorphic to T T 8 . Let v 1 , . . . , v 8 be the unique acyclic ordering of S. By Lemma 11, for every i ∈ [START_REF] Diestel | Graph Theory[END_REF], there exists a vertex

x i ∈ V \ S such that v i v i+1 x i v i forms an induced directed triangle C i .
Let H be the graph with vertex set V (H) = [START_REF] Diestel | Graph Theory[END_REF] and that contains an edge linking i and j if V (C i ) ∩ V (C j ) = ∅. For any i, j ∈ [START_REF] Diestel | Graph Theory[END_REF] with ij ∈ E(H) and |i -j| ≥ 2, we have x i = x j . By Lemma 13, there is no set {i, j, k} ⊆ [START_REF] Diestel | Graph Theory[END_REF] 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 ⊆ [START_REF] Diestel | Graph Theory[END_REF] with |I| = 3 such that the following hold: This shows that D contains F + or F -, yielding a contradiction to Lemma 20.

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 ∈ 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 L of all semi-complete digraphs L on nine vertices such that each of the following holds:

(i) L contains some T ∈ {T 1 , T 2 , T 3 , T 4 } as a subdigraph, (ii) L does not contain any digraph in { ← → S 4 , ← → K 2 ⇒ ← → K 2 , ← → K 2 ⇒ -→ C 3 , -→ C 3 ⇒ ← → K 2 , -→ C 3 ⇒ -→ C 3 , O 4 , O 5 } as a subdigraph,
(iii) L admits a uv-colouring for every arc uv ∈ A(L), and (iv) L does not contain T T 8 as an induced subdigraph.

By Lemmas 10,[START_REF] Erdos | Problems and results in chromatic graph theory[END_REF][START_REF] Havet | On the minimum number of arcs in 4-dicritical oriented graphs[END_REF][START_REF] Hoshino | The edge density of critical digraphs[END_REF], and 18, we know that D contains some L ∈ L as an induced subdigraph. In the second part of the code, we check that every 2-extension L ′ of 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 ∈ L or D is a 1-extension of L . Finally, we check that every L ∈ 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.

We now give the definition of T 8 and show that no digraph in T 8 can be contained in a 3-dicritical semi-complete digraph as an induced subdigraph. Let T 8 be the set of tournaments obtained from T T 8 by reversing exactly one arc. Observe that T T 8 belongs to T 8 . Lemma 23. Let D be a 3-dicritical semi-complete digraph. Then D does not contain any digraph in T 8 as an induced subdigraph.

Proof. Assume for a contradiction that D contains some T ′ ∈ T 8 as an induced subtournament. Let X ⊆ V (T ) be such that D[X] is isomorphic to T ′ . By definition of T 8 , let x 1 , . . . , 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, ℓ}, k < ℓ.

Assume first that k = ℓ -1. Then observe that T ′ is isomorphic to T T 8 , with the acyclic ordering obtained from x 1 , . . . , x 8 by swapping x ℓ and x ℓ-1 . This contradicts Lemma 21.

Henceforth assume that

k ≤ ℓ -2. If k ≥ 2 and ℓ ≤ 7 then D[{x 1 , x k , x ℓ-1 , x ℓ , x 8
}] is isomorphic to O 5 , a contradiction to Lemma 12. Henceforth we assume that k = 1 or ℓ = 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 \ {x 1 , x 2 , x ℓ }. We denote its acyclic ordering by y 1 , . . . , y 5 , which exactly corresponds to x 3 , . . . , x ℓ-1 , x ℓ+1 , . . . , x 8 . By Lemma 11, for every k ∈ [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF], 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 \ V (S). Moreover, z k / ∈ {x 1 , x 2 , x ℓ } because both X \ {x 1 } and X \ {x ℓ } are acyclic.
Let H be the graph with vertex set V (H) = [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] and that contains an edge linking i and j if V (C i ) ∩ V (C j ) = ∅. For any i, j ∈ [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] with ij ∈ E(H) and |i -j| ≥ 2, we have z i = z j . By Lemma 13, there is no set {h, i, j} ⊆ [START_REF] Bang-Jensen | Digraphs: Theory, Algorithms and Applications[END_REF] 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 1 x 2 x ℓ , we deduce that D contains F as a subdigraph. This contradicts Lemma 22.

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 ∈ [START_REF] Diestel | Graph Theory[END_REF], let D i be the set of semi-complete digraphs D such that each of the following holds:

• the maximum acyclic set S ⊆ 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 { ← → S 4 , ← → K 2 ⇒ ← → K 2 , ← → K 2 ⇒ -→ C 3 , -→ C 3 ⇒ ← → K 2 , -→ C 3 ⇒ -→ C 3 , O 4 , O 5 , F } as a subdigraph,
• D does not contain any digraph of T 8 as an induced subdigraph, Lemma 24. The 3-dicritical digraphs in 7 i=1 D i are exactly ← → K 3 , H 5 , and P 7 .

Proof. For every i ∈ [START_REF] Diestel | Graph Theory[END_REF], we compute D i by starting from the singleton {T T i } which is clearly the only digraph in D i on at most i vertices. Using the code in Appendix B.4, we first successively compute the digraphs in D i on j ≥ i vertices by generating every possible 1-extension of the digraphs in D i on j -1 vertices, and saving only the ones satisfying the conditions on D i . When j is large enough, it turns out that the set of digraphs in D i on j vertices is empty, implying that D i is finite.

We then consider every digraph D ∈ 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.

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

Proof. By Lemmas 10,[START_REF] Erdos | Problems and results in chromatic graph theory[END_REF][START_REF] Havet | On the minimum number of arcs in 4-dicritical oriented graphs[END_REF][START_REF] Hoshino | The edge density of critical digraphs[END_REF][START_REF] Kostochka | On the number of edges in colour-critical graphs and hypergraphs[END_REF][START_REF] Krivelevich | On the minimal number of edges in color-critical graphs[END_REF][START_REF] Liu | On the minimum edge-density of 4-critical graphs of girth five[END_REF], we have that every 3-dicritical semi-complete digraph that is not contained in

7 i=1 D i is one of -→ W 3 , R( ← → K 2 , ← → K 2 ), R( ← → K 2 , -→ C 3 ), R( -→ C 3 , ← → K 2 ), and R( -→ C 3 , -→ C 3
). The statement then follows directly from Lemma 24.

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 1 u 2 . . . u p u 1 . Let ← → C be the bidirected cycle in D corresponding to C. The cycle C cannot be odd, for otherwise ← → C would be a bidirected odd cycle, and D = ← → 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 φ of D \ {u 1 u 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 φ is a 2-dicolouring of D, a contradiction.

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 ∈ V (T ) form an odd pair if they are non-adjacent and dist T (u, v) is odd, where 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:

dearth(T ) = v∈V3(T ) 1 6 d(v)(d(v) -1) + 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 ) ≥ 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 ≥ 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 ∈ {1, . . . , n-3}, as n ≥ 4, there are exactly i distinct pairs of vertices at distance

exactly n -i in T . Hence dearth(T ) ≥ op(T ) = n-2 2 i=1 (2i -1) = n-2 2 2 ≥ 1 3 n -1. Case 2: T is a path of odd length.
For every odd i ∈ {1, . . . , n-2}, as n ≥ 4, there are exactly i distinct pairs of vertices at distance

exactly n -i in T . Hence dearth(T ) ≥ op(T ) = n-3 2 i=1 2i = n-3 2 n-1 2 ≥ 1 3 n -1. Case 3: T is a star on n ≥ 4 vertices.
As n ≥ 4, we obtain that dearth(T ) is exactly 1 6 (n -1)(n -2), and so dearth(T ) ≥ 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) ≥ 2 and d T (v) ≥ 3. Let v 1 , . . . , v r be the neighbours of v in T , where v 1 = u and r = d T (v) ≥ 3. For each i ∈ [r], let T i be the component of Tv containing v i . By the choice of T , we have dearth(T i ) ≥ 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 , . . . , v r we obtain:

dearth(T ) ≥ r i=1 dearth(T i ) + 1 6 r(r -1) + (r -1) ≥ 1 3 (n(T ) -1) -r + 1 6 r(r -1) + (r -1) ≥ 1 3 n(T ) -1,
where in the last inequality we used r ≥ 3. This contradicts the choice of T .

Lemma 28. Let D be a 3-dicritical digraph distinct from { ← → K 3 , -→ W 3 } and ← → T be a bidirected tree contained in D. Then we have |{{u, v} ⊆ V (T ) | {uv, vu} ∩ A(D) = ∅}| ≥ dearth(T ). Proof. Set O = {{u, v} ⊆ V (T ) | {uv, vu} ∩ A(D) = ∅}. For every vertex v ∈ V 3 (T ), let O v = O ∩ (N T (v) × N T (v)). Finally let O odd = O ∩ OP(T ).
Let us first show that these sets are pairwise disjoint. Let u, v ∈ V 3 (T ) be two vertices of degree at least 3 in T . Since T is a tree, we have that N T (u) ∩ N T (v) contains at most one vertex, implying that O u ∩ O v = ∅. Also note that vertices in N T (v) are at distance exactly 2 from each other, so

O v ∩ O odd = ∅. This implies |O| ≥ v∈V3(T ) |O v | + |O odd |.
Hence it is sufficient to prove

|O v | ≥ 1 6 d T (v)(d T (v) -1)
for every v ∈ V 3 (T ) and O odd = OP(T ) to prove Lemma 28.

Let v ∈ 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

← → K 3 , -→ 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)]) • (d T (v) -2) = X⊆NT (v), |X|=3 m(D[X]) ≤ 2 • d T (v) 3 , implying that m(D[N T (v)]) ≤ 1 3 d T (v)(d T (v) -1). Therefore, we obtain |O v | = dT (v) 2 - m(D[N T (v)]) ≥ 1 6 d T (v)(d T (v) -1)
as desired. To show O odd = OP(T ), it is sufficient to show that if {u, v} is an odd pair then {uv, vu} ∩ A(D) = ∅. Assume this is not the case, then by Lemma 10 D ′ = D \ {uv, vu} admits a 2-dicolouring φ in which φ(u) = φ(v), a contradiction since u and v are connected by a bidirected odd path in D ′ . This shows the claim.

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 ← → K 3 and -→ W 3 , then m(D) ≤ n 2 + 2 3 n. Proof.
Let D be such a digraph. If D is a bidirected odd cycle, we have n ≥ 5 and hence D has 2n ≤ n 2 + 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 , . . . , T s be the connected components of B(D). For every i ∈ [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 dearth(T i ) by Claim 28. Hence, since there is no digon between the T i s, we obtain

m(D) ≤ n 2 + s i=1 (n(T i ) -1) -dearth(T i ) ≤ n 2 + s i=1 (n(T i ) -1) -( 1 3 n(T i ) -1) by Claim 26 = n 2 + 2 3 n,
which concludes the proof.

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) ≥ n 2 .

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

Conjecture 30. For every k ≥ 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-vertexdicritical if D is not 3-dicolourable, but Dv is for all v ∈ 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 [START_REF] Chen | A min-max theorem on tournaments[END_REF] 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.

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.

B.0 Preliminaries for the code

In the following code, we give a collection of subroutines we use in our code. F . add_edge (j , i ) 143 F . add_edge (6 ,0) 144 F . add_edge (1 ,6) 145 F . add_edge (7 ,2) 146 F . add_edge (3 ,7) 147 F . add_edge (8 ,4)

22

B.1 The proof of Lemma 19

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

Proof. For every tournament T ∈ F , we check, using the following code, if it contains -→ C 3 ⇒ -→ C 3 as a subdigraph or if it admits no uv-colouring for an arc uv. This is always the case except when T ∈ {T 1 , T 2 , T 3 , T 4 }. The Claim then follows by Lemmas 10 and 18.

1 load ( " tools . sage " ) missing_edges =[(6 ,2) ,(6 ,3) , (6 ,4) , (6 ,5) ,(6 ,7) ,(6 ,8) ,(7 ,0) ,(7 ,1) , (7 ,4) , (7 ,5) , (7 ,8) ,(8 ,0) ,(8 ,1) ,(8 ,2) ,(8 ,3) ] 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 subtournamen t 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.

1 import networkx 2 load ( " tools . sage " )

17 # 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 +. 18 # 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 . Running this code produces the following output after roughly 1 second of execution on a standard desktop computer:

1 We start from the 4 candidates on 9 vertices . 2 Computing for F +...

B.3 The proof of Lemma 22

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

1 import networkx 2 load ( " tools . sage " )

B.4 The proof of Lemma 24

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

1 load ( " tools . sage " ) # we consider every possible orientation between the vertices ( nb_vertices -1) and ( progress ) 36 n e x t _ t r a n s i t i v e _ t o u r n a m e n t. add_edge (j , i )

Theorem 7 .

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

Figure 2 :

 2 Figure 2: The oriented graph O 5 .

Lemma 16 .Figure 4 :

 164 Figure 4: The digraph O 4 .

Figure 5 :S 4 .

 54 Figure 5: The bidirected star on 4 vertices ← → S 4 .

Figure 6 :

 6 Figure 6: The oriented graph F .

Figure 7 :

 7 Figure 7: The oriented graphs F + (left) and F -(right).

  (a) {1, 7} \ I = ∅, (b) C i and C j are vertex-disjoint for all {i, j} ⊆ I.

1 # 7 #

 17 The following function displays a progress bar 2 def printProgre s sB ar ( iteration , total ) : 3 percent = ( " {0:.1 f } " ) . 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 " ) 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 ) : 29 # u : vertex 30 # v : vertex 31 # Returns : True if and only if d contains a directed path from u to v 32 def c o n t a i n s _ d i r e c t e d _ p a t h(d ,u , v ) : d . neighbors_out ( x ) : 40 if ( not y in to_be_treated ) : 96 d_aux = DiGraph ( len ( d . vertices () ) ) 97 d_aux . add_edges ( d . edges () ) 98 d_aux . delete_edge ( e ) 99 current_col ou r in g = {} 100 current_col ou r in g [ e [0]] = 0 101 current_col ou r in g [ e [1]] = 0 102 if ( not c a n _ b e _ s u b g r a p h _ o f _ 3 _ d i c r i t i c a l _ a u x( d_aux , e [0] , e [1] , current_col o ur i ng ) ) : 107 # Returns : True if and only if d is 2 -dicolourable 108 def is_two_dic o l ou r ab l e ( d ) : 109 n = d . order () 110 for bipartition in range (2** n ) : 111 # build the binary word corresponding to the bipartition 112 binary = bin ( bipartition ) [2:] 113 while ( len ( binary ) <( n ) ) : whether ( V1 , V2 ) is actually a dicolouring 124 d1 = d . subgraph ( V1 ) 125 d2 = d . subgraph ( V2 ) 126 if ( d1 . is_directe d _a c yc l ic () and d2 . is_directe d _a c yc l ic () ) : is the digraph made of two disjoint directed triangles , the vertices of one dominating the vertices of the other 131 C3_C3 = DiGraph (6) 132 for i in range (3) : 133 C3_C3 . add_edge (i ,( i +1) %3) 134 C3_C3 . add_edge ( i +3 ,(( i +1) %3) +3) 135 for j in range (3 ,6) : 136 C3_C3 . add_edge (i , j ) 137 138 # F is the digraph on nine vertices made of a TT6 u1 ,... , u6 and the arcs of the directed triangles u1u2x1u1 , u3u4x2u3 , u5u6x3u5 . 139 F = DiGraph (9) 140 for i in range (6) : 141 for j in range ( i ) :

  142

2 3 # 8 # 10 #

 3810 binary_code : a string of fifteen characters '0 ' and '1 ' 4 # Returns : a tournament of \ mathcal { F }. The orientations of the fifteen nonforced arcs correspond to the characters of binary_code . 5 def digraph_bl o wu p _T T 3 ( binary_code ) : 6 iterator_ bi n ar y _ co d e = iter ( binary_code ) 7 d = DiGraph (9) the vertices 0 ,... ,8 correspond respectively to u_1 ,... , u_6 , x_1 , x_2 , x_3 9 add the arcs of the TT_6 11 for i in range (6) : 12 for j in range ( i ) :

15 #

 15 add the arcs of the directed triangles 16 for i in range (3) :

21 #

 21 we orient the missing_edges according to binary_code 22 for e in missing_edges :

  24 if ( next ( iterator_ bi n ar y _c o d e ) == '0 ') : 24 d . add_edge ( e [0] , e [1]) " Computing all possible candidates of \ mathcal { F } for being a subtournament of a 3 -dicritical semi -complete digraph ... " ) 30 list_candida t es = [] 31 l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s = [ C3_C3 ] 32 33 # print progress bar 34 printProgre ss B ar (0 , 2**15) 35 for i in range (2**15) : 36 binary_value = bin ( i ) [2:] 37 while ( len ( binary_value ) <15) : 38 binary_value = '0 ' + binary_value 39 d = digraph_blo w up _ TT 3 ( binary_value ) 40 if ( c a n _ b e _ s u b g r a p h _ o f _ 3 _ d i c r i t i c a l(d ,[] , l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s) ) : 41 list_candida te s . append ( d ) 42 # update progress bar 43 printProgre s sB ar ( i + 1 , 2**15) 44 45 print ( " Number of candidates : " , len ( list_candida te s ) ," . " ) 46 for i in range ( len ( list_candid at e s ) ) : 47 print ( " Candidate " ,i +1 , " : " ) 48 list_candid at es [ i ]. export_to_fil e ( " T " + str ( i +1) + " . pajek " ) 49 print ( list_candida te s [ i ]. adjacency_m at r ix () )

3 4 6 7

 36 list_candida t es = [] 5 l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s = [ C3_C3 ] # import T1 , T2 , T3 and T4 8 for i in range (1 ,5) : 9 candidate = DiGraph (9) 10 nx = networkx . read_pajek ( " T " + str ( i ) + " . pajek " ) 11 for e in nx . edges () : 12 candidate . add_edge ( int ( e [0]) , int ( e [1]) ) 13 list_candid at es . append ( candidate ) 14 15 print ( " We start from the " , len ( list_candid at es ) , " candidates on 9 vertices . " )

  19 print ( " Computing for F +... " ) 20 list_Fp = [] 21 printProgre ss B ar (0 , 8) 22 for orientation in range (2**3) : 23 binary = bin ( orientation ) [2:]

  a n _ b e _ s u b g r a p h _ o f _ 3 _ d i c r i t i c a l( T10 ,[] , l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s) 38 if ( check ) : 39 list_Fm . append ( T2 ) 40 printProgre s sB ar ( orientation +1 , 8) 41 42 print ( " Number of 1 -extensions of { T1 , T2 , T3 , T4 } containing F +: " , len ( list_Fp ) )

3

 3 Process : | # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # # | 100.0% Complete 4 Number of 1 -extensions of { T1 , T2 , T3 , T4 } containing F +: 0

3 4

 3 all_candidat es = [] 5 current_ca nd i da t es = [] 6 next_candida t es = []

7 8

 7 l i s t _ f o r b i d d e n _ s u b d i g r a p h s = [ S4 , K2_K2 , O4 , O5 , K2_C3 , C3_K2 , C3_C3 ] 9 l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s = [ TT8 ] 10 11 # import the candidates T1 , ... , T4 on 9 vertices : 12 for i in range (1 ,5) : 13 candidate = DiGraph (9) 14 nx = networkx . read_pajek ( " T " + str ( i ) + " . pajek " ) 15 for e in nx . edges () :

20 21 26 #

 2026 16candidate . add_edge ( int ( e [0]) , int ( e[1]) ) 17 current_ca n di d at e s . append ( candidate ) 18 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 " )19 all_candidat es . extend ( current_can d id a te s )22 # completions of T1 , ... , T4 23 while ( len ( current_can d id a te s ) >0) :24for old_D in current_ca n di d at e s :25 for e in old_D . edges () : we try to complete old_D by replacing e by a digon . It actually makes sense only if e is not already in a digon .

27 if

 27 ( not ( e[1] , e [0] , None ) in old_D . edges () ) :

  ( old_D . edges () ) 30 new_D . add_edge ( e [1] , e [0]) 31 # we check whether this completion of old_D is potentially a subdigraph of a larger 3 -dicritical semi -complete digraph . 32 check = c a n _ b e _ s u b g r a p h _ o f _ 3 _ d i c r i t i c a l( new_D , list_forbidde n_ su bd ig ra ph s , l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s) 33 for D in next_candida te s : 34 check = check and ( not D . is_isomorphic ( new_D ) ) 35 if ( check ) : 36 next_candid at e s . append ( new_D ) 37 all_candidat es . extend ( next_candida te s )

2 3 9 #

 29 def possible_ co m pl e t io n s ( graph_to_complete , nb_vertices , list_forbidde n_ su bd ig ra ph s , list_forbi dd en _ in d uc e d_ su b di g ra p hs , progress =0we make a copy of the graph_to_c o mp l et e 10 new_D = DiGraph ( nb_vertices ) 11 new_D . add_edges ( graph_to_co m pl e te . edges () ) 12 13

  14 if ( i ==0) : 15 new_D . add_edge ( nb_vertices -1 , progress ) 16 elif ( i ==1) :

22 #

 22 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 23 if ( c a n _ b e _ s u b g r a p h _ o f _ 3 _ d i c r i t i c a l( new_D , list_forbidde n_ su bd ig ra ph s , l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s) ) : 24 result . extend ( possible_ co m pl e ti o n s ( new_D , nb_vertices , list_forbidde n_ su bd ig ra ph s , list_forbi dd en _ in d uc e d_ su b di g ra p hs , progress +1) ) 25 return result 26 27 for tt in range (1 ,8) : 28 transitiv e _t o ur n a me n t = DiGraph ( tt ) 29 for i in range ( tt ) : 30 for j in range ( i ) : 31 transitive _ t ou r na m e nt . add_edge (j , i ) 32 33 n e x t _ t r a n s i t i v e _ t o u r n a m e n t = DiGraph ( tt +1) 34 for i in range ( tt +1) : 35 for j in range ( i ) :

  t _ f o r b i d d e n _ s u b d i g r a p h s = [ S4 , K2_K2 , O4 , O5 , K2_C3 , C3_K2 , C3_C3 , F ] 39 l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s = [] 40 if ( tt <7) : 41 l i s t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s = [ n e x t _ t r a n s i t i v e _ t o u r n a m e n t]

  t _ f o r b i d d e n _ i n d u c e d _ s u b d i g r a p h s = reversed_TT8 44 30

  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 R(H 1 , H 2 ), implying that D is exactly R(H 1 , H 2 ) since both D and R(H 1 , H 2 ) are 3-dicritical.

  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 -→ 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.

  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.

* Research supported by the research grant DIGRAPHS ANR-19-CE48-0013 † Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATIC-GRAPH. ‡ Research supported by the research grants DIGRAPHS ANR-19-CE48-0013 and ANR-17-EURE-0004.

A The tournaments T 1 , . . . , T 4 We give the adjacency matrices of T 1 , T 2 , T 3 and T 4 . -----------------------------------------" ) 42 print ( " There are " , len ( all_candidate s ) ," 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 .\ n " ) 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 . 3 -----------------------------------------4 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 .

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

Computing 1 -extensions of the candidates on 9 vertices that are potentially subtournamen ts of 3 -dicritical tournaments ( up to isomorphism ) .

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 -----------------------------------------15 Computing 2 -extensions of the candidates on 9 vertices that are potentially subtournamen ts of 3 -dicritical tournaments ( up to isomorphism ) . Running this code produces the following output after roughly 2 hours of execution on a standard desktop computer: 123 Generating all 3 -dicritical semi -complete digraphs with maximum acyclic induced subdigraph of size exactly 1. The adjacency matrices in the output are exactly those of the digraphs ← → K 3 , H 5 and P 7 .