The minimum number of edges in 4-critical digraphs of given order (Q2175801)

The authors consider the problem of finding critical graphs for coloring of directed graphs, the model defined by \textit{V. Neumann-Lara} [J. Comb. Theory, Ser. B 33, 265--270 (1982; Zbl 0506.05031)]. The dichromatic number \(\chi(D)\) of a directed graph \(D\) is the smallest number \(k\) for which \(D\) has a coloring such that each vertex receives a color and no directed cycle of \(D\) is monochromatic (acyclic coloring). Let \(d_k(n)\) denote the number of the minimum number of arc possible in a \(k\)-critical digraph of order \(n\). The paper gives proof that \(d_4(n) \geq \lceil (10n-4)/3\rceil\) for all \(n\geq 4\) and \(n\not = 5\). The results presented in the paper complete the knowledge in the subject under consideration. Up to know the problem of \(k\)-critical graphs for coloring of directed graphs were known for \(k\leq 3\). Thus, the contribution is significant.