论文标题
在$ k $ dicricitighitiencition的图中，最小弧数
On the minimum number of arcs in $k$-dicritical oriented graphs
论文作者
论文摘要
Digraph $ d $的DICHOROMATING NUMBER $ \ dic（d）$是整数$ k $的最小值，因此可以将$ d $划分为$ k $指导的循环digraphs。如果$ \ dic（d）= k $，并且每个适当的子图$ d'US $ d $ of $ d $满足$ \ dic（d'）\ leq k-1 $，则DIGRAPH为$ K $ -DICICALICATION。面向图形是一个无定向周期$ 2 $的图形。对于整数$ k $和$ n $，我们用$ o_k（n）$表示$ n $ vertices上的$ k $至关重要的图形的最小边数（如果没有$ k $ $ k $ - $ k $ - $ dicritical-dicritience of-n $ n $ n $ n $ vertices的订单$ o_k（n）=+\ iffty $）。本文的主要结果是证明了$ o_3（n）\ geq \ frac {7n+2} {3} $，以及一个结构，见证了$ o_3（n）\ leq \ left \ left \ lef \ lceil \ frac {5n} {5n} {2} {2} {2} \ right \ rceil $ for $ n \ geq geq for $ n \ geq 12 $。我们还提供了一个施工，表明所有足够大的$ n $以及所有$ k \ geq 3 $，$ o_k（n）<（2k-3）n $，反驳了Hoshino和Kawarabayashi的猜想。最后，我们证明，对于所有$ k \ geq 2 $，$ o_k（n）\ geq \ pth {k- \ frac {3} {4} {4} - \ frac {1} {1} {4K-6}}}} n + \ frac {3} {3} {4（2k-3）$，以前的bank and and tourder，以前的bank bank and tourder and tourdion tourder and tourdion and tourdion tourder and tourdie tourdie tourdie tourdie and tourdion and。和Stiebitz。
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') \leq k-1$. An oriented graph is a digraph with no directed cycle of length $2$. For integers $k$ and $n$, we denote by $o_k(n)$ the minimum number of edges of a $k$-critical oriented graph on $n$ vertices (with the convention $o_k(n)=+\infty$ if there is no $k$-dicritical oriented graph of order $n$). The main result of this paper is a proof that $o_3(n) \geq \frac{7n+2}{3}$ together with a construction witnessing that $o_3(n) \leq \left \lceil \frac{5n}{2} \right \rceil$ for all $n \geq 12$. We also give a construction showing that for all sufficiently large $n$ and all $k\geq 3$, $o_k(n) < (2k-3)n$, disproving a conjecture of Hoshino and Kawarabayashi. Finally, we prove that, for all $k\geq 2$, $o_k(n) \geq \pth{ k - \frac{3}{4}-\frac{1}{4k-6}} n + \frac{3}{4(2k-3)}$, improving the previous best known lower bound of Bang-Jensen, Bellitto, Schweser and Stiebitz.
