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

Description

The dichromatic number of a digraph 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 is ‐dicritical if and each proper subdigraph of satisfies . For integers and , we define (resp., ) as the minimum number of arcs possible in a ‐dicritical digraph (resp., oriented graph). Kostochka and Stiebitz have shown that . They also conjectured that there is a constant such that for and large enough. This conjecture is known to be true for . In this work, we prove that every 4‐dicritical oriented graph on vertices has at least arcs, showing the conjecture for . We also characterise exactly the 4‐dicritical digraphs on vertices with exactly arcs.

Abstract

International audience

Additional details