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

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

Clément Rambaud
email: clement.rambaud@ens.psl.eu

On the minimum number of arcs in 4-dicritical oriented graphs *

The dichromatic number ⃗ χ(D) of a digraph D is the minimum number of colours needed to colour the vertices of a digraph such that each colour class induces an acyclic subdigraph.

).

In this work, we prove that every 4-dicritical oriented graph on n vertices has at least ( 10 3 + 1 51 )n -1 arcs, showing the conjecture for k = 4. We also characterise exactly the k-dicritical digraphs on n vertices with exactly 10 3 n -4 3 arcs.

Introduction

Let G be a graph. We denote by V (G) its vertex set and by E(G) its edge set; we set n

(G) = |V (G)| and m(G) = |E(G)|. A k-colouring of G is a function φ : V (G) → [k].
It is proper if for every edge uv ∈ E(G), φ(u) ̸ = φ(v). The smallest integer k such that G has a proper k-colouring is the chromatic number, and is denoted by χ(G). Since χ is non decreasing with respect to the subgraph relation, it is natural to consider the minimal graphs (for this relation) which are not (k -1)-colourable. Following this idea, Dirac defined k-critical graphs as the graphs G with χ(G) = k and χ(H) < k for every proper subgraph H of G. A first property of k-critical graph is For k = 4, the conjecture trivially holds as there is no K 2 -free 4-critical graph. Moreover, this conjecture has been confirmed for k = 5 by Postle [START_REF] Postle | On the minimum number of edges in triangle-free 5-critical graphs[END_REF], for k = 6 by Gao and Postle [START_REF] Gao | On the minimal edge density of K 4 -free 6-critical graphs[END_REF], and for k ⩾ 33 by Gould, Larsen, and Postle [START_REF] Gould | Structure in sparse k-critical graphs[END_REF]. Equivalently, it is a k-dicolouring if every colour class induces an acyclic subdigraph. The smallest integer k such that D has a k-dicolouring is the dichromatic number of D and is denoted by ⃗ χ(D). A digon in D is a pair of opposite arcs between two vertices. Such a pair of arcs {uv, vu} is denoted by [u, v]. We say that D is a bidirected graph if every pair of adjacent vertices forms a digon. In this case, D can be viewed as obtained from an undirected graph G by replacing each edge {u, v} of G by the digon [u, v]. We say that D is a bidirected G, and we denote it by ← → G . Observe that χ(G) = ⃗ χ( ← → G ). Thus every statement on proper colouring of undirected graphs can be seen as a statement on dicolouring of bidirected graphs.

Exactly as in the undirected case, one can define k-dicritical digraphs to be digraphs D with ⃗ χ(D) = k and ⃗ χ(H) < k for every proper subdigraph H of D. It is easy to check that if G is a k-critical graph, then ← → G is k-dicritical. Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF] conjectured that the kdicritical digraphs with the minimum number of arcs are bidirected graphs. Thus they conjectured the following generalisation of Theorem 1 to digraphs.

Conjecture 3 (Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF]). Let k ⩾ 2. Every k-dicritical digraph on n vertices has at least (k -2 k-1 )n -k(k-3) k-1 arcs. Moreover, equality holds only if D is bidirected.

In the case k = 2, this conjecture is easy and weak as it states that a 2-dicritical digraph on n vertices has at least two arcs, while, for all n ⩾ 2, the unique 2-dicritical digraph of order n is the directed n-cycle which has n arcs. The case k = 3 of the conjecture has been confirmed by Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF]. Using a Brooks-type result for digraphs due to Harutyunyan and Mohar [START_REF] Harutyunyan | Gallai's theorem for list coloring of digraphs[END_REF], they proved the following: if D is a 3-dicritical digraph of order n ⩾ 3, then m(D) ⩾ 2n and equality holds if and only if n is odd and D is a bidirected odd cycle. The conjecture has also been proved for k = 4 by Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF]. However, the conjecture is open for every k ⩾ 5. Recently, this problem has been investigated by Aboulker and Vermande [START_REF] Aboulker | Various bounds on the minimum number of arcs in a k-dicritical digraph[END_REF] who proved the weaker bound (k -1 2 -2 k-1 )n -k(k-3) k-1 for the number of arcs in an n-vertex k-dicritical digraph.

For integers k and n, let d k (n) denote the minimum number of arcs in a k-dicritical digraph of order n. By the above observations, d 2 (n) = n for all n ⩾ 2, and d 3 (n) ⩾ 2n for all possible n, and equality holds if and only if n is odd and n ⩾ 3. Moreover, if n is even then d 3 (n) = 2n + 1 (see [START_REF] Aboulker | On the minimum number of arcs in k-dicritical oriented graphs[END_REF]).

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 graph G is triangle-free (that is has no cycle of length 3), then m(G)/n(G) ⩾ k -o(k) as k → +∞. 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. Similarly to this 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, that is a digraph with no digon. 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 o k (n) ⩾ d k (n).
Conjecture 4 (Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF]). For any k ⩾ 3, there is a constant

α k > 0 such that o k (n) > (1 + α k )d k (n) for n sufficiently large.
For k = 3, this conjecture has been recently confirmed by Aboulker, Bellitto, Havet, and Rambaud [START_REF] Aboulker | On the minimum number of arcs in k-dicritical oriented graphs[END_REF] who proved that o 3 (n) ⩾ (2 + 1 3 )n + 2 3 . In view of Conjecture 2, Conjecture 4 can be generalized to ← -→ K k-2 -free digraphs.

Conjecture 5. For any k ⩾ 4, there is a constant

β k > 0 such that every k-dicritical ← -→ K k-2 -free digraph D on n vertices has at least (1 + β k )d k (n) arcs.
Together with Conjecture 3, this conjecture would imply the following generalisation of Conjecture 2. Conjecture 6. For every integer k ⩾ 4, there exists

ε k > 0 such that every k-dicritical ← -→ K k-2 -free digraph D on n vertices has at least (k -2 k-1 + ε k )n -k(k-3) k-1 arcs. A ← → K 2 -
free digraph is an oriented graph, and there are infinitely many 4-dicritical oriented graphs. Thus, while Conjecture 2 holds vacuously for k = 4, this is not the case for Conjecture 6. In this paper, we prove that Conjectures 4, 5, and 6 hold for k = 4.

Theorem 7. If ⃗ G is a 4-dicritical oriented graph, then m( ⃗ G) ⩾ 10 3 + 1 51 n( ⃗ G) -1.
To prove Theorem 7, we use an approach similar to the proof of the case k = 5 of Conjecture 2 by Postle [START_REF] Postle | On the minimum number of edges in triangle-free 5-critical graphs[END_REF]. This proof is based on the potential method, which was first popularised by Kostochka and Yancey [START_REF] Kostochka | Ore's conjecture on color-critical graphs is almost true[END_REF] when they proved Theorem 1. The idea is to prove a more general result on every 4-dicritical digraphs that takes into account the digons.

With a slight abuse, we call digon a subdigraph isomorphic to ← → K 2 , the bidirected complete graph on two vertices. We also call bidirected triangle a subdigraph isomorphic to ← → K 3 , the bidirected complete graph on three vertices. A packing of digons and bidirected triangles is a set of vertex-disjoint digons and bidirected triangles. To take into account the digons, we define a parameter T (D) as follows.

T (D) = max{d + 2t | there exists a packing of d digons and t bidirected triangles} Clearly, T (D) = 0 if and only if D is an oriented graph.

Let ε, δ be fixed non-negative real numbers. We define the potential (with respect to ε and δ) of a digraph D to be

ρ(D) = 10 3 + ε n(D) -m(D) -δT (D).
Thus Theorem 7 can be rephrased as follows.

Theorem 7. Set ε = 1 51 and δ = 6ε = 2 17 . If ⃗ G is a 4-dicritical oriented graph, then ρ( ⃗ G) ⩽ 1.
In fact, we prove a more general statement which holds for every 4-dicritical digraph (with or without digons), except for some exceptions called the 4-Ore digraphs. Those digraphs, which are formally defined in Section 2, are the bidirected graphs whose underlying graph is one of the 4-critical graphs reaching equality in Theorem 1. In particular, every 4-Ore digraph D has 10 3 n(D) - 4 3 arcs. Moreover, the statement holds for all non-negative constants ε and δ satisfying the following inequalities:

• δ ⩾ 6ε; • 3δ -ε ⩽ 1 3 ; Theorem 8. Let ε, δ ⩾ 0 be constants satisfying the aforementioned inequalities. If D is a 4- dicritical digraph with n vertices, then (i) ρ(D) ⩽ 4 3 + εn -δ 2(n-1) 3 if D is 4-Ore, and (ii) ρ(D) ⩽ 1 otherwise.
In order to provide some intuition to the reader, let us briefly describe the main ideas of our proof. We will consider a minimum counterexample D to Theorem 8, and show that every subdigraph of D must have large potential. To do so, we need to construct some smaller 4-dicritical digraphs to leverage the minimality of D. These smaller 4-dicritical digraphs will be constructed by identifying some vertices of D. This is why, in the definition of the potential, we consider T (D) instead of the number of digons: when identifying a set of vertices, the number of digons may be arbitrary larger in the resulting digraph, but T (D) increases at most by 1. Using the fact that every subdigraph of D has large potential, we will prove that some subdigraphs are forbidden in D. Using this, we get the final contradiction by a discharging argument.

