Journal
JOURNAL OF COMBINATORIAL THEORY SERIES B
Volume 99, Issue 6, Pages 869-903Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jctb.2009.03.002
Keywords
Graph; Matroid; Chromatic polynomial; Dichromatic polynomial; Flow polynomial; Characteristic polynomial; Tutte polynomial; Potts model; Chromatic root; Flow root; Zero-free interval
Categories
Funding
- U.S. National Science Foundation [PHY-0099393, PHY-0424082]
Ask authors/readers for more resources
The chromatic polynomial P(G)(q) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals (-infinity, 0), (0,1) and (1, 32/27). Analogous theorems hold for the flow polynomial of bridgeless graphs and for the characteristic polynomial of loopless matroids. Here we exhibit all these results as special cases of more general theorems on real zero-free regions of the multivariate Tutte polynomial Z(G)(q, v). The proofs are quite simple, and employ deletion-contraction together with parallel and series reduction. In particular, they shed light on the origin of the curious number 32/27. (C) 2009 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available