|Discrete Mathematics and Optimization Seminar
Monday January 10th at 4.30pm
Title. The roots of the stable set polynomial of a claw-free graph.
The stable set polynomial of a graph G is the polynomial
\Sumi>=0 aixi where ai 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
K1,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