The chromatic polynomial P G ( q ) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals ( − ∞ , 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.
%0 Journal Article
%1 jackson09
%A Jackson, Bill
%A Sokal, Alan D.
%D 2009
%J Journal of Combinatorial Theory, Series B
%K algebraic.graph.theory chromatic graph.theory polynomial potts root root-free spin.model tutte
%N 6
%P 869 -- 903
%R 10.1016/j.jctb.2009.03.002
%T Zero-Free Regions for Multivariate Tutte Polynomials (alias Potts-Model Partition Functions) of Graphs and Matroids.
%V 99
%X The chromatic polynomial P G ( q ) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals ( − ∞ , 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.
@article{jackson09,
abstract = {The chromatic polynomial P G ( q ) of a loopless graph G is known to be non-zero (with explicitly known sign) on the intervals ( − ∞ , 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. },
added-at = {2013-12-27T20:44:22.000+0100},
author = {Jackson, Bill and Sokal, Alan D.},
biburl = {https://www.bibsonomy.org/bibtex/2b989029b4370e4958651f82572854c57/ytyoun},
doi = {10.1016/j.jctb.2009.03.002},
interhash = {9aa555d9a2ffd538cdb396e911741abe},
intrahash = {b989029b4370e4958651f82572854c57},
issn = {0095-8956},
journal = {Journal of Combinatorial Theory, Series B },
keywords = {algebraic.graph.theory chromatic graph.theory polynomial potts root root-free spin.model tutte},
number = 6,
pages = {869 -- 903},
timestamp = {2016-02-25T13:31:39.000+0100},
title = {Zero-Free Regions for Multivariate {Tutte} Polynomials (alias {Potts}-Model Partition Functions) of Graphs and Matroids.},
volume = 99,
year = 2009
}