Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419851 | Discrete Applied Mathematics | 2011 | 9 Pages |
Abstract
We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) [15], with respect to classes of graphs defined by excluding induced subgraphs. We prove that the sandwich problem corresponding to excluding a chordless cycle of fixed length kk is NP-complete. We prove that the sandwich problem corresponding to excluding Kr∖eKr∖e for fixed rr is polynomial. We prove that the sandwich problem corresponding to 3PC(⋅,⋅)3PC(⋅,⋅)-free graphs is NP-complete. These complexity results are related to the classification of a long-standing open problem: the sandwich problem corresponding to perfect graphs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Simone Dantas, Celina M.H. de Figueiredo, Murilo V.G. da Silva, Rafael B. Teixeira,