In addition to Theorem 7, Theorem 8 has also the following consequence when we take ε = δ = 0. 10 3 n(D) -4 3 . Moreover, equality holds if and only if D is 4-Ore, otherwise m(D) ⩾ 10 3 n(D) -1. This is a slight improvement on a result of Kostochka and Stiebitz [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF] who proved the inequality m(D) ⩾ 10 3 n(D) -4 3 without characterising the equality case. Another interesting consequence of our result is the following bound on the number of vertices in a 4-dicritical oriented graph embedded on a fixed surface. Since a graph on n vertices embedded on a surface of Euler characteristic c has at most 3n -3c edges, we immediately deduce the following from Theorem 7.

Corollary 9. If D is a 4-dicritical digraph, then m(D) ⩾
Corollary 10. If ⃗ G is a 4-dicritical oriented graph embedded on a surface of Euler characteristic c, then n( ⃗ G) ⩽ 17 6 (1 -3c).
The previous best upper bound was n( ⃗ G) ⩽ 4 -9c [START_REF] Kostochka | The minimum number of edges in 4-critical digraphs of given order[END_REF].

In Section 2 we prove some first preliminary results on 4-Ore digraphs, before proving Theorem 8 in Section 3. In Section 4, we show that o k (n) ⩽ (2k - 7 2 )n for every fixed k and infinitely many values of n. The proof is strongly based on the proof of [START_REF] Aboulker | On the minimum number of arcs in k-dicritical oriented graphs[END_REF]Theorem 4.4], which shows o k (n) ⩽ (2k -3)n for every fixed k, n (with n large enough). For k = 4, the construction implies in particular that there is a 4-dicritical oriented graph with 76 vertices and 330 arcs, and there are infinitely many 4-dicritical oriented graphs with m/n ⩽ 9/2.

The 4-Ore digraphs and their properties

We start with a few notations. We denote by x 1 , . . . , x n the bidirected path with vertex set {x 1 , . . . , x n } in this order. If x 1 = x n , x 1 , . . . , x n denotes the bidirected cycle of order n with cyclic order x 1 , . . . , x n . If D is a digraph, for any X ⊆ V (D), D -X is the subdigraph induced by V (D) \ X. We abbreviate D -{x} into D -x. Moreover, for any

F ⊆ V (D) × V (D), D \ F is the subdigraph (V (D), A(D) \ F ) and D ∪ F is the digraph (V (D), A(D) ∪ F ) Let D 1 ,
z 1 z ∈ A(D 2 ) and z 1 ∈ Z 1 }, {yz 2 | zz 2 ∈ A(D 2 ) and z 2 ∈ Z 2 }, {z 2 y | z 2 z ∈ A(D 2 ) and z 2 ∈ Z 2 }, where (Z 1 , Z 2
) is a partition of N D 2 (z) into non-empty sets. We call D 1 the digon side and D 2 the split side of the Ore-composition. The class of the 4-Ore digraphs is the smallest class containing ← → K 4 which is stable under Ore-composition. See Figure 1 for an example of a 4-Ore digraph. Observe that all the 4-Ore-digraphs are bidirected.

Proposition 11 (Dirac [START_REF] Dirac | On the structure of 5-and 6-chromatic abstract graphs[END_REF], see also [START_REF] Kostochka | A Brooks-type result for sparse critical graphs[END_REF]). 4-Ore digraphs are 4-dicritical.

Proof. One can easily show that a bidirected digraph is 4-dicritical if and only if its undirected underlying graph is 4-critical. Then the result follows from the undirected analogous proved by [START_REF] Dirac | On the structure of 5-and 6-chromatic abstract graphs[END_REF].

Lemma 12. Let D be a 4-dicritical bidirected digraph and v ∈ V (D). Let (N + 1 , N + 2 ) and (N - 1 , N - 2 ) be two partitions of N (v). Consider D ′ the digraph with vertex set

V (D)\{v}∪{v 1 , v 2 } with N + (v i ) = N + i , N -(v i ) = N - i for i = 1, 2 and D ′ ⟨V (D) \ {v}⟩ = D -v.
Then D ′ has a 3-dicolouring with v 1 and v 2 coloured the same except if

N + 1 = N - 1 (that is D ′ is bidirected). Proof. Suppose that D ′ is not bidirected. Consider a vertex u ∈ N D (v) such that v 1 u, uv 2 ∈ A(D ′ ) or v 2 u, uv 1 ∈ A(D ′ ). Without loss of generality, suppose v 1 u, uv 2 ∈ A(D ′ ). As D is 4-dicritical, D \ [u, v] has a proper 3-dicolouring φ. We set φ(v 1 ) = φ(v 2 ) = φ(v)
and claim that φ is a 3dicolouring of D ′ . To show that, observe that φ is a proper 3-colouring of the underlying undirected graph of D ′ \ {v 1 u, uv 2 }, and so φ is a 3-dicolouring of D ′ as wanted.

Lemma 13. Let D be a digraph. If v is a vertex of D, then T (D -v) ⩾ T (D) -1.
Proof. Let M be a packing of d digons and t bidirected triangles in

H such that d + 2t = T (D). If v belongs to a digon [u, v] in M , then M \ {[u, v]} witnesses the fact that T (D -v) ⩾ T (D) -1. If v belongs to a bidirected triangle u, v, w, u , then M \ { u, v, w, u } ∪ [u, v] witnesses the fact that T (D -v) ⩾ T (D) -2 + 1. Otherwise T (D -v) ⩾ T (D).
Lemma 14. If D 1 , D 2 are two digraphs, and D is an Ore-composition of D 1 and D 2 , then

T (D) ⩾ T (D 1 )+T (D 2 )-2. Moreover, if D 1 or D 2 is isomorphic to ← → K 4 , then T (D) ⩾ T (D 1 )+T (D 2 )-1.
Proof. Let D be the Ore-composition of D 1 (the digon side with replaced digon [x, y]) and D 2 (the split side with split vertex z). One can easily see that If T ⊆ D 1 , then by Lemma 16, in D 2 there exists either an Ore-collapsible subdigraph O or an emerald E disjoint from z. In the former case O is an Ore-collapsible subdigraph of D disjoint from T , and in the later one E is an emerald in D disjoint from T .

T (D) ⩾ T (D 1 -x) + T (D -z) ⩾ T (D 1 ) + T (D 2 )-2 by Lemma 13. Moreover, if D 1 (resp. D 2 ) is a copy of ← → K 4 , then T (D 1 -x) = 2 = T (D 1 ) (resp. T (D 2 -z) = 2 = T (D 2 )) and therefore T (D) ⩾ T (D 1 ) + T (D 2 ) -1. Lemma 15. If D is 4-Ore, then T (D) ⩾ 2 3 (n(D) -1). Proof. If D is ← → K 4 , then the result is clear. Suppose now that D is an Ore-composition of D 1 and D 2 . Then n(D) = n(D 1 ) + n(D 2 ) -1 and, by Lemma 14, T (D) ⩾ T (D 1 ) + T (D 2 ) -2. By induction, T (D 1 ) ⩾ 2 3 (n(D 1 ) -1) and T (D 2 ) ⩾ 2 3 (n(D 2 ) -1), and so T (D) ⩾ 2 3 (n(D 1 ) + n(D 2 ) -1 -1) = 2 3 (n(D) -1). Let D be a digraph. A diamond in D is a subdigraph isomorphic to ← → K 4 minus a digon [u, v], with vertices different from u and v having degree 6 in D. An emerald in D is a subdigraph isomorphic to ← → K 3 whose vertices have degree 6 in D. Let R be an induced subdigraph of D with n(R) < n(D). The boundary of R in D, denoted by ∂ D (R), or simply ∂(R) when D is clear from the context, is the set of vertices of R having a neighbour in V (D) \ R. We say that R is Ore-collapsible if the boundary of R contains exactly two vertices u and v and R ∪ [u, v] is 4-Ore. Lemma 16. If D is 4-Ore and v ∈ V (D),
If T ⊆ D 2 -z, then D 1 \ {x, y} is an Ore-collapsible subdigraph disjoint from T . Assume now that T contains a vertex w ∈ {x, y} and two vertices in V (D 2 -z). Without loss of generality, we may assume that y ̸ ∈ T . Let z 1 and z 2 be the two vertices of T disjoint from w.

Then {z, z 1 , z 2 } induces a bidirected triangle T ′ in D 2 . If D 2 ̸ = ⃗ K 4
, then by induction in D 2 , there exists either an Ore-collapsible subdigraph O or an emerald E disjoint from T ′ . In the former case O is an Ore-collapsible subdigraph of D disjoint from T , and in the later one E is an emerald in D disjoint from T .

Henceforth we may assume that D 2 = ← → K 4 . This implies that y has exactly one neighbour in D 2 -z and so its degree is the same in D 1 and D. By Lemma 16, in D 1 there exists either an Ore-collapsible subdigraph O or an emerald E disjoint from x. In the former case O is an Orecollapsible subdigraph of D disjoint from T , and in the later one E is an emerald in D disjoint from T even if y ∈ V (E) because y has the same degree in D 1 and D.

Lemma 18. If R is an Ore-collapsible induced subdigraph of a 4-Ore digraph D, then there exists a diamond or an emerald of D whose vertices lie in V (R).

Proof. Let D be a digraph. Let R be a minimal counterexample to this lemma, and let

∂(R) = {u, v} and H = D⟨R⟩ ∪ [u, v]. If H = ← → K 4 , then R is a diamond in D.
Suppose now that H is the Ore-composition of two 4-Ore digraphs H 1 (the digon side with replaced digon [x, y]) and H 2 (the split side with split vertex z). If {u, v} ̸ ⊂ V (H 2 ), then by Lemma 16 there exists an Orecollapsible subdigraph in H 2 disjoint from z. As it is smaller than H, it contains an emerald or a diamond as desired, a contradiction. Now assume that {u, v} ⊂ V (H 2 ), then H 1 is an Ore-collapsible subdigraph of D smaller than H, and by induction, H 1 contains a diamond or an emerald in D. The following theorem was formulated for undirected graphs, but by replacing every edge by a digon, it can be restated as follows:

