Helly property, clique graphs, complementary graph classes, and sandwich problems

A sandwich problem for property Π asks whether there exists a sandwich graph of a given pair of graphs which has the desired property Π. Graph sandwich problems were first defined in the context of Computational Biology as natural generalizations of recognition problems. We contribute to the study of the complexity of graph sandwich problems by considering the Helly property and complementary graph classes. We obtain a graph class defined by a finite family of minimal forbidden subgraphs for which the sandwich problem is NP-complete. A graph is clique-Helly when its family of cliques satisfi...

Texto completo