Deterministic approximate counting of colorings with fewer than 2 colors via absence of zeros

Let, q 3 be integers. We prove that there exists 0. 002 such that if q (2-), then there exists an open set U C that contains the interval 0, 1 such that for each w U and any graph G= (V, E) of maximum degree at most, the partition function of the anti-ferromagnetic q-state Potts model evaluated at w does not vanish. This provides a (modest) improvement on a result of Liu, Sinclair, and Srivastava, and breaks the q=2-barrier for this problem. As a direct consequence we obtain via Barvinok's interpolation method a deterministic polynomial time algorithm to approximate the number of proper q-colorings of graphs of maximum degree at most, provided q (2-).