Theorem 21 (Kostochka and Yancey [START_REF] Kostochka | A Brooks-type result for sparse critical graphs[END_REF], Theorem 6). Let D be a 4-dicritical bidirected digraph.

If

10 3 n(D) -m(D) > 1, then D is 4-Ore and 10 3 n(D) -m(D) = 4 3 . Lemma 22. If D is a 4-Ore digraph with n vertices, then ρ(D) ⩽ 4 3 + εn -δ 2(n-1) 3 .
Proof. Follows from Theorem 21 and Lemma 15.

Lemma 23 (Kostochka and Yancey [START_REF] Kostochka | A Brooks-type result for sparse critical graphs[END_REF], Claim 16).

Let D be a 4-Ore digraph. If R ⊆ D and 0 < n(R) < n(D), then 10 3 n(R) -m(R) ⩾ 10 3 .
Lemma 24. Let D be a 4-Ore digraph obtained from a copy J of ← → K 4 by successive Orecompositions with 4-Ore digraphs, vertices and digons in J being always on the digon side. Let [u, v] be a digon in D⟨V (J)⟩. For every 3-dicolouring φ of D \ [u, v], vertices in V (J) receive distinct colours except u and v.

Proof. We proceed by induction on n(D), the result holding trivially when D is ← → K 4 . Now assume that D is the Ore-composition of D 1 , the digon side containing J, and D 2 , with D 1 and D 2 being 4-Ore digraphs. Let [x, y] ⊆ A(D 1 ) be the replaced digon in this Ore-composition, and let z ∈ V (D 2 ) be the split vertex. Let φ be a Lemma 25. Let D be a 4-Ore digraph obtained from a copy J of ← → K 4 by successive Orecompositions with 4-Ore digraphs, vertices and digons in J being always on the digon side. Let v be a vertex in V (J). For every 3-dicolouring φ of D -v, vertices in J receive distinct colours.

3-dicolouring of D \ [u, v]. Then φ induces a 3-dicolouring of D⟨V (D 2 -z) ∪ {x, y}⟩. Necessarily φ(x) ̸ = φ(y), for otherwise φ 2 defined by φ 2 (v) = φ(v) if v ∈ V (D 2 -z) and φ 2 (z) = φ(x) is a 3-dicolouring of D 2 ,
Proof. We proceed by induction on n(D), the result holding trivially when D is ← → K 4 . Now assume that D is the Ore-composition of D 1 , the digon side containing J, and D 2 , with D 1 and D 2 being 4-Ore digraphs. Let [x, y] ⊆ A(D 1 ) be the replaced digon in this Ore-composition, and let z ∈ V (D 2 ) be the split vertex. Let φ be a 3-

dicolouring of D -v. If v ∈ {x, y}, then φ is a 3- dicolouring of D 1 -v and the result follows by induction. Now assume v ̸ ∈ {x, y}. Then φ induces a 3-dicolouring of D⟨V (D 2 -z) ∪ {x, y}⟩. Necessarily φ(x) ̸ = φ(y), for otherwise φ 2 defined by φ 2 (v) = φ(v) if v ∈ V (D 2 -z) and φ 2 (z) = φ(x) is a 3-dicolouring of D 2 ,
contradicting the fact that 4-Ore digraphs have dichromatic number 4 by Lemma 11. Hence φ induces a 3-dicolouring of D 1 -v. So, by the induction hypothesis, vertices in V (J) have distinct colours in φ.

Proof of Theorem 8

Let D be a 4-dicritical digraph, R be an induced subdigraph of D with 4 ⩽ n(R) < n(D) and φ a 3-dicolouring of R. The φ-identification of R in D, denoted by D φ (R) is the digraph obtained from D by identifying for each i ∈ [START_REF] Aboulker | Various bounds on the minimum number of arcs in a k-dicritical digraph[END_REF] the vertices coloured i in V (R) to a vertex x i , adding the digons [x i , x j ] for all 1 ⩽ i < j ⩽ 3. Observe that D φ (R) is not 3-dicolourable. Indeed, assume for a contradiction that D φ (R) has a 3-dicolouring φ ′ . Since {x 1 , x 2 , x 3 } induces a ← → K 3 , we may assume without loss of generality that φ 2 for an example of a φ-identification and a dicritical extension.

′ (x i ) = i for i ∈ [3]. Consider the 3-colouring φ ′′ of D defined by φ ′′ (v) = φ ′ (v) if v ̸ ∈ R and φ ′′ (v) = φ(v) if v ∈ R. One easily checks that φ ′′ is a 3-dicolouring of D, a contradiction to the fact that ⃗ χ(D) = 4. Now let W be a 4-dicritical subdigraph of D φ (R) and X = {x 1 , x 2 , x 3 }. Then we say that R ′ = D⟨(V (W ) \ X) ∪ R⟩ is the dicritical extension of R with extender W . We call X W = X ∩ V (W ) the core of the extension. Note that X W is not empty, because W is not a subdigraph of D. Thus 1 ⩽ |X W | ⩽ 3. See Figure
Let D be a counterexample to Theorem 8 with minimum number of vertices. By Lemma 22, D is not 4-Ore. Thus ρ(D) > 1.

Claim 1. If D is a 4-dicritical digraph with n( D) < n(D), then ρ( D) ⩽ 4 3 + 4ε -2δ. R D X X W W D φ (R) R ′
⩽ 4 3 + 4ε -2δ because δ ⩾ 3 2 ε and n( D) ⩾ 4. ♢ Claim 2. Let R be a subdigraph of D with 4 ⩽ n(R) < n(D). If R ′ is a dicritical extension of R with extender W and core X W , then ρ(R ′ ) ⩽ ρ(W ) + ρ(R) -ρ( ← --→ K |X W | ) + δ • T ( ← --→ K |X W | ) + δ • (T (W ) -T (W -X W ))
and in particular

ρ(R ′ ) ⩽ ρ(W ) + ρ(R) - 10 3 -ε + δ.
Proof of claim. We have

• n(R ′ ) = n(W ) -|X W | + n(R), • m(R ′ ) ⩾ m(W ) + m(R) -m( ← --→ K |X W | ), • T (R ′ ) ⩾ T (W -X W ) + T (R)
and by summing these inequalities, we get the first result. Now observe that T (W ) -T (W -X W ) ⩽ |X W | by Lemma 13, and that the maximum of

-ρ( ← --→ K |X W | ) + δT ( ← --→ K |X W | ) + δ|X W | is reached when |X W | = 1, in which case it is equal to -10 3 -ε + δ. The second inequality follows. ♢ Claim 3. If R is a subdigraph of D with 4 ⩽ n(R) < n(D), then ρ(R) ⩾ ρ(D) + 2 -3ε + δ > 3 -3ε + δ.
Proof of claim. We proceed by induction on n -n(R). Let R ′ be a dicritical extension of R with extender W and core X W . By Claim 2, we have

ρ(R ′ ) ⩽ ρ(W ) + ρ(R) - 10 3 -ε + δ. Either V (R ′ ) = V (D) and so ρ(R ′ ) ⩾ ρ(D) or V (R ′ ) is a proper subset of V (D) and, since R is a proper subdigraph of R ′ , by induction ρ(R ′ ) ⩾ ρ(D) + 2 -3ε + δ ⩾ ρ(D). In both cases, ρ(R ′ ) ⩾ ρ(D). Now W is smaller than D so ρ(W ) ⩽ 4 3 + 4ε -2δ by Claim 1. Thus ρ(D) ⩽ ρ(R ′ ) ⩽ 4 3 + 4ε -2δ + ρ(R) - 10 3 -ε + δ. This gives ρ(R) ⩾ ρ(D) + 2 -3ε + δ > 3 -3ε + δ, because ρ(D) > 1. ♢
As a consequence of Claim 3, any subdigraph (proper or not) of size at least 4 has potential at least ρ(D).

We say that an induced subdigraph R of D is collapsible if, for every 3-dicolouring φ of R, its dicritical extension R ′ (with extender W and core X W ) is D, has core of size 1 (i.e. |X W | = 1), and the border

∂ D (R) of R is monochromatic in φ. Claim 4. Let R be an induced subdigraph of D and φ a 3-dicolouring of R such that ∂(R) is not monochromatic in φ. If D is a dicritical extension of R dicoloured by φ with extender W and core X W with |X W | = 1, then ρ(R) ⩾ ρ(D) + 3 -3ε + δ.
Proof of claim. Assume D is a dicritical extension of R dicoloured by φ with extender W and core X W with |X W | = 1. Observe that each of the following inequalities holds:

• n(D) = n(W ) -|X W | + n(R) = n(X) + n(R) -1, • m(D) ⩾ m(W ) + m(R) -m( ← --→ K |X W | ) + 1 = m(W ) + m(R) + 1 because ∂ D (R) is not monochromatic in φ, and • T (D) ⩾ T (W -X W ) + T (R) ⩾ T (W ) + T (R) -1 by Lemma 13.
By Claim 1, we have

ρ(D) ⩽ ρ(W ) + ρ(R) - 10 3 + ε -1 + δ ⩽ 4 3 + 4ε -2δ + ρ(R) - 13 3 -ε + δ and so ρ(R) ⩾ ρ(D) + 3 -3ε + δ. ♢ Claim 5. If R is a subdigraph of D with 4 ⩽ n(R) < n(D) and R is not collapsible, then ρ(R) ⩾ ρ(D) + 8 3 -ε -δ > 11 3 -ε -δ.
Proof of claim. Let R ′ be a dicritical extension of R dicoloured by φ with extender W and core X W .

