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

06/19/2023
by   Frédéric Havet, et al.
0

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. A digraph D is k-dicritical if χ⃗(D) = k and each proper subdigraph H of D satisfies χ⃗(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) ≥10/3n -4/3. They also conjectured that there is a constant c such that o_k(n) ≥ cd_k(n) for k≥ 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 (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/3n -4/3 arcs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset