Article ID Journal Published Year Pages File Type
4650209 Discrete Mathematics 2009 12 Pages PDF
Abstract

For some graph classes defined by forbidding one-vertex extensions of the P4P4, we introduce an implicit description of the stable set polytope; furthermore, for some of those classes, we give explicitly a minimal defining linear system. This is of interest since the class of P4P4-free graphs is basic in modular decomposition theory, and at the same time a well-known result of Chvátal [V. Chvátal, On certain polytopes associated with graphs, Journal of Combinatorial Theory Series (B) 18 (1975) 138–154] provides a strict link between modular decomposition of graphs and their stable set polytope.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,