Stable skew partition problem Original Research Article

A skew partition is a partition of the vertex set of a graph into four nonempty parts A,B,C,D such that there are all possible edges between A and B, and no edges between C and D. A stable skew partition is a skew partition where A induces a stable set of the graph. We show that determining if a graph permits a stable skew partition is NP-complete. We discuss limits of such reductions by adding cardinality constraints.