On the forbidden induced subgraph sandwich problem Original Research Article

We consider the sandwich problem, a generalization of the recognition problem introduced by Golumbic et al. (1995) , 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 image is NP-complete. We prove that the sandwich problem corresponding to excluding image for fixed image is polynomial. We prove that the sandwich problem corresponding to image-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.