Discrete Mathematics and Optimization Seminar

---

PAUL SEYMOUR
Princeton
Monday January 10th at 4.30pm
Burnside 1205



Title. The roots of the stable set polynomial of a claw-free graph.

Abstract. The stable set polynomial of a graph G is the polynomial \Sum_i>=0 a_ixⁱ where a_i is the number of stable sets
of size i in G. Heilmann and Lieb (1972) proved that for any graph, all roots of its ``matching polynomial'' are real. The
matching polynomial of G is the stable set polynomial of the line graph of G, so stable set polynomials of line graphs
always have all roots real. How far can this be generalized? Not to the stable set polynomial of every graph;
the stable set polynomial of a ``claw'' (the complete bipartite graph K_1,3) does not have all roots real.
But many theorems about line graphs extend to ``clawfree'' graphs, the graphs in which no induced
subgraph is a claw, and Hamidoune (1990) and Stanley (1998) asked whether for every clawfree graph,
its stable set polynomial has all roots real. We give a proof. It does not depend on our structure theorem for
clawfree graphs, that Maria will present in a separate lecture.
(Joint work with Maria Chudnovsky - her lecture will be in the Algorithms Seminar on Wednesday.)