(i) If R ′ is not D, then it has a dicritical extension R ′′ with extender W ′ . By (the consequence of) Claim 3, we have ρ(D) ⩽ ρ(R ′′ ) ; by Claim 2 (applied twice), ρ(R ′′ ) ⩽ ρ(R)+ρ(W ′ )+ρ(W )+ 2 - 10 3 -ε + δ ; both W and W ′ are smaller than D, so, by Claim 1, ρ(W ), ρ(W ′ ) ⩽ 4 3 +4ε-2δ. Those three inequalities imply

ρ(D) ⩽ ρ(R ′′ ) ⩽ ρ(R) + 2 4 3 + 4ε -2δ + 2 - 10 3 -ε + δ = ρ(R) -4 + 6ε -2δ and so ρ(R) ⩾ ρ(D) + 4 -6ε + 2δ ⩾ ρ(D) + 8 3 -ε -δ. (ii) If R ′ = D and |X W | = 2, then ρ( ← --→ K |X W | ) + δT ( ← --→ K |X W | ) = 14 3 + 2ε
, and, by Lemma 13,

T (W ) -T (W -X W ) ⩽ |X w | = 2. Thus, by Claim 2, ρ(D) ⩽ ρ(W ) + ρ(R) - 14 3 -2ε + 2δ
Now, since W is smaller than D, ρ(W ) ⩽ 4 3 + 4ε -2δ by Claim 1. Thus

ρ(D) ⩽ ρ(R) + 4 3 + 4ε -2δ - 14 3 -2ε + 2δ = ρ(R) - 10 3 + 2ε
and so ρ(R) ⩾ ρ(D)

+ 10 3 -2ε ⩾ ρ(D) + 8 3 -ε -δ. (iii) If R ′ = D and |X W | = 3, then ρ( ← --→ K |X W | ) + δT ( ← --→ K |X W | ) = 4 +
ρ(D) ⩽ ρ(R) + 4 3 + 4ε -2δ -4 -3ε + 3δ = ρ(R) - 8 3 + ε + δ and so ρ(R) ⩾ ρ(D) + 8 3 -ε -δ. (iv) If R ′ = D, |X W | = 1 and ∂(R) is not monochromatic in φ, then, by Claim 4, we have ρ(R) ⩾ ρ(D) + 3 -3ε + δ ⩾ ρ(D) + 8 3 -ε -δ. If R is not collapsible, then
, by definition, it has a dicritical extension R ′ satisfying the hypothesis of one of the cases (i)-(iv). In any case, ρ(R) ⩾ ρ(D) + 8 3 -ε -δ. ♢

Recall that a k-cutset in a graph G is a set S of k vertices such that G -S is not connected. A graph is k-connected if it has more than k vertices and has no (k -1)-cutset. A k-cutset in a digraph is a k-cutset in its underlying graph, and a digraph is k-connected if its underlying graph is k-connected. Claim 6. D is 2-connected.

Proof of claim. Suppose for contradiction that {x} is a 1-cutset in D. Let (A 0 , B 0 ) be a partition of V (D -x) into non-empty sets such that there is no edge between A 0 and B 0 , and set A = A 0 ∪ {x} and B = B 0 ∪ {x}.

Since D is 4-dicritical, there exist a 3-dicolouring φ A of D⟨A⟩ and a 3-dicolouring φ B of D⟨B⟩. Free to swap the colours, we may assume φ A (x) = φ B (x). Let φ be defined by φ Proof of claim. Suppose for contradiction that {x, y} is a 2-cutset of D. Let (A 0 , B 0 ) be a partition of V (D) \ {x, y} into non-empty sets such that there is no edge between A 0 and B 0 , and set A = A 0 ∪ {x, y} and B = B 0 ∪ {x, y}.

(v) = φ A (v) if v ∈ A and φ(v) = φ B (v) if v ∈ B. Since ⃗ χ(D) = 4,
Assume for a contradiction that there exists a 3-dicolouring φ A of D⟨A⟩ and a 3-dicolouring φ B of D⟨B⟩ such that φ A (x) ̸ = φ A (y) and φ B (x) ̸ = φ B (y). Free to swap the colours, we may assume φ A (x) = φ B (x) and φ A (y) = φ B (y). Let φ be defined by φ

(v) = φ A (v) if v ∈ A and φ(v) = φ B (v) if v ∈ B.
Every directed cycle either is in D⟨A⟩, or is in D⟨B⟩ or contains both x and y. Therefore it cannot be monochromatic with φ because φ A and φ B are 3-dicolourings of D⟨A⟩ and D⟨B⟩ respectively, and φ(x) ̸ = φ(y). Thus φ is a 3-dicolouring of D, a contradiction. Henceforth either D⟨A⟩ or D⟨B⟩ has no 3-dicolouring φ such that φ(x) ̸ = φ(y). Suppose without loss of generality that it is D⟨A⟩.

Let D A = D⟨A⟩ ∪ [x, y]. D A is not 3-dicolourable because in every 3-dicolouring of D⟨A⟩, x and y are coloured the same. Let D B be the digraph obtained from D⟨B⟩ by identifying x and y into a vertex z. Assume for a contradiction that D B has a 3-dicolouring ψ B . Set ψ(x) = ψ(y) = ψ B (z), and ψ(u) = ψ B (u) for every u ∈ B \ {x, y}. Then consider a 3-dicolouring ψ A of D⟨A⟩ such that ψ A (x) = ψ(x) = ψ A (y) = ψ(y) (such a colouring exists because A is a proper subdigraph of D) and we set ψ(u) = ψ A (u) for ever u ∈ V (A)\{x, y}. As D is not 3-dicolourable, it contains a monochromatic directed cycle C (with respect to ψ). The cycle C is not included in D⟨A⟩ nor in D B . As a consequence, there is a monochromatic directed path from {x, y} to {x, y} in B, and so there is a monochromatic directed cycle in D B for ψ B , a contradiction. Therefore D B is not 3-dicolourable Now D A has a 4-dicritical subdigraph W A which necessarily contains {x, y}, and D B has a 4-dicritical subdigraph W B which necessarily contains z. As W A and W B are 4-dicritical digraphs smaller than D, we have ρ(W A ), ρ(W B ) ⩽ 4 3 + 4ε -2δ by Claim 1. Let H be the subdigraph of D induced by

V (W A ) ∪ V (W B -z). Note that n(H) = n(W A ) + n(W B ) -1 and m(H) ⩾ m(W A ) + m(W B ) -2. Moreover T (H) ⩾ T (W A -x) + T (W B -z) ⩾ T (W A ) + T (W B ) -2, by Lemma 13. Hence we have ρ(H) ⩽ ρ(W A ) + ρ(W B ) - 10 3 + ε + (m(W A ) + m(W B ) -m(H)) + 2δ ⩽ ρ(W A ) + ρ(W B ) - 10 3 -ε + 2 + 2δ = ρ(W A ) + ρ(W B ) - 4 3 -ε + 2δ (1)
⩽ 2 4 3 + 4ε -2δ - 4 3 -ε + 2δ = 4 3 + 7ε -2δ By Claim 3, if n(H) < n(D) then ρ(H) > 3 -3ε + δ. As 10ε -3δ ⩽ 5 3 , we deduce that H = D. Hence 1 < ρ(D) = ρ(H) ⩽ 4 3 + 7ε -2δ + (m(W A ) + m(W B ) -m(H) -2) and so m(H) = m(W A ) + m(W B ) -2 because 2δ -7ε ⩽ 2 3 .
In particular, there is no arc between x and y in D. Moreover, no arc was suppressed when identifying x and y into z to obtain D B , so x and y have no common out-neighbour (resp. in-neighbour) in B 0 .

We first show that either W A or W B is not 4-Ore. Assume for contradiction that both W A and W B are 4-Ore. If H = D is not bidirected, then by Lemma 12, D⟨B⟩ admits a 3-dicolouring φ B such that φ B (x) = φ B (y). Now let φ A be a 3-dicolouring of D⟨A⟩. We have φ A (x) = φ A (y). Free to exchange colour we may assume,

φ A (x) = φ A (y) = φ B (x) = φ B (y). Hence we can define the 3-colouring φ of D by φ(v) = φ A (v) if v ∈ A, and φ(v) = φ B (v) if v ∈ B.
Observe that, since A is bidirected, all neighbours of x and y in D⟨A⟩ have a colour distinct from φ(x). Therefore there is no monochromatic directed cycle in D coloured by φ. Thus φ is a 3-dicolouring of D, a contradiction. Therefore, H = D is bidirected, and so H is an Ore-composition of W A and W B (because D is 2-connected by Claim 6), and so D is 4-Ore, a contradiction. Henceforth, we may assume that either W A or W B is not 4-Ore.

If none of W A and W B are is a 4-Ore, then by minimality of D, ρ(W A ) ⩽ 1 and ρ(W B ) ⩽ 1. Together with Equation (1), this yields

ρ(H) ⩽ 2 3 -ε + 2δ ⩽ 1 because 2δ -ε ⩽ 1 3 , a contradiction. If none of W A and W B is ← → K 4 , then ρ(W A ) + ρ(W B ) ⩽ 1 + ( 4 3 + 7ε -4δ) (recall that if a digraph is 4-Ore but not ← → K 4
, then it has potential at most 4 3 + 7ε -4δ by Lemma 22). Thus, with Equation (1), we get Lemma 13, and so

ρ(H) ⩽ 1 + 4 3 + 7ε -4δ - 4 3 -ε + 2δ = 1 + 6ε -2δ ⩽ 1 because δ ⩾ 3ε.

