Back to Search Start Over

The stable set polytope for some extensions of P4-free graphs

Authors :
Raffaele Mosca
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