2022/07/03 by Aboulker, Pierre, Bellitto, Thomas, Havet, Frédéric +1
#05C20 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2207.01051
The dichromatic number \dic(D) of a digraph D is the least integer k such that D can be partitioned into k directed acyclic digraphs. A digraph is k-dicritical if \dic(D) = k and each proper subgraph D' of D satisfies \dic(D') ≤ k-1. An oriented graph is a digraph with no directed cycle of length 2. For integers k and n, we denote by ok(n) the minimum number of edges of a k-critical oriented graph on n vertices (with the convention ok(n)=+∞ if there is no k-dicritical oriented graph of order n). The main result of this paper is a proof that o3(n) ≥ (7n+2)/(3) together with a construction witnessing that o3(n) ≤ \lceil (5n)/(2) \rceil for all n ≥ 12. We also give a construction showing that for all sufficiently large n and all k≥ 3, ok(n) < (2k-3)n, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all k≥ 2, ok(n) ≥ \pth k - (3)/(4)-(1)/(4k-6) n + (3)/(4(2k-3)), improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.