Composition of graphs and polyhedra III : Graphs with No $W_4$ minor
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
TypeArticle accepté pour publication ou publié
Journal nameSIAM Journal on Discrete Mathematics
MetadataShow full item record
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 / Keywordscompact systems; stable set polytope; composition of polyhedra; Polyhedral combinatorics
Showing items related by title and author.