Gear Composition of Stable Set Polytopes and š¯’¢-Perfection
Anna Galluccio, Claudio Gentile, Paolo Ventura Ā· Mathematics of Operations Research Ā· 2009
Graphs obtained by applying the gear composition to a given graph H are called geared graphs. We show how a linear description of the stable set polytope STAB(G) of a geared graph G can be obtained by extending the linear inequalities defining STAB(H) and STAB(He), where He is the graph obtained from H by subdividing the edge e. We also introduce the class of š¯’¢-perfect graphs, i.e., graphs whose stable set polytope is described by nonnegativity inequalities, rank inequalities, lifted 5-wheel inequalities, and some special inequalities called geared inequalities and g-lifted inequalities. We prove that graphs obtained by repeated applications of the gear composition to a given graph H are š¯’¢-perfect, provided that any graph obtained from H by subdividing a subset of its simplicial edges is š¯’¢-perfect. In particular, we show that a large subclass of claw-free graphs is š¯’¢-perfect.