Compositions of Graphs and Polyhedra III: Graphs with No $W_4 $ Minor
Francisco Barahona, Ali Ridha Mahjoub · SIAM Journal on Discrete Mathematics · 1994
The authors characterize the stable set polytope for graphs that do not have a 4-wheel as a minor. The authors prove that the nontrivial facets are either “edge” inequalities or can be obtained by composing “odd cycles” and “subdivisions of $K_4 $.” By adding some extra variables, it is shown that the stable set problem for these graphs can be formulated as a linear program of polynomial size.