Chromatic polynomials, Potts models and all that

The q-state Potts model can be defined on an arbitrary finite graph, and it s partition function encodes much important information about that graph, i ncluding its chromatic polynomial, flow polynomial and reliability polynomi al. The complex zeros of the Pens partition function are of interest both t o statistical mechanicians and to combinatorists. I give a pedagogical intr oduction to all these problems, and then sketch two recent results: (a) Con struction of a countable family of planar graphs whose chromatic zeros are dense in the whole complex q-plane except possibly for the disc \q - 1\ < 1 . (b) Proof of a universal upper bound on the q-plane zeros of the chromati c polynomial (or antiferromagnetic Potts-model partition function) in terms of the graph's maximum degree. (C) 2000 Elsevier Science B.V. All rights r eserved.