论文标题
$ k $ - dicricitical Digraph中最小弧数的各种界限
Various bounds on the minimum number of arcs in a $k$-dicritical digraph
论文作者
论文摘要
Digraph $ g $的二分法$ \vecχ（g）$是整数$ k $的最小值，因此可以将$ g $划分为$ k $ k $ acyclic digraphs。如果$ \vecχ（g）= k $，并且每个适当的子图$ h $ of $ g $ of $ g $满足$ \vecχC（h）\ leq k-1 $，则digraph为$ k $ -Dicricital。 ％面向图形是一个无循环$ 2 $的图形。我们证明了在$ k $ - dicritical Digraph中的最小弧数，这是$ k $ - dicricital Digraphs的结构性结果，以及列表dicolouring的结果。 我们表征了$ 3 $ -Dicritical Digraphs $ g $ with $（k-1）| v（g）| + 1 $弧。对于$ k \ geq 4 $，我们表征$ k $ -dicritical Digraphs $ g $至少$ k+1 $ VERTICES和$（K-1）| V（g）| + k-3 $弧，概括了狄拉克的结果。我们证明，对于$ k \ geq 5 $，每个$ k $ -dicricital Digraph $ g $至少都有$（k-1/2-1/（k-1））| v（g）| -k（1/2-1/（k -1））$弧，这是最著名的下限。我们证明，由$ k $ - dicricition Digraph的度数$ 2（k-1）$的顶点引起的连接组件的数量最多是digraph的连接组件的数量，从而概括了Stiebitz的结果。最后，我们将thomassen的定理概括为无方向图的列表 - 奇迹数字，以列表列表数字数字。
The dichromatic number $\vecχ(G)$ of a digraph $G$ is the least integer $k$ such that $G$ can be partitioned into $k$ acyclic digraphs. A digraph is $k$-dicritical if $\vecχ(G) = k$ and each proper subgraph $H$ of $G$ satisfies $\vecχ(H) \leq k-1$. %An oriented graph is a digraph with no cycle of length $2$. We prove various bounds on the minimum number of arcs in a $k$-dicritical digraph, a structural result on $k$-dicritical digraphs and a result on list-dicolouring. We characterise $3$-dicritical digraphs $G$ with $(k-1)|V(G)| + 1$ arcs. For $k \geq 4$, we characterise $k$-dicritical digraphs $G$ on at least $k+1$ vertices and with $(k-1)|V(G)| + k-3$ arcs, generalising a result of Dirac. We prove that, for $k \geq 5$, every $k$-dicritical digraph $G$ has at least $(k-1/2 - 1/(k-1)) |V(G)| - k(1/2 - 1/(k-1))$ arcs, which is the best known lower bound. We prove that the number of connected components induced by the vertices of degree $2(k-1)$ of a $k$-dicritical digraph is at most the number of connected components in the rest of the digraph, generalising a result of Stiebitz. Finally, we generalise a Theorem of Thomassen on list-chromatic number of undirected graphs to list-dichromatic number of digraphs.
