### Abstract

We show that there exist universal constants C(r) < ∞ such that, for all loopless graphs G of maximum degree ≤ r, the zeros (real or complex) of the chromatic polynomial P_{G}(q) lie in the disc |q| < C(r). Furthermore, C(r) ≤ 7.963907r. This result is a corollary of a more general result on the zeros of the Potts-model partition function Z_{G}(q, {v_{e}}) in the complex antiferromagnetic regime |1 + v_{e}| ≤ 1. The proof is based on a transformation of the Whitney-Tutte-Fortuin-Kasteleyn representation of Z_{G}(q, {v_{e}}) to a polymer gas, followed by verification of the Dobrushin-Kotecký-Preiss condition for nonvanishing of a polymer-model partition function. We also show that, for all loopless graphs G of second-largest degree ≤ r, the zeros of P_{G}(q) lie in the disc |q| < C(r) + 1. Along the way, I give a simple proof of a generalized (multivariate) Brown-Colboum conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.

Original language | English (US) |
---|---|

Pages (from-to) | 41-77 |

Number of pages | 37 |

Journal | Combinatorics Probability and Computing |

Volume | 10 |

Issue number | 1 |

DOIs | |

State | Published - 2001 |

### ASJC Scopus subject areas

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics