Article ID Journal Published Year Pages File Type
419851 Discrete Applied Mathematics 2011 9 Pages PDF
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
, , , ,