2023/10/05 by Lucas Picasarri‐Arrieta, Picasarri-Arrieta, Lucas, Michael Stiebitz +1 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.03584
openalex publication_date 2023/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The dichromatic number χ(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' of D satisfies χ(D')<χ(D)=k. For integers k and n, let \overrightarrowext(k,n) denote the minimum number of arcs possible in a k-critical digraph of order n. It is easy to show that \overrightarrowext(2,n)=n for all n≥ 2, and \overrightarrowext(3,n)≥ 2n for all possible n, where equality holds if and only if n is odd and n≥ 3. As a main result we prove that if n, k and p are integers with n=k+p and 2≤ p ≤ k-1, then \overrightarrowext(k,n)=2(\binomn2 - (p2+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.