在图论中，若存在常数 $c$ 使得任意 $n$ 顶点的图 $G\in\mathcal{G}$ 的最小分离集数目不超过 $n^c$，则称图类 $\mathcal{G}$ 为可控（tame）。常见的可控类包括弦图、置换图和圆图等。
可控类的一个重要特性是，许多经典优化问题在这些类上可以在多项式时间内求解。例如，最大加权独立集（Max Weight Independent Set）在所有可控类上均可在 $\text{poly}(n)$ 时间内完成，这为它们在不同图类上的可解性提供了统一解释。
本文的主要贡献是证明列表3着色（List 3-Coloring）在任意可控图类上可以在准多项式时间内求解。具体而言，设 $n$ 为输入图的顶点数，则该算法的时间复杂度为 $2^{O((\log n)^k)}$，其中 $k$ 为仅依赖于常数 $c$ 的固定指数。该结果表明，即使在仅允许每个顶点从至多三个颜色中选择的约束下，列表着色问题在广泛的图类上仍保持相对高效的可解性。
技术要点
- 利用可控类的最小分离集上界，将图划分为若干子图，使得每个子图的结构足够简单以便递归求解。
- 在递归过程中采用动态规划记录每个子图的可行颜色列表，确保全局一致性。
- 通过对分离集的枚举和子图合并的精细分析，控制递归深度在 $O(\log n)$ 量级，从而实现准多项式时间复杂度。
该方法不仅统一了已有的多项式时间算法（如在弦图上的列表着色），还扩展到更一般的可控类，为进一步研究图着色的复杂性提供了新思路。
点评