An FPTAS for Counting Proper Four-Colorings on Cubic Graphs
Lu, Yang, Zhang, Zhu · cs.DS,math.CO · 2016-11-13 · 原文
Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting. It is conjectured that there is a fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as q \geq Δ+ 1, where q is the number of colors and Δ is the maximum degree of the graph. The bound of q = Δ+ 1 is the uniqueness threshold for Gibbs measure on Δ-regular infinite trees. However, the conjecture remained open even for any fixed Δ\geq 3 (The cases of Δ=1, 2 are trivial). In this paper, we design an FPTAS for counting the number of proper 4-colorings on graphs with maximum degree 3 and thus confirm the conjecture in the case of Δ=3. This is the first time to achieve this optimal bound of q = Δ+ 1. Previously, the best FPRAS requires q > \frac{11}{6} Δ and the best deterministic FPTAS requires q > 2.581Δ+ 1 for general graphs. In the case of Δ=3, the best previous result is an FPRAS for counting proper 5-colorings. We note that there is a barrier to go beyond q = Δ+ 2 for single-site Glauber dynamics based FPRAS and we overcome this by correlation decay approach. Moreover, we develop a
讲义
讲义·推断 依据「原文」自动生成的结构化摘要（推断），非原文表述；以原文为准。
1. 人话版
Graph coloring is arguably the most exhaustively studied problem in the area of approximate counting.
It is conjectured that there is a fully polynomial-time (randomized) approximation scheme (FPTAS/FPRAS) for counting the number of proper colorings as long as q \geq Δ+ 1, where q is the number of colors and Δ is the maximum degree of the graph.
2. 领域脉络
本文类目：cs.DS、math.CO，属于其所在研究脉络的最新进展。
3. 机制拆解
摘要未展开方法细节——精读时重点看方法/模型部分。
4. 证据与数字
The bound of q = Δ+ 1 is the uniqueness threshold for Gibbs measure on Δ-regular infinite trees.
However, the conjecture remained open even for any fixed Δ\geq 3 (The cases of Δ=1, 2 are trivial).
In this paper, we design an FPTAS for counting the number of proper 4-colorings on graphs with maximum degree 3 and thus confirm the conjecture in the case of Δ=3.
5. 反例与边界
摘要未声明局限与反例——这是需要警惕的信号，精读时先问边界。
6. 跨领域连接与意外收获
横跨 2 个类目（cs.DS、math.CO），关注其在你兴趣板块间的迁移面。
7. 可复用方法
把本文机制与你手头项目对照，找一个两周内能验证的最小实验。
8. 术语表
精读时把不熟的术语记入此处，作为下次回忆的锚点。