The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem

The ΠΠ graph sandwich problem asks, for a pair of graphs G1=(V,E1)G1=(V,E1) and G2=(V,E2)G2=(V,E2) with E1⊆E2E1⊆E2, whether there exists a graph G=(V,E)G=(V,E) that satisfies property ΠΠ and E1⊆E⊆E2E1⊆E⊆E2. We consider the property of being FF-free, where FF is a fixed graph. We show that the claw-free graph sandwich and the bull-free graph sandwich problems are both NP-complete, but the paw-free graph sandwich problem is polynomial. This completes the study of all cases where FF has at most four vertices. A skew partition of a graph GG is a partition of its vertex set into four nonempty parts A,B,C,DA,B,C,D such that each vertex of AA is adjacent to each vertex of BB, and each vertex of CC is nonadjacent to each vertex of DD. We prove that the skew partition sandwich problem is NP-complete, establishing a computational complexity non-monotonicity.