Claw-free independence polynomials
The independence polynomial of a finite claw-free graph is real-rooted, also with nonnegative vertex weights.
Results
A graph is claw-free if no vertex has three pairwise non-adjacent neighbors. The independence polynomial of a finite graph $G$ is $\sum_A x^{|A|}$, summed over the independent sets $A$ of $G$.
Theorem (Chudnovsky--Seymour). If $G$ is a finite claw-free graph, then its independence polynomial is real-rooted [CS07].
Theorem (weighted form). Let $G$ be a finite claw-free graph and let $w(v)\ge0$ for every vertex $v$. Then $$ \sum_A x^{|A|}\prod_{v\in A}w(v) $$ is real-rooted. This form is due to Engström; see the Heilmann--Lieb page.
References
[CS07]. Background on claw-free graphs is on symmetricfunctions.com.
- [CS07] The roots of the independence polynomial of a clawfree graph. Journal of Combinatorial Theory, Series B, 97(3), 350-357, 2007.
BibTeX
@article{ChudnovskySeymour2007, doi = {10.1016/j.jctb.2006.06.001}, url2 = {https://doi.org/10.1016/j.jctb.2006.06.001}, year = {2007}, month = may, publisher = {Elsevier {BV}}, volume = {97}, number = {3}, pages = {350--357}, author = {Maria Chudnovsky and Paul Seymour}, title = {The roots of the independence polynomial of a clawfree graph}, journal = {Journal of Combinatorial Theory, Series B} }