2K2-Partition Problem

A 2K2-partition of a graph is a partition of its vertex set in four (nonempty) parts a, b, c, d such that each vertex of a is adjacent to every vertex of b, and each vertex of c is adjacent to every vertex of d. We show that determining if a graph G admits a 2K2-partition is NP-complete. This result completely classify the H-Partition Problems. Moreover, the 2K2-Partition Problem is the only NP-complete.