Composition of graphs and polyhedra III : Graphs with No $W_4$ minor

Barahona, Francisco; Mahjoub, Ali Ridha

Barahona, Francisco; Mahjoub, Ali Ridha (1994), Composition of graphs and polyhedra III : Graphs with No $W_4$ minor, SIAM Journal on Discrete Mathematics, 7, 3, p. 372-389. http://dx.doi.org/10.1137/S089548019018268X

Type

Article accepté pour publication ou publié

Date

1994

Journal name

SIAM Journal on Discrete Mathematics

Volume

Number

Publisher

SIAM

Pages

372-389

Abstract (EN)

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.

Subjects / Keywords

compact systems; stable set polytope; composition of polyhedra; Polyhedral combinatorics