论文标题
改善局部稀疏超图的着色边界
Improved bounds for coloring locally sparse hypergraphs
论文作者
论文摘要
我们表明，对于每$ k \ ge 2 $，每个$ k $均匀的高度$δ$和girth至少$ 5 $有效地是$（1+o（1））（k-1）（k-1）（Δ/ \lnΔ）作为一个应用程序（在我们所知的最佳知识中），我们获得了当前最佳的算法，用于列表颜色的随机超图，并具有界平均程度的随机超图。
We show that, for every $k \ge 2$, every $k$-uniform hypergaph of degree $Δ$ and girth at least $5$ is efficiently $(1+o(1) )(k-1) (Δ/ \ln Δ)^{ 1/(k-1) } $-list colorable. As an application (and to the best of our knowledge) we obtain the currently best algorithm for list-coloring random hypergraphs of bounded average degree.
