论文标题
关于大周长的着色挖掘的注释
A Note on Coloring Digraphs of Large Girth
论文作者
论文摘要
挖掘的挖掘是最短的定向周期的长度。 Digraph $ d $的二分法$ \vecχ（d）$是顶点集合中的最小尺寸，诱导无偶石子图的子集。 Harutyunyan和Mohar的一个猜想指出，每个Digraph $ d $ d $ d $ d $ d $ d $ d $ d $ d $ d $ 3 $ $ 3 $，$ \ lew \ left \ lest \ lew \ lew \ lew \ lew \fracδ{4} \ right \ rceil+1 $。 Golowich最著名的部分结果表明，$ \vecχ（d）\ le \ frac {2} {5} {5}δ+o（1）$。在简短的说明中，我们证明，如果$ g \ ge 2 $，则如果$ d $是挖掘的挖掘，至少$ 2G-1 $和最高度$δ$，则$ \vecχ（d）\ le（\ frac {1} {1} {1} {3} {3} {3}+ \ frac {1} {1} {3G} {3G} {3G} {3G} {3G} {1）Δ+ O_G（1）$。这改善了Golowich的挖掘界限，而无需指向长度的定向周期最多$ 10 $。
The digirth of a digraph is the length of a shortest directed cycle. The dichromatic number $\vecχ(D)$ of a digraph $D$ is the smallest size of a partition of the vertex-set into subsets inducing acyclic subgraphs. A conjecture by Harutyunyan and Mohar states that $\vecχ(D) \le \left\lceil\fracΔ{4}\right\rceil+1$ for every digraph $D$ of digirth at least $3$ and maximum degree $Δ$. The best known partial result by Golowich shows that $\vecχ(D) \le \frac{2}{5}Δ+O(1)$. In this short note we prove for every $g \ge 2$ that if $D$ is a digraph of digirth at least $2g-1$ and maximum degree $Δ$, then $\vecχ(D) \le (\frac{1}{3}+\frac{1}{3g}) Δ+ O_g(1)$. This improves the bound of Golowich for digraphs without directed cycles of length at most $10$.
