Résumé | Composition of strips was introduced by Chudnovsky and Seymour as a key tool for decomposing claw-free graphs. In this talk we are going to reveal the close connection between the stable set problem in composed graphs and the matching theory. We will basically show that anything we can do for the strips, we can extend to composition of strips i.e. polytime algorithm (resp. separation, polyhedral description) for the strip extends to polytime algorithm (resp. separation, polyhedral description) for the composed graph.
We will then apply those general results back to where they originated from: stable set in claw-free graphs, to show that the stable set polytope can be reduced to understanding the polytope in very basic structures (for most of which it is already known). In particular for a general claw-free graph $G$, we show an integral extended formulation for $STAB(G)$ and a procedure to separate in polynomial time over $STAB(G)$; moreover, we provide a complete characterization of $STAB(G)$ when $G$ is any claw-free graph with stability number at least 4 having neither homogeneous pairs nor 1-joins. |