2K2 vertex-set partition into nonempty parts

A graph is 2K"2-partitionable if its vertex set can be partitioned into four nonempty parts A, B, C, D such that each vertex of A is adjacent to each vertex of B, and each vertex of C is adjacent to each vertex of D. Determining whether an arbitrary graph is 2K"2-partitionable is the only vertex-set partition problem into four nonempty parts according to external constraints whose computational complexity is open. We establish that the 2K"2-partition problem parameterized by minimum degree is fixed-parameter tractable. We also show that for C"4-free graphs, circular-arc graphs, spiders, P"4-sparse graphs, and bipartite graphs the 2K"2-partition problem can be solved in polynomial time.