Skew partition sandwich problem is NP-complete

Sandwich problems generalize graph recognition problems with respect to a property Π. A recognition problem has a graph as input, whereas a sandwich problem has two graphs as input. In a sandwich problem, we look for a third graph, required to satisfy a property Π, whose edge set lies between the edge sets of two given graphs. A skew partition of a graph G = ( V , E ) is a partition of its vertex set V into four nonempty parts A, B, C, D such that each vertex of part A is adjacent to each vertex of part B, and each vertex of part C is nonadjacent to each vertex of part D. Skew cutset generalizes star cutset which in turn generalizes both homogeneous set and clique cutset. Homogeneous set, clique cutset, star cutset, and skew cutset are decompositions arising in perfect graph theory and the recognition of each decomposition is known to be polynomial. Regarding sandwich problems, it is known that homogeneous set sandwich problem is polynomial, clique cutset sandwich problem is NP-complete, and star cutset sandwich problem is polynomial. We prove that skew partition sandwich problem is NP-complete, establishing an interesting computational complexity non-monotonicity.