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