期刊
COMBINATORICS PROBABILITY & COMPUTING
卷 10, 期 1, 页码 41-77出版社
CAMBRIDGE UNIV PRESS
DOI: 10.1017/S0963548300004612
关键词
-
We show that there exist universal constants C(r) < such that, for all loopless graphs G of maximum degree less than or equal to 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)\ less than or equal to 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-Kotecky-Preiss condition for nonvanishing of a polymer-model partition function. We also show that, for all loopless graphs G of second-largest degree less than or equal to 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-Colbourn conjecture on the zeros of the reliability polynomial for the special case of series-parallel graphs.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据