Polyhedral results on the stable set problem in graphs containing even or odd pairs

• 成果类型: Article
• 署名作者: Witt, Jonas T.; Luebbecke, Marco E.; Reed, Bruce
• 署名单位: RWTH Aachen University; Centre National de la Recherche Scientifique (CNRS); Universite Cote d'Azur; Instituto Nacional de Matematica Pura e Aplicada (IMPA)
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-017-1168-x
• 发表日期: 2018
• 页码: 519-522
• 关键词: imperfect graphs; conjecture

摘要

Even and odd pairs are important tools in the study of perfect graphs and were instrumental in the proof of the Strong Perfect Graph Theorem. We suggest that such pairs impose a lot of structure also in arbitrary, not just perfect graphs. To this end, we show that the presence of even or odd pairs in graphs imply a special structure of the stable set polytope. In fact, we give a polyhedral characterization of even and odd pairs.