On the minimum number of arcs in k-dicritical oriented graphs

Description

The dichromatic number ⃗ χ(D) of a digraph D is the least integer k such that D can be partitioned into k directed acyclic digraphs. A digraph is k-dicritical if ⃗ χ(D) = k and each proper subgraph D ′ of D satisfies ⃗ χ(D) ≤ k − 1. An oriented graph is a digraph with no directed cycle of length 2. For integers k and n, we denote by o k (n) the minimum number of edges of a k-dicritical oriented graph on n vertices (with the convention o k (n) = +∞ if there is no k-dicritical oriented graph of order n). The main result of this paper is a proof that o 3 (n) ≥ 7n+2 3 together with a construction witnessing that o 3 (n) ≤ 5n 2 for all n ≥ 12. We also give a construction showing that for all sufficiently large n and all k ≥ 3, o k (n) < (2k − 3)n, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all k ≥ 2, o k (n) ≥ k − 3 4 − 1 4k−6 n + 3 4(2k−3) , improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.

Additional details