Various bounds on the minimum number of arcs in a \(k\)-dicritical digraph (Q6117430)

Summary: The dichromatic number \(\vec{\chi}(G)\) of a digraph \(G\) is the least integer \(k\) such that \(G\) can be partitioned into \(k\) acyclic digraphs. A digraph is \(k\)-dicritical if \(\vec{\chi}(G) = k\) and each proper subgraph \(H\) of \(G\) satisfies \(\vec{\chi}(H) \leqslant k-1\). We prove various bounds on the minimum number of arcs in a \(k\)-dicritical digraph, a structural result on \(k\)-dicritical digraphs and a result on list-dicolouring. We characterise \(3\)-dicritical digraphs \(G\) with \((k-1)|V(G)| + 1\) arcs. For \(k \geqslant 4\), we characterise \(k\)-dicritical digraphs \(G\) on at least \(k+1\) vertices and with \((k-1)|V(G)| + k-3\) arcs, generalising a result of Dirac. We prove that, for \(k \geqslant 5\), every \(k\)-dicritical digraph \(G\) has at least \((k-\frac 1 2 - \frac 1 {k-1}) |V(G)| - k(\frac 1 2 - \frac 1 {k-1})\) arcs, which is the best known lower bound. We prove that the number of connected components induced by the vertices of degree \(2(k-1)\) of a \(k\)-dicritical digraph is at most the number of connected components in the rest of the digraph, generalising a result of \textit{M. Stiebitz} [Combinatorica 2, 315--323 (1982; Zbl 0512.05029)]. Finally, we generalise a theorem of \textit{C. Thomassen} [J. Comb. Theory, Ser. B 70, No. 1, 67--100 (1997; Zbl 0883.05051)] on list-chromatic number of undirected graphs to list-dichromatic number of digraphs.