Finally, if exactly one of W

A or W B is isomorphic to ← → K 4 , then either T (W A -x) = T (W A ) = 2 (if W A = ← → K 4 ) or T (W B -z) = T (W B ) = 2 (if W B = ← → K 4 ). Therefore T (H) ⩾ T (W A -x) + T (W B -z) ⩾ T (W A ) + T (W B ) -1 by
ρ(H) ⩽ ρ(W A ) + ρ(W B ) - 10 3 + ε + 2 + δ.
Now the non 4-Ore digraph among W A , W B has potential at most 1 and the other has potential ρ( If

← → K 4 ) = 4 3 + 4ε -2δ. Thus ρ(H) ⩽ 1 + 4 3 + 4ε -2δ - 10 3 + ε + 2 + δ = 1 + 3ε -δ ⩽ 1 because δ ⩾ 3ε. In all three cases, ρ(D) = ρ(H) ⩽ 1, which is a contradiction. Hence D is 3-connected. ♢ Claim 8. If R is a collapsible subdigraph of D, u, v are in the boundary of R and D⟨R⟩ ∪ [u, v] is 4-Ore, then there exists R ′ ⊆ R such that (i) either R ′ is an Ore-collapsible subdigraph of D, or (ii) R ′ is an induced subdigraph of R, n(R ′ ) < n(R), and there exist u ′ , v ′ in ∂ D (R ′ ) such that R ′ ∪ [u ′ , v ′ ] is 4-Ore. Proof of claim. If ∂(R) = {u,
u or v is in V (H 2 ), then R ′ = D⟨V (H 1 )⟩ with u ′ = x, v ′ = y satisfies (ii). Now we assume that u, v ∈ V (H 1 ) \ V (H 2 )
. By repeating this argument successively on H 1 , and then on the digonside of H 1 , etc, either we find a subdigraph R ′ satisfying (ii) or u and v are in a copy J of ← → K 4 such that H is obtained by Ore-compositions between J and some 4-Ore digraphs with J being always in the digon side.

Observe that w ̸ ∈ V (J) because in any 3-dicolouring of H \[u, v], vertices in J receive different colours by Lemma 24, except u and v. Hence at one step in the succession of Ore-compositions, w was in the split-side S when a digon e in J has been replaced. However e ̸ = [u, v], so either u or v is not in e. Suppose without loss of generality that e is not incident to v.

We claim that

H ′ = R -v ∪ [u, w] is not 3-dicolourable.
Otherwise, let φ be a 3-dicolouring of H ′ . Then φ is a 3-dicolouring of H -v with H 4-Ore, so vertices in J -v must receive pairwise different colours by Lemma 25. Let φ ′ be a 3-dicolouring of R. Without loss of generality, we may assume that φ(x) = φ ′ (x) for every x ∈ V (J -v). If y ∈ S, let φ ′′ (y) = φ(y), and let φ ′′ (y) = φ ′ (y) if y ̸ ∈ S. Then φ ′′ is a 3-dicolouring of R but with φ(u) ̸ = φ(w), contradicting the fact that R is collapsible. This shows that

H ′ = R -v ∪ [u, w] is not 3-dicolourable.
This implies that D does not contain any collapsible subdigraph. Indeed, assume for a contradiction that D contains a collapsible subdigraph R, and let u, v be two vertices in its boundary. Then there exists a 3-dicolouring

φ of R ∪ [u, v], for which ∂(R) is not monochromatic, a contra- diction. ♢ Claim 10. If R is a subdigraph of D with n(R) < n(D) and u, v, u ′ , v ′ ∈ R, then R ∪ {uv, u ′ v ′ } is 3-dicolourable.
In particular, D contains no copy of ← → K 4 minus two arcs.

Proof of claim. Assume for a contradiction that the statement is false. Consider a smallest subdigraph R for which the statement does not hold. Then K = R ∪ {uv, u ′ v ′ } is 4-dicritical and smaller than D, so ρ(K) ⩽ 4 3 + 4ε -2δ by Claim 1. By Claim 9, R is not collapsible, so, by Claim 5, we have ρ(R) ⩾ ρ(D)

+ 8 3 -ε -δ > 11 3 -ε -δ. But ρ(R) ⩽ ρ(K) + 2 + 2δ ⩽ 10 3 + 4ε, which is a contradiction as 5ε + δ ⩽ 1 3 . ♢ For any v ∈ V (D), we denote by n(v) its number of neighbours, that is n(v) = |N + (u) ∪ N -(v)|, and by d(v) its number of incident arcs, that is d(v) = d + (v) + d -(v).
Claim 11. Vertices of degree 6 in D have either three or six neighbours.

Proof of claim. Let x be a vertex of degree 6.

If n(x) = 4, then let a, b, c, d be its neighbours such that

N + (x) = {a, b, c} and N -(x) = {a, b, d}. Consider D ′ = D -x ∪ dc. By Claim 10, D ′ has a 3-dicolouring φ. If |φ(N -(x))| < 3, then choosing φ(x) in {1, 2, 3} \ φ(N -(x)),
D ′ = D -x ∪ db ∪ dc. By Claim 10, D ′ has a 3-dicolouring φ. If |φ(N -(x))| < 3, then choosing φ(x) in {1, 2, 3} \ φ(N -(x))
, we obtain a 3-dicolouring of D, a contradiction. Hence φ(N -(x)) = {1, 2, 3}. We set φ(x) = φ(d). As D is not 3-dicolourable, there is a monochromatic directed cycle C, which must contain the arc dx and an out-neighbour z of x. Note that z must be b or c because φ(a)

̸ = φ(d). Then C -x ∪ dz is a monochromatic directed cycle in D ′ , a contradiction. ♢ Claim 12.
There is no bidirected triangle containing two vertices of degree 6. In particular, D contains no emerald. Proof of claim. Let R be an induced subdigraph of D with 4 ⩽ n(R) < n(D). By Claim 9, R is not collapsible. Let φ be a 3-dicolouring of R, R ′ be a dicritical extension of R with extender W and core X W (with respect to φ). By (the consequence of) Claim 3, we know that ρ(R ′ ) ⩾ ρ(D).

Assume first that R ′ ̸ = D. Then, by Claims 3 and 2,

ρ(D) + 2 -3ε + δ ⩽ ρ(R ′ ) ⩽ ρ(W ) + ρ(R) - 10 3 -ε + δ. Since ρ(W ) ⩽ 4 3 + 4ε -2δ by Claim 1, we have ρ(R) ⩾ ρ(D) + 4 -6ε + 2δ ⩾ ρ(D) + 3 + 3ε -3δ, because 1 ⩾ 9ε -5δ.
In the following we suppose that R ′ = D. We distinguish three cases depending on the cardinality of |X W |.

• Assume first that |X W | = 2. Then, by Claim 2 and Lemma 13,

ρ(D) ⩽ ρ(R ′ ) ⩽ ρ(W ) + ρ(R) - 20 3 -2ε + 2 + 2δ
and, as ρ(W ) ⩽ 4 3 +4ε-2δ by Claim 1, we have ρ(R) ⩾ ρ(D)+ 10 3 -2ε ⩾ ρ(D)+3+3ε-3δ because 5ε -3δ ⩽ 1 3 .

• Assume now that |X W | = 3. If there is a vertex v ∈ V (D -R) with two out-neighbours (resp. two in-neighbours) in V (R) with the same colour for φ, then

-n(R ′ ) = n(W ) -|X W | + n(R), -m(R ′ ) ⩾ m(W ) + m(R) -m( ← --→ K |X W | ) + 1 because v has two in-or out-neighbour in V (R) with the same colour for φ, -T (R ′ ) ⩾ T (W -X W ) + T (R). It follows that ρ(D) ⩽ ρ(R ′ ) ⩽ ρ(W ) + ρ(R) -(10 + 3ε -6) + 3δ -1 and so ρ(R) ⩾ ρ(D) -4 3 -4ε + 2δ + 5 + 3ε -3δ ⩾ ρ(D) + 11 3 -ε -δ ⩾ ρ(D) + 3 + 3ε -3δ because 4ε -2δ ⩽ 2
3 . Now we assume that there is no vertex with two out-neighbours (resp. two in-neighbours) in R with the same colour for φ. In other words, the in-degrees and out-degrees of vertices in D -R are the same in D and in W .

♢

In D, we say that a vertex v is a simple in-neighbour (resp. simple out-neighbour) if v is a in-neighbour (resp. out-neighbour) of u and [u, v] is not a digon in D. If v is a simple in-neighbour or simple out-neighbour of u, we simply say that v is a simple neighbour of u.

Claim 14. Vertices of degree 7 have seven neighbours. In other words, every vertex of degree 7 has only simple neighbours.

Proof of claim. Let x be a vertex of degree 7. We suppose, without loss of generality, that d -(x) = 3 and d + (x) = 4.

If n(x) = 4, then x has a unique simple out-neighbour a. As D is 4-dicritical, D \ xa has a 3-dicolouring φ. But then every directed cycle is either in D \ xa or it contains xa and thus an inneighbour t of x. In the first case, it is not monochromatic because φ is a 3-dicolouring of D \ xa, and in the second case, it is not monochromatic because [t, x] is a digon and so φ(t) ̸ = φ(x). Hence φ is a 3-dicolouring of D, a contradiction. We first show that D ′ is not 3-dicolourable. Assume for a contradiction that there is a 3- Thus

dicolouring φ of D ′ . If |φ(N -(x))| < 3, then choosing φ(x) in {1, 2, 3} \ φ(N -(x))
ρ(D) ⩽ ρ( D) + 2 10 3 + ε -8 + δ ⩽ 4 3 + 4ε -2δ - 4 3 + 2ε + δ by Claim 1, ⩽ 1 because 6ε -δ ⩽ 1.
This is a contradiction.

• Assume now that a, c ∈ V (U ), then we have

• n(U ) = n( D) + 1, • m(U ) ⩾ m( D) + 4 and • T (U ) ⩾ T ( D -b) ⩾ T ( D) -1 by Lemma 13. Thus ρ(U ) ⩽ ρ( D) + 10 3 + ε -4 + δ ⩽ 4 3 + 4ε -2δ + 10 3 + ε -4 + δ by Claim 1, ⩽ 1 because 5ε -δ ⩽ 1 3 .
Together with the consequence of Claim 3, we get that ρ(D) ⩽ ρ(U ) ⩽ 1, a contradiction. ♢

The 8 + -valency of a vertex v, denoted by ν(v), is the number of arcs incident to v and a vertex of degree at least 8.

Let D 6 be the subdigraph of D induced by the vertices of degree 6 incident to digons. Let us describe the connected components of D 6 and their neighbourhoods. Remember that vertices of degree 7 are incident to no digon by Claim 14, and so they do not have neighbours in V (D 6 ). If v is a vertex in D 6 , we define its neighbourhood valency to be the sum of the 8 + -valency of its neighbours of degree at least 8. We denote the neighbourhood valency of v by ν N (v). Let u and v be the two neighbours of x different from y. By Claim 14, u and v have degree 6 or at least 8.

If u and v are linked by a digon, then by Claim 12, u and v do not have degree 6, so they have degree 8. Moreover ν(u) ⩾ 2 and ν(v) ⩾ 2. Thus ν N (x) = ν(u) + ν(v) ⩾ 4 and (ii) holds. Henceforth, we may assume that u and v are not linked by a digon.

Let D ′ the digraph obtained by removing x and y and identifying u and v into a single vertex u⋆v. We claim that D ′ is not 3-dicolourable. To see that, suppose for contradiction that there exists a 3-dicolouring φ of D ′ . Then set φ(u) = φ(v) = φ(u⋆v), choose φ(y) in {1, 2, 3}\φ(N (y)\{x}), and finally choose φ(x) in {1, 2, 3} \ {φ(u ⋆ v), φ(y)}. One can easily see that φ is now a 3dicolouring of D, a contradiction. This proves that D ′ is not 3-dicolourable and so it contains a 4-dicritical digraph D, which must contain u ⋆ v because every subdigraph of D is 3-dicolourable. Let R be the subdigraph of D induced by (V ( D) \ {u ⋆ v}) ∪ {u, v, x}. We have

• n(R) = n( D) + 2, • m(R) ⩾ m( D) + 4 and • T (R) ⩾ T ( D -u ⋆ v) + 1 ⩾ T ( D) because [x,
u] is a digon, and by Lemma 13.

If D is not 4-Ore, then ρ( D) ⩽ 1 by minimality of D, and so

ρ(R) ⩽ ρ( D) + 2 10 3 + ε -4 ⩽ 1 + 8 3 + 2ε < ρ(D) + 3 + 3ε -3δ because ε -3δ ⩾ - 1 3 . Similarly, if D is 4-Ore but not ← → K 4 , then ρ(R) ⩽ ρ( D) + 2 10 3 + ε -4 ⩽ 4 3 + 7ε -4δ + 8 3 + 2ε by Lemma 22, = 1 + 3 + 9ε -4δ < ρ(D) + 3 + 9ε -4δ ⩽ ρ(D) + 3 + 3ε -3δ because δ ⩾ 6ε.
In both cases (that is when D is not ← → K 4 ), by Claim 13, D -R is a single vertex of degree 6, namely y. Then every neighbour w of y different from x has degree at least 6 in D (because D is 3-dicritical) and so has degree at least 8 in D and (i) holds.

Assume now that D is a copy of ← → K 4 . Let us denote by a, b, c the vertices of D different from u ⋆ v. Suppose for a contradiction that u has degree 6. Then u has exactly three neighbours by Claim 11. If |N (u) ∩ {a, b, c}| = 2, then D⟨{u, a, b, c}⟩ is a copy of ← → K 4 minus a digon, contradicting Claim 9. If |N (u) ∩ {a, b, c}| ⩽ 1, then v must be adjacent to at least two vertices of {a, b, c} with a digon, and so D⟨{v, a, b, c}⟩ contains a copy of ← → K 4 minus a digon, contradicting Claim 9. Hence u has degree at least 8, and by symmetry so does v. Moreover D⟨{a, b, c}⟩ is a bidirected triangle, and so by Claim 12, at least two of these vertices have degree at least 8 (remember that vertices of degree 7 are in no digon by Claim 14). Hence at least four arcs between {u, v} and {a, b, c} are incident to two vertices of degree at least 8. In other word, ν N (x) = ν(u) + ν(v) ⩾ 4, so (ii) holds. ♢ Claim 16. Let C be a connected component of D 6 . Then C is one of the following (see Figure 3):

(i) a single vertex, or (ii) a bidirected path on two vertices, or Symmetrically, we say that an arc xy is in-chelou if yx is out-chelou in the digraph obtained from D by reversing every arc. See Figure 4 for an example of an out-chelou arc.

ν N ⩾ 4 ν N ⩾ 4 ν N ⩾ 4 ν N ⩾ 4 ν N ⩾ 4
Claim 17. There is no out-chelou arc and no in-chelou arc in D. We now redistribute this total charge according to the following rules:

⃗ C 3 ⃗ C 3 ⃗ C 3 ⃗ C 3 ⃗ C 3
⃗ G 3 ⃗ G 3 ⃗ G 3 ⃗ G 3 ⃗ G 3 ⃗ G 3
n k = k + k 2 n k-1 m k = k 2 + k 2 × 2 × n k-1 + k 2 × m k-1 ⩽ k 2 + k 2 2 + 2(k -1) - 7 2 n k-1 = k 2 + k 2 2k - 7 2 n k-1 = k 2 + 2k - 7 2 (n k -k) ⩽ 2k - 7 2 n k
where in the last inequality we used k 2k -7 2 ⩾ k 2 , which holds when k ⩾ 2. We will now prove that ⃗ G k is indeed k-dicritical.

We first prove that ⃗ χ( ⃗ G k ) = k. Assume that there exists a (k -1)-dicolouring α of ⃗ G k . Then there exist x, y ∈ V (T ) such that α(x) = α(y). Since ⃗ χ( ⃗ G k-1 ) = k -1, there exists

Let

  D be a digraph. We denote by V (D) its vertex set and by A(D) its arc set; we set n(D) = |V (D)| and m(D) = |E(D)|. A k-colouring of D is a function φ : V (D) → [k]. It is a kdicolouring if every directed cycle C in D is not monochromatic for φ (that is |φ(V (C))| > 1).

Figure 1 :

 1 Figure 1: An example of a 4-Ore digraph obtained by an Ore-composition of two smaller 4-Ore digraphs, with replaced digon [x, y] and split vertex z.

  then there exists either an Ore-collapsible subdigraph of D disjoint from v or an emerald of D disjoint from v. Proof. If D is a copy of ← → K 4 , then D -v is an emerald. Otherwise, D is the Ore-composition of two 4-Ore digraphs: D 1 the digon side with replaced digon [x, y], and D 2 the split side with split vertex z. If v ∈ V (D 2 -z), then D 1 \ {x, y} is an Ore-collapsible subdigraph with boundary {y, z}. Otherwise v ∈ V (D 1 ) and we apply induction on D 2 to find an emerald or an Ore-collapsible subdigraph in D 2 disjoint from z. Lemma 17. If D ̸ = ← → K 4 is 4-Ore and T is a copy of ← → K 3 in D, then there exists either an Orecollapsible subdigraph of D disjoint from T or an emerald of D disjoint from T . Proof. As D is not ← → K 4 , it is an Ore-composition of two 4-Ore digraphs: D 1 the digon side with replaced digon [x, y], and D 2 the split side with split vertex z. As x and y are non adjacent, we have either T ⊆ D 1 , T ⊆ D 2 -z, or T contains a vertex w ∈ {x, y} and two vertices in V (D 2 -z).

Lemma 19 .

 19 If D is a 4-Ore digraph and v is a vertex in D, then D contains a diamond or an emerald disjoint from v. Proof. Follows from Lemmas 16 and 18. Lemma 20. If D is a 4-Ore digraph and T is a bidirected triangle in D, then either D = ← → K 4 or D contains a diamond or an emerald disjoint from T . Proof. Follows from Lemmas 17 and 18.

  contradicting the fact that 4-Ore digraphs have dichromatic number 4 by Lemma 11. Hence φ induces a 3-dicolouring of D 1 \[u, v]. So, by the induction hypothesis, vertices in V (J) have distinct colours in φ, except u and v.

Figure 2 :

 2 Figure 2: A 4-dicritical digraph D together with an induced subdigraph R of D and φ a 3dicolouring of R, the φ-identification D φ (R) of R in D and the dicritical extension R ′ of R with extender W and core X W . For clarity, the digons are represented by undirected edges.

  3ε, and, by Lemma 13, T (W ) -T (W -X W ) ⩽ |X w | = 3. Thus, by Claim 2, ρ(D) ⩽ ρ(W ) + ρ(R) -4 -3ε + 3δ. Now, since W is smaller than D, ρ(W ) ⩽ 4 3 + 4ε -2δ by Claim 1. Thus

  D, coloured with φ, must contain a monochromatic directed cycle. Such a directed cycle must be contained in D⟨A⟩ or D⟨B⟩, a contradiction. ♢ Claim 7. D is 3-connected. In particular, D contains no diamond.

  v}, then R is Ore-collapsible and we are done. Suppose now that there exists w ∈ ∂(R) distinct from u and v. Let H = D⟨R⟩ ∪ [u, v]. Observe that H ̸ = ← → K 4 as u, v and w receive the same colour in any 3-dicolouring of D⟨R⟩ because R is collapsible. Hence H is the Ore-composition of two 4-Ore digraphs H 1 (the digon side with replaced digon [x, y]) and H 2 (the split side with split vertex z).

  we obtain a 3-dicolouring of D, a contradiction. Hence φ(N -(x)) = {1, 2, 3}. We set φ(x) = φ(d). As D is not 3-dicolourable, D contains a monochromatic directed cycle C. This cycle C must contain the arc dx, and an out-neighbour z of x. Since φ(a), φ(b) and φ(d) are all distinct, necessarily z = c. But then C -x ∪ dc is a monochromatic directed cycle in D ′ , a contradiction. Similarly, if n(v) = 5, let N + (x) = {a, b, c} and N -(x) = {a, d, e}, and consider

  Proof of claim. Suppose that D⟨{x, y, z}⟩ = ← → K 3 and d(x) = d(y) = 6. By Claim 11, x and y have exactly three neighbours, and N [x] ̸ = N [y] because D contains no copy of ← → K 4 minus two arcs by Claim 10. Let u (resp. v) be the unique neighbour of x distinct from y and z (resp. x and z). Consider D ′ = D -{x, y} ∪ [u, v]. By Claim 9, D ′ has a 3-dicolouring φ. Without loss of generality, suppose that φ(u) = 1 and φ(v) = 2. If φ(z) = 1 (resp. φ(z) = 2, φ(z) = 3), we set φ(x) = 2 and φ(y) = 3 (resp. φ(x) = 3 and φ(y) = 1, φ(x) = 2 and φ(y) = 1). In each case, this yields a 3-dicolouring of D, a contradiction. ♢ So now we know that D contains no emerald, and no diamond by Claim 7. Claim 13. If R is an induced subdigraph of D with 4 ⩽ n(R) < n(D), then ρ(R) ⩾ ρ(D) + 3 + 3ε -3δ, except if D -R contains a single vertex which has degree 6 in D.

If W is not 4 -

 4 Ore, then by Claim 2 ρ(D) ⩽ ρ(R ′ ) ⩽ ρ(W ) + ρ(R) -(10 + 3ε -6) + 3δ and, as ρ(W ) ⩽ 1, we have ρ(R) ⩾ ρ(D) + 3 + 3ε -3δ. Now suppose W is 4-Ore. If W ̸ = ← → K 4 , then, by Lemma 20, W contains a diamond or an emerald disjoint from X, and this gives a diamond or an emerald in D because the degrees of vertices in D -R are the same in D and in W , which is a contradiction. Now suppose that W = ← → K 4 . Then D -R has a single vertex of degree 6 in D.• Assume finally that |X W | = 1. Since R is not collapsible by Claim 9, φ may have been chosen so that ∂(R) is not monochromatic in φ. Then, by Claim 4, ρ(R) ⩾ ρ(D) + 3 -3ε + δ ⩾ ρ(D) + 3 + 3ε -3δ, because 6ε -4δ ⩽ 0.

  If n(x) = 5, let N -(x) = {a, b, c} and N + (x) = {a, b, d, e}. By Claim 10,D ′ = D -x ∪ {cd, ce} has a 3-dicolouring φ. If |φ(N -(x))| < 3, then choosing φ(x) in {1, 2, 3} \ φ(N -(x)) gives a 3-dicolouring of D, a contradiction. If |φ(N -(x))| = 3, then we set φ(x) = φ(c).Suppose for a contradiction that there is a monochromatic directed cycle C in D (with φ). Necessarily C contains x (since φ is a 3-dicolouring of D -x) and so it must contain c and one vertex y in {d, e} because φ(a), φ(b), and φ(c) are all distinct. Then C -x ∪ cy is a monochromatic directed cycle in D ′ , a contradiction. Therefore φ is a 3-dicolouring of D, a contradiction. If n(x) = 6, let N -(x) = {a, b, c} and N + (x) = {a, d, e, f }. Consider D ′ = D -x ∪ {bd, be, bf }.

gives a 3 -

 3 dicolouring of D, a contradiction. Hence |φ(N -(x))| = 3. We set φ(x) = φ(b). Since D is not 3-dicolourable, there exists a monochromatic directed cycle C in D (with φ). Necessarily C contains x (since φ is a 3-dicolouring of D -x) and so it must contain b and one vertex y in {d, e, f } because φ(a), φ(b), and φ(c) are all distinct. Then C -x∪by is a monochromatic directed cycle in D ′ , a contradiction. This gives a 3-dicolouring of D, a contradiction. Henceforth D ′ is not 3-dicolourable, and so it contains a 4-dicritical digraph D, smaller than D. If D does not contain the three arcs bd, be, bf , then it can be obtained from a proper induced subdigraph of D by adding at most two arcs, and so it is 3-dicolourable by Claim 10, a contradiction. Hence {b, d, e, f } ⊆ V ( D). Now consider U = D⟨V ( D) ∪ {x}⟩. • Assume first that a ̸ ∈ V (U ) or c ̸ ∈ V (U ). Then we have • n(U ) = n( D) + 1, • m(U ) ⩾ m( D) + 1 and • T (U ) ⩾ T ( D -b) ⩾ T ( D) -1 by Lemma 13. Hence ρ(U ) ⩽ ρ( Hence by Claim 13, D -U has a single vertex of degree 6 (in D), which must be either a or c. Then we have • n(D) = n( D) + 2, • m(D) ⩾ m( D) -3 + 11 and • T (D) ⩾ T ( D -b) ⩾ T ( D) -1.

Claim 15 .

 15 If [x, y] is a digon and both x and y have degree 6, then either (i) the two neighbours of y distinct from x have degree at least 8, or (ii) the two neighbours of x distinct from y have degree at least 8 and ν N (x) ⩾ 4. Proof of claim. Let [x, y] be a digon in D with d(x) = d(y) = 6. By Claim 11 n(x) = n(y) = 3.

Figure 3 :Figure 4 :

 34 Figure 3: The possible connected components of D 6 .

4 3

 4 Proof of claim. By directional duality, it suffices to prove that D has no out-chelou arcs.Let xy be an out-chelou arc with z ∈ N -(y) \ (N + (y) ∪ {x}).Consider D ′ = D -{x, y} ∪ {zz ′ | z ′ ∈ N + (y) \ N -(y)}. We claim that D ′ is not 3-dicolourable. To see that, suppose for contradiction that there is a 3-dicolouring φ of D ′ . As d + (x) = 3, we can choose φ(x) in {1, 2, 3} \ φ(N + (x) \ {y}) to obtain a 3-dicolouring of D -y. If |φ(N -(y))| < 3, then choosing φ(y) in {1, 2, 3} \ φ(N -(y)) gives a 3-dicolouring of D, a contradiction. Hence |φ(N -(y)| = 3. Set φ(x) = φ(z).Suppose there is a monochromatic directed cycle C in D. It must contain y and thus z, its unique in-neighbour with its colour. Let z ′ be the out-neighbour of y in C. It must be inN + (y) \ N -(y), so zz ′ is an arc in D ′ . Thus C -y ∪ zz ′ is a monochromatic directed cycle in D ′ , a contradiction. Therefore φ is a 3-dicolouring of D, a contradiction. Hence D ′ is not 3-dicolourable.Consequently, D ′ contains a 3-dicritical digraph D, which is smaller than D and contains z, for otherwise D would be a subdigraph of D. Consider U = D⟨V ( D) ∪ {y}⟩. We have• n(U ) = n( D) + 1, • m(U ) ⩾ m( D) + 1 and • T (U ) ⩾ T ( D -z) ⩾ T ( D) -1 by Lemma 13.First if D is not 4-Ore, then by minimality of D we have ρ( D) ⩽ 1, soρ(U ) ⩽ ρ( D) + 10 3 + ε -1 + δ ⩽ 10 3 + ε + δ ⩽ 11 3 -ε -δ 2ε + 2δ ⩽ 1 3 . Next if D is 4-Ore, but not isomorphic to ← → K 4 ,then ρ( D) ⩽ 4 3 + 7ε -4δ by Lemma 22, and ρ(U ) ⩽ ρ( δ because 9ε -2δ ⩽ 0. Finally if D is isomorphic to ← → K 4 , then we have T (U ) ⩾ T ( D -z) ⩾ T ( D) and ρ( D) = + 4ε -2δ. So the same computation yields ρ(U ) ⩽ ρ( δ because 6ε -δ ⩽ 0. In all cases, we have ρ(U ) ⩽ 11 3 -ε -δ. This contradicts Claim 5 because U is not collapsible by Claim 9. ♢ We now use the discharging method. For every vertex v, let σ(v) = δ |C| if v has degree 6 and is in a component C of D 6 of size at least 2, and σ(v) = 0 otherwise. Clearly T (D) is at least the number of connected components of size at least 2 of D 6 so v∈V (D) σ(v) ⩽ δT (D). We define the initial charge of v to be w(v) = 10 3 + ε -d(v) 2 -σ(v). We have ρ(D) ⩽ v∈V (D) w(v).

Figure 5 :

 5 Figure 5: A 3-dicritical oriented graph with 5 2 n arcs.

Figure 6 :

 6 Figure 6: A 4-dicritical oriented graph with at most 9 2 n arcs.

Research supported by research grant DIGRAPHS ANR-19-CE48-0013 and by the French government, through the EUR DS4H Investments in the Future project managed by the National Research Agency (ANR) with the reference number ANR-17-EURE-0004.

1

Hence R -v ∪ [u, w] contains a 4-dicritical digraph K. By Lemma 23, R ′ = D⟨V (K)⟩, as a subdigraph of H which is a 4-Ore, satisfies 10 3 n(R ′ ) -m(R ′ ) ⩾ 10 3 . This implies that 10 3 n(K)m(K) ⩾ 4 3 . Note also that K is bidirected because R -v is bidirected. Thus, by Theorem 21, K is 4-Ore. Hence R ′ with u, w satisfies (ii). ♢ Claim 9. If R is a subdigraph of D with n(R) < n(D) and u, v ∈ V (R), then R ∪ [u, v] is 3-dicolourable. As a consequence, there is no collapsible subdigraph in D.

Proof of claim. Assume for a contradiction that the statement is false. Consider a smallest induced subdigraph R for which the statement does not hold. Then K = R ∪ [u, v] is 4-vertex-dicritical, that is for every vertex v ∈ V (K), ⃗ χ(K -v) < 4 = ⃗ χ(K). Note that 4-vertex-dicritical digraphs smaller than D satisfy the outcome of Theorem 8 since adding arcs does not increase the potential. Note that ρ(R) ⩽ ρ(K) + 2 + δ.

If R is not collapsible, then, by Claim 5, ρ(R) ⩾ ρ(D)

Hence, free to consider u ′ , v ′ instead of u, v, we can suppose that u and v are on the boundary of R. If K is 4-Ore, then, by Claim 8 and by minimality of R, we have that R is Ore-collapsible, and so has boundary of size 2. This contradicts the fact that D is 3-connected. Hence K is not 4-Ore.

By Claim 2, we have

and as ρ(K) ⩽ 1 (because it is not 4-Ore and by minimality of D) we get

3 , W must be 4-Ore. Moreover, W must be isomorphic to ← → K 4 , for otherwise ρ(W ) would be at most 4 3 + 7ε -4δ, and

. Thus, by Claim 2 and because δ ⩾ 3ε, we have

(R1) A vertex of degree 6 incident to no digon sends 1 12 -ε 8 to each of its neighbours.

(R2) A vertex of degree 6 incident to digons sends

2 -ε) via each arc of the digon).

(R3) A vertex of degree 7 with d -(v) = 3 (resp. d + (v) = 3) sends 1 12 -ε 8 to each of its inneighbours (resp. out-neighbours).

For every vertex v, let w * (v) be the final charge of v.

Claim 18. If v has degree at least 8, then w * (v) ⩽ 0.

Proof of claim. Let v be a vertex of degree at least 8. If v is not adjacent to a vertex of degree at most 7, then w

Thus v receives at most

Proof of claim. By Claim 14, v has seven neighbours. Without loss of generality, let us suppose that d -(v) = 3 and d + (v) = 4. By Claim 17, the in-neighbours of v can not have out-degree 3.

In particular, they do not have degree 6, and if they have degree 7, they do not send anything to v by Rule (R3). Hence v receives at most four times the charge 1 12 -ε 8 by (R1) or (R3), and it sends three times this charge by (R3). Hence

Proof of claim. The vertex v sends 1 12 -ε 8 to each of its neighbours, and it receives no charge as all its in-neighbours (resp. out-neighbours) have out-degree (resp. in-degree) at least 4, by Claim 17. As a consequence,

and the result comes because ε ⩽ 2 21 . ♢ Claim 21. Let v be a vertex in D 6 having at least two neighbours of degree at least 8. Then w * (v) ⩽ 0. Moreover, if v is not an isolated vertex in D 6 and ν N (v) ⩾ 4, then w * (v) ⩽ -1 9 + 5 3 ε-δ 4 . Proof of claim. Observe that v receives no charge and sends the following charge to each of its neighbour u with degree at least 8:

Assume first that v is isolated in D 6 . By Claim 14, its three neighbours do not have degree 7, and so have degree at least 8. Thus v sends three times at least 1 6 -ε 4 , and so

Moreover it sends two times at least 1 6 -ε 4 . Hence

and the result comes because δ ⩾ 6ε. This shows the first part of the statement.

We will now prove the second part of the statement. Assume that v is not an isolated vertex in D 6 and ν N (v) ⩾ 4. Let u 1 and u 2 be the two neighbours of v with degree at least 8. For every i ∈ {1, 2} we have

Case 1: ν(u i ) ⩾ 7 for some i ∈ {1, 2}. Without loss of generality suppose i = 1. Then we have

Then the total charge sent by v is at least 1, and thus

26 Thus, we have w * (v) ⩽ -1 9 + 5 3 ε -δ 4 because ε, δ ⩾ 0. Case 2: ν(u 1 ), ν(u 2 ) ⩽ 6. Let f : [0, 6] → R be the function defined by

Observe that f is non decreasing and convex on [0, 6] because -10 3 -ε+ 8 2 ⩾ 0. For i = 1, 2, we have

Hence the charge sent by v to u i is at least f (ν(u i )). By hypothesis we have ν N (v) = ν(u ) + ν(u 2 ) ⩾ 4. It follows that the total charge sent by v is at least

Hence

showing the second part of the statement.

Proof of claim. If C has a unique vertex v, then, by Claim 21, we have w * (v) ⩽ 0 as wanted.

If C has two vertices x and y, then, again by Claim 21, w * (x), w * (y) ⩽ 0, and so w * (x) + w * (y) ⩽ 0.

If C is a bidirected path [x, y, z], then, by Claim 16, x and z have both neighbourhood valency at least 4 and so by Claim 21 w * (x), w * (z) ⩽ -1 9 -ε 6 . Moreover, y sends at least 2 8 (-

Altogether, we get that

Finally, if C is a bidirected star with centre x and three other vertices y, z, w, then w * (x) ⩽ w(x) = 1 3 + ε -δ 4 . Moreover, each of y, z, w has neighbourhood valency at least 4 by Claim 16 and so has final charge at most -1 9 + 5 3 ε -δ 4 by Claim 21. Hence

As a consequence of these last claims, we have ρ(D) ⩽ v∈V (D) w(v) = v∈V (D) w * (v) ⩽ 0 ⩽ 1, a contradiction. This proves Theorem 8.

An upper bound on o k (n)

In this section, we show that, for every fixed k, there are infinitely many values of n such that

2 )n. The proof is strongly based on the proof of [2, Theorem 4.4], which shows o k (n) ⩽ (2k -3)n for every k, n (with n large enough). For k = 4, the construction implies in particular that there is a 4-dicritical oriented graph with 76 vertices and 330 arcs, and there are infinitely many 4-dicritical oriented graphs with m/n ⩽ 9/2. Proposition 26. Let k ⩾ 3 be an integer. For infinitely many values of n ∈ N, there exists a k-dicritical oriented graph ⃗ G k on n vertices with at most (2k -7 2 )n arcs. Proof. Let us fix n 0 ∈ N. We will show, by induction on k, that there exists a k-dicritical oriented graph ⃗ G k on n vertices with at most (2k -7 2 )n arcs, such that n ⩾ n 0 . When k = 3, the result is known ([2, Corollary 4.3]). We briefly describe the construction for completeness. Start from any orientation of an odd cycle on 2n 0 + 1 vertices. Then for each arc xy in this orientation, add a directed triangle ⃗ C 3 and every arc from y to V ( ⃗ C 3 ) and every arc from V ( ⃗ C 3 ) to x (see Figure 5). This gadget forces x and y to have different colours in every 2-dicolouring. Since we started from an orientation of an odd cycle, the result is a 3-dicritical oriented graph on 4(2n 0 + 1) vertices and 10(2n 0 + 1) arcs.

Let us fix k ⩾ 4 and assume that there exists such a

2 )n k-1 arcs. We start from any tournament T on k vertices. Then we add, for each arc xy of T , a copy ⃗

) such that α(z) = α(x). But then (x, y, z, x) is a monochromatic directed triangle in α: a contradiction.

Let us now prove that ⃗ χ( ⃗ G k \ {uv}) ⩽ k -1 for every arc uv ∈ A( ⃗ G k ). This implies immediately that ⃗ χ( ⃗ G k = k and shows the result. Consider first an arc uv in A(T ). We colour each copy ⃗

We then choose a distinct colour for every vertex in T , except u and v which receive the same colour. This results in a (k -1)-dicolouring of ⃗ G k \ {uv}. Consider now an arc uv of ⃗ G xy k-1 for some xy ∈ A(T ). Because ⃗ G k-1 is (k -1)-dicritical, there exists a (k -2)-dicolouring ξ of ⃗ G xy k-1 \ {uv}. Hence we colour ⃗ G xy k-1 \ {uv} with ξ, every other copy of ⃗ G k-1 a (k -1)-dicolouring of ⃗ G k-1 , and we choose a distinct colour for every vertex in T , except x and y which both receive colour k -1. This results in a (k -1)-dicolouring of ⃗ G k \ {uv}. Consider finally an arc uv arc from u ∈ V (T ) to v ∈ V ( ⃗ G uy k-1 ) (the case of u ∈ V ( ⃗ G xv k-1 ) and v ∈ V (T ) being symmetric). Because ⃗ G k-1 is dicritical, there exists a (k -1)-dicolouring γ of ⃗ G uy k-1 in which v is the only vertex coloured k -1. Hence, we colour ⃗ G uy k-1 with γ, every other copy of ⃗ G k-1 with a (k -1)-dicolouring of ⃗ G k-1 , and we choose a distinct colour for every vertex in T , except u and y which both receive colour k -1. This results in a (k -1)-dicolouring of ⃗ G k \ {uv}.