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

Abstract

The dichromatic number $\vec{\chi }(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. A digraph $D$ is $k$-dicritical if $\vec{\chi }(D)=k$ and each proper subdigraph $H$ of $D$ satisfies $\vec{\chi }(H)<k$. For integers $k$ and $n$, we define $d_k(n)$ (respectively $o_k(n)$) as the minimum number of arcs possible in a $k$-dicritical digraph (respectively oriented graph). Kostochka and Stiebitz have shown that $d_4(n)\ge \frac{10}{3}n-\frac{4}{3}$. They also conjectured that there is a constant $c$ such that $o_k(n)\ge c{d}_k(n)$ for $k\ge 3$ and $n$ large enough. This conjecture is known to be true for $k=3$ (Aboulker et al.). In this work, we prove that every $4$-dicritical oriented graph on $n$ vertices has at least $(\frac{10}{3}+\frac{1}{51})n-1$ arcs, showing the conjecture for $k=4$. We also characterise exactly the $k$-dicritical digraphs on $n$ vertices with exactly $\frac{10}{3}n-\frac{4}{3}$ arcs.

31 pages, 6 figures