On the minimum number of arcs in -dicritical oriented graphs
The dichromatic number $\dic(D)$ of a digraph is the least integer such that can be partitioned into directed acyclic digraphs. A digraph is -dicritical if $\dic(D) = k$ and each proper subgraph of satisfies $\dic(D') \leq k-1$. An oriented graph is a digraph with no directed cycle of length . For integers and , we denote by the minimum number of edges of a -critical oriented graph on vertices (with the convention if there is no -dicritical oriented graph of order ). The main result of this paper is a proof that together with a construction witnessing that for all . We also give a construction showing that for all sufficiently large and all , , disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all , $o_k(n) \geq \pth{ k - \frac{3}{4}-\frac{1}{4k-6}} n + \frac{3}{4(2k-3)}$, improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.