Title: The Graph Sandwich Problem for a coNP Property
Published: July 2006
Authors: Marcus Schaefer
Abstract: If F ⊂ G  ⊂ F' we say that the graph G is sandwiched between graphs F and F'. The graph sandwich problem consists in finding such a graph G in a particular class or with a special property. We show that there is a coNP-complete graph property for which the graph sandwich problem is complete for the second level of the polynomial time hierarchy.
Full Paper: [postscript, pdf]