a b s t r a c t 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 k is NP-complete. We prove that the sandwich problem corresponding to excluding Kr \ e for fixed r is polynomial. We prove that the sandwich problem corresponding to 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.
['Simone Dantas', 'Celina M. Herrera de Figueiredo', 'Murilo Vicente Gonçalves da Silva', 'Rafael B. Teixeira']
On the forbidden induced subgraph sandwich problem