Discrete Mathematics and Optimization Seminar
Sept. 3, 2008
MC 320, 4:30 PM
On the stable set polytope of claw-free 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 claw-free graphs, we build a significant subclass of claw-free graphs for which these new inequalities yield a defining linear system for their stable set polytopes.