Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650209 | Discrete Mathematics | 2009 | 12 Pages |
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
Raffaele Mosca,