We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting the number of q-colorings of a graph of maximum degree ?, provided only that q ≥ 2?. This substantially improves on previous deterministic algorithms for this problem, the best of which requires q ≥ 2.58?, and matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the special case when the graph is also triangle-free, we show that our algorithm applies under the condition q ≥ α? + β, where α ≈ 1.764 and β = β(α) are absolute constants.

Our result applies more generally to list colorings, and to the partition function of the anti-ferromagnetic Potts model. Our algorithm exploits the so-called “polynomial interpolation” method of Barvinok, identifying a suitable region of the complex plane in which the Potts model partition function has no zeros. Interestingly, our method for identifying this zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.