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.

  1. [CS07] Maria Chudnovsky & Paul Seymour. 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}
    }

Definitions

  • Claw-free graph

    RealRooted.Graph.ClawFreesource
    def ClawFree {V : Type u} (G : _root_.SimpleGraph V) : Prop :=
      ∀ v : V, ∀ s : Finset V, (∀ w ∈ s, G.Adj v w) → ¬ G.IsNIndepSet 3 s
  • Independence polynomial

    RealRooted.Graph.indepPolysource
    def indepPoly {V : Type u} [Fintype V] [DecidableEq V]
        (G : _root_.SimpleGraph V) : ℝ[X] := by
      classical
      exact ∑ s ∈ (Finset.univ.powerset.filter fun s : Finset V =>
          G.IsIndepSet (s : Set V)),
        (X : ℝ[X]) ^ s.card

Theorems

  • Chudnovsky–Seymour: claw-free graphs have real-rooted independence polynomials

    RealRooted.Graph.clawFree_indepPoly_splitssource
    theorem clawFree_indepPoly_splits :
        ∀ {V : Type u} [Fintype V] [DecidableEq V]
          (G : _root_.SimpleGraph V), ClawFree G → (indepPoly G).Splits
  • Weighted independence polynomials of claw-free graphs are real-rootedMain result

    RealRooted.Graph.clawFree_weightedIndepPoly_splitssourcestatement on symmetricfunctions.com
    theorem clawFree_weightedIndepPoly_splits
        {V : Type u} [Fintype V] [DecidableEq V]
        {G : _root_.SimpleGraph V} [DecidableRel G.Adj]
        (hG : ClawFree G) (wt : V → ℝ) (hwt : ∀ v, 0 ≤ wt v) :
        (weightedIndepPoly G wt).Splits

Lean source RealRooted/Challenges/Graphs/ChudnovskySeymour.lean at revision d6670742. Formalized 2026-07-09.