Acyclic sink polynomials of chordal claw-free graphs

A claw-free graph with a reverse perfect elimination order has a real-rooted acyclic sink polynomial.

Results

For a finite graph $G$, the acyclic sink polynomial is $$ S_G(t)=\sum_{O}t^{\operatorname{sink}(O)}, $$ summed over the acyclic orientations $O$ of $G$, where $\operatorname{sink}(O)$ is the number of vertices with no outgoing edge. A reverse perfect elimination order is a linear order of the vertices in which the earlier neighbors of every vertex form a clique. A graph has such an order exactly when it is chordal.

Theorem. If a finite claw-free graph $G$ has a reverse perfect elimination order, then $S_G(t)$ is real-rooted.

The ascent-refined polynomial $S_G(t;q)$ of acyclic sinks of natural unit interval graphs depends on a vertex labelling, and $S_G(t;1)=S_G(t)$.

Use

Line graphs of forests are chordal and claw-free. For them $S_{L(F)}$ is the minima polynomial of the forest $F$.

Proof

Insert the vertices along the order. Since the earlier neighbors of each vertex form a clique, $S_G(t+1)$ is a positive multiple of a weighted independence polynomial of $G$ with nonnegative weights. This is real-rooted for claw-free $G$ by the weighted form of the Chudnovsky--Seymour theorem.

References

P. Alexandersson and L. Saud Maia Leite, unpublished manuscript (2026). Background on claw-free graphs is on the Chudnovsky--Seymour and Leake--Ryder pages.

Definitions

  • Acyclic sink polynomial

    RealRooted.Graph.ordinaryAcyclicSinkPolynomialsource
    def ordinaryAcyclicSinkPolynomial [Fintype V]
        (G : _root_.SimpleGraph V) : ℝ[X] := by
      classical
      exact ∑ O : Orientation.AcyclicOrientation G, X ^ O.1.sinkCount
  • Reverse perfect elimination order

    RealRooted.Graph.ReversePerfectEliminationOrdersource
    structure ReversePerfectEliminationOrder (G : _root_.SimpleGraph V) where
      /-- The linear order on the vertices. -/
      order : LinearOrder V
      earlier_isClique : ∀ v,
        G.IsClique {u | order.lt u v ∧ G.Adj u v}

Theorems

  • Chordal claw-free graphs have real-rooted acyclic sink polynomialsMain resultCoauthored paper

    RealRooted.Graph.ReversePerfectEliminationOrder.ordinaryAcyclicSinkPolynomial_splits_of_clawFreesource
    theorem ordinaryAcyclicSinkPolynomial_splits_of_clawFree
        (P : ReversePerfectEliminationOrder G) (hG : ClawFree G) :
        (ordinaryAcyclicSinkPolynomial G).Splits
  • At q = 1 the ascent-refined sink polynomial is the ordinary oneCoauthored paper

    RealRooted.Graph.acyclicSinkPolynomial_one_eq_ordinarysource
    theorem acyclicSinkPolynomial_one_eq_ordinary
        [Fintype V] [LinearOrder V] (G : _root_.SimpleGraph V) :
        acyclicSinkPolynomial G 1 = ordinaryAcyclicSinkPolynomial G

Lean source RealRooted/Challenges/Graphs/ChordalClawFreeAcyclicSinks.lean at revision d6670742. Formalized 2026-09-13.