A Deterministic Algorithm for Counting Colorings with 2Δ Colors

Abstract

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 case when the graph is also triangle-free, we show that our algorithm applies under the weaker 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. The core of our argument is the establishment of a region in the complex plane in which the Potts model partition function (a classical graph polynomial) has no zeros. This result, which substantially sharpens previous work on the same problem, is of independent interest. Our algorithms follow immediately from zero-freeness via the “polynomial interpolation" method of Barvinok. Interestingly, our method for identifying the zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.