The Minimum Number of Edges in 4-Critical Digraphs of Given Order

The dichromatic number χ(D) of a digraph D, introduced by Neumann-Lara in the 1980s, is the least integer k for which D has a coloring with k colors such that each vertex receives a color and no directed cycle of D is monochromatic. The digraphs considered here are finite and may have antiparalell arcs, but no parallel arcs. A digraph D is k-critical if each proper subdigraph D^′ of D satisfies χ(D^′) < χ(D) = k. For integers k and n, let d_k(n) denote the minimum number of arcs possible in a k-critical digraph of order n. It is easy to show that d₂(n) = n for all n≥ 2 , and d₃(n) ≥ 2 n for all possible n, where equality holds if and only if n is odd and n≥ 3. As a main result we prove that d₄(n) ≥ ⌈ (10 n- 4) / 3 ⌉ for all n≥ 4 and n≠ 5 where equality holds if n≡1(mod3) or n≡2(mod3). As a consequence, we obtain that for each surface S the number of 4-critical oriented graphs that can be embedded on S is finite.