An FPTAS for Counting Proper Four-Colorings on Cubic Graphs

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\ge \mathrm{\Delta }+1$, where $q$ is the number of colors and $\mathrm{\Delta }$ is the maximum degree of the graph. The bound of $q=\mathrm{\Delta }+1$ is the uniqueness threshold for Gibbs measure on $\mathrm{\Delta }$-regular infinite trees. However, the conjecture remained open even for any fixed $\mathrm{\Delta }\ge 3$ (The cases of $\mathrm{\Delta }=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 $\mathrm{\Delta }=3$. This is the first time to achieve this optimal bound of $q = \Delta

• 1$\mathrm{.}Previously,thebestFPRASrequires$q > \frac{11}{6} \Delta$ and the best deterministic FPTAS requires $q>2.581\mathrm{\Delta }+1$ for general graphs. In the case of $\mathrm{\Delta }=3$, the best previous result is an FPRAS for counting proper 5-colorings. We note that there is a barrier to go beyond $q = \Delta + 2$ for single-site Glauber dynamics based FPRAS and we overcome this by correlation decay approach. Moreover, we develop a number of new techniques for the correlation decay approach which can find applications in other approximate counting problems.