New graph polynomials from the Bethe approximation of the Ising partition function

Yusuke Watanabe, Kenji Fukumizu

We introduce two graph polynomials and discuss their properties. One is a polynomial of two variables whose investigation is motivated by the performance analysis of the Bethe appr…