Back to Search
Start Over
The stable set polytope for some extensions of P4-free graphs
- Source :
- Discrete Mathematics. 309:176-187
- Publication Year :
- 2009
- Publisher :
- Elsevier BV, 2009.
-
Abstract
- For some graph classes defined by forbidding one-vertex extensions of the P"4, 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 P"4-free graphs is basic in modular decomposition theory, and at the same time a well-known result of Chvatal [V. Chvatal, 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.
Details
- ISSN :
- 0012365X
- Volume :
- 309
- Database :
- OpenAIRE
- Journal :
- Discrete Mathematics
- Accession number :
- edsair.doi...........d4875f258840af71db2dfa72eaf2a824
- Full Text :
- https://doi.org/10.1016/j.disc.2007.12.068