论文标题
线性树木猜想的改进结合
An Improved Bound for the Linear Arboricity Conjecture
论文作者
论文摘要
1980年，Akiyama，Exoo和Harary提出了线性树木的猜想，该猜想指出，任何最大程度的$ g $ $ g $ $δ$最多都可以分解为最多$ \ weft \ lceil \ lceil \fracΔ{2} \ right \ right \ right \ rceil $ linear $ linearears sorests。 （如果森林的所有组成部分都是路径，则是线性的。）1988年，阿隆证明了猜想渐近地存在。当前的最佳界限是由于2020年的Ferber，Fox和Jain造成的，他们表明$ \fracδ{2}+ O（δ^{。661}）$足够大的$δ$。在这里，我们表明$ g $最多可以将分解成$ \fracδ{2}+ 3 \sqrtδ\ log^4Δ$线性森林$δ$足够大。 此外，我们的结果还存在于更一般的列表设置中，边缘具有（可能不同的）允许线性森林集。因此，我们的界限也适用于列表线性树子型猜想，这直到最近才被金和第二作者渐近地证明。实际上，我们的证明方法将线性支撑性猜想和众所周知的列表构想联系在一起。因此，我们对线性树木的错误术语与2000年的Molloy和Reed有关的列表着色的最著名错误期与此匹配。这是随后的两种颜色的副本，然后寻求适当的边缘着色，避免在颜色和副本之间避免双色周期；我们通过巧妙地修改nibble方法来实现这一目标。
In 1980, Akiyama, Exoo and Harary posited the Linear Arboricity Conjecture which states that any graph $G$ of maximum degree $Δ$ can be decomposed into at most $\left\lceil \fracΔ{2}\right\rceil$ linear forests. (A forest is linear if all of its components are paths.) In 1988, Alon proved the conjecture holds asymptotically. The current best bound is due to Ferber, Fox and Jain from 2020 who showed that $\fracΔ{2}+ O(Δ^{.661})$ suffices for large enough $Δ$. Here, we show that $G$ admits a decomposition into at most $\fracΔ{2}+ 3\sqrtΔ \log^4 Δ$ linear forests provided $Δ$ is large enough. Moreover, our result also holds in the more general list setting, where edges have (possibly different) sets of permissible linear forests. Thus our bound also holds for the List Linear Arboricity Conjecture which was only recently shown to hold asymptotically by Kim and the second author. Indeed, our proof method ties together the Linear Arboricity Conjecture and the well-known List Colouring Conjecture; consequently, our error term for the Linear Arboricity Conjecture matches the best known error-term for the List Colouring Conjecture due to Molloy and Reed from 2000. This follows as we make two copies of every colour and then seek a proper edge colouring where we avoid bicoloured cycles between a colour and its copy; we achieve this via a clever modification of the nibble method.
