Monday January 10th at 4.30pm

of size

matching polynomial of

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

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.)