k-Coloring 比计算色数更快

k-Coloring is Faster than Computing the Chromatic Number

图论领域迎来重大突破，Or Zamir 证明了针对 n 个顶点的图，k-Coloring 问题存在一种随机算法，其运行时间为 (2−ε_k)^n。此前，只有 k≤6 的情况已知拥有比通用 O⋆(2^n) 算法更快的解法，而该通用算法由 Björklund 等人提出用于计算色数。这项研究通过推广并组合 (k+2)-coloring 到 k-list-coloring 的归约工具，以及基于超图容器的方法，成功解决了这一长期悬而未决的难题。新的算法策略混合了长列表和短列表的实例，实现了从 (k+1)-list-coloring 到 k-list-coloring 的可迭代归约，为固定调色板下的列表着色问题提供了全新视角。