论文标题
在三角形列表分配中
On triangle-free list assignments
论文作者
论文摘要
我们表明，伯恩斯泰恩（Bernshteyn）证明了Molloy的突破性结果，即可以从尺寸$ $ $ $（1+O（1））Δ/\logδ$的列表中选择无三角形的图表，可以改编以产生更强的结果。特别是，只要在其列表中共享常见颜色的顶点不会引起$ g $中的三角形，这可能证明这种列表尺寸足以为任何最高度$δ$的图形上色$δ$，这涵盖了Molloy定理所涵盖的所有案例。到目前为止，这对于大小$ $（1000+O（1））Δ/\logδ$的列表所知，这是正确的，这意味着由于Amini和Reed而引起的更一般的结果。我们还证明，如果一个人用$ r \ geq 4 $替换了任何$ k_r $，则长度$ 2（r-2）δ\log_2Δ/\log_2Δ/\log_2Δ$就足够了，也将略微稍微推送出Bernshteyn的结果$ 200R $的$ r \ geq 4 $。在对应着色的更通用的环境中，呈现的所有界限也有效。
We show that Bernshteyn's proof of the breakthrough result of Molloy that triangle-free graphs are choosable from lists of size $(1+o(1))Δ/\logΔ$ can be adapted to yield a stronger result. In particular one may prove that such list sizes are sufficient to colour any graph of maximum degree $Δ$ provided that vertices sharing a common colour in their lists do not induce a triangle in $G$, which encompasses all cases covered by Molloy's theorem. This was thus far known to be true for lists of size $(1000+o(1))Δ/\logΔ$, as implies a more general result due to Amini and Reed. We also prove that lists of length $2(r-2)Δ\log_2\log_2Δ/\log_2Δ$ are sufficient if one replaces the triangle by any $K_r$ with $r\geq 4$, pushing also slightly the multiplicative factor of $200r$ from Bernshteyn's result down to $2(r-2)$. All bounds presented are also valid within the more general setting of correspondence colourings.
