
Discrete Mathematics and Optimization Seminar

Sept. 3, 2008
MC 320, 4:30 PM
On the stable set polytope of clawfree graphs
Anna Galluccio
CNR, Rome

We build new classes of facet defining inequalities for the stable set polytope
using a new graph composition named gear composition.
Using the decomposition theorem of Chudnovsky and Seymour for clawfree graphs,
we build a significant subclass of clawfree graphs for which these new inequalities
yield a defining linear system for their stable set polytopes.



