Minimum number of arcs in $k$-critical digraphs with order at most $2k-1$

Abstract

The dichromatic number $\vec{\chi }(D)$ of a digraph $D$ is the least integer $k$ for which $D$ has a coloring with $k$ colors such that there is no monochromatic directed cycle in $D$. The digraphs considered here are finite and may have antiparallel arcs, but no parallel arcs. A digraph $D$ is called $k$-critical if each proper subdigraph $D^{\prime }$ of $D$ satisfies $\vec{\chi }(D^{\prime })<\vec{\chi }(D)=k$. For integers $k$ and $n$, let $\overrightarrow{\mathrm{ext}}(k,n)$ denote the minimum number of arcs possible in a $k$-critical digraph of order $n$. It is easy to show that $\overrightarrow{\mathrm{ext}}(2,n)=n$ for all $n\ge 2$, and $\overrightarrow{\mathrm{ext}}(3,n)\ge 2n$ for all possible $n$, where equality holds if and only if $n$ is odd and $n\ge 3$. As a main result we prove that if $n,k$ and $p$ are integers with $n=k+p$ and $2\le p\le k-1$, then $\overrightarrow{\mathrm{ext}}(k,n)=2((\genfrac{}{}{0ex}{}{n}{2})-(p^2+1))$, and we give an exact characterisation of $k$-critical digraphs for which equality holds. This generalizes a result about critical graphs obtained in 1963 by Tibor Gallai.