论文标题
用于涂色的算法框架本地稀疏图
An algorithmic framework for colouring locally sparse graphs
论文作者
论文摘要
我们开发了用于图形着色的算法框架，以减少问题以验证独立集的局部概率属性。 这样我们就给出了任何固定的$ k \ ge 3 $和$ \ varepsilon> 0 $，是一种随机的多项式时间算法，用于着色图$δ$的着色图，其中每个顶点都包含在最多$ t $ k $的$ t $ k $的$ 1/2 \ le t \ le t \ le t \ le t \ le t \ le t \ le t \ le t \ le t \ le t $中δ^\ frac {2 \ varepsilon} {1+2 \ varepsilon}/（\logδ）^2 $，带有$ \ lfloor（1+ \ varepsilon）Δ/\ log（Δ/\ sqrt t）\ rfloor $ $。 这一概括和改善了几个值得注意的结果，包括Kim（1995）和Alon，Krivelevich和Sudakov（1999），以及Molloy（2019）和Achlioptas，Iliopoulos和Sinclair（2019）的最新结果。在色数上的这种结合到渐近因子$ 2 $，它与著名的算法屏障相吻合。
We develop an algorithmic framework for graph colouring that reduces the problem to verifying a local probabilistic property of the independent sets. With this we give, for any fixed $k\ge 3$ and $\varepsilon>0$, a randomised polynomial-time algorithm for colouring graphs of maximum degree $Δ$ in which each vertex is contained in at most $t$ copies of a cycle of length $k$, where $1/2\le t\le Δ^\frac{2\varepsilon}{1+2\varepsilon}/(\logΔ)^2$, with $\lfloor(1+\varepsilon)Δ/\log(Δ/\sqrt t)\rfloor$ colours. This generalises and improves upon several notable results including those of Kim (1995) and Alon, Krivelevich and Sudakov (1999), and more recent ones of Molloy (2019) and Achlioptas, Iliopoulos and Sinclair (2019). This bound on the chromatic number is tight up to an asymptotic factor $2$ and it coincides with a famous algorithmic barrier to colouring random graphs.
