On the forbidden induced subgraph sandwich problem

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.