2K22K2 vertex-set partition into nonempty parts

A graph is 2K22K2-partitionable if its vertex set can be partitioned into four nonempty parts AA, BB, CC, DD such that each vertex of AA is adjacent to each vertex of BB, and each vertex of CC is adjacent to each vertex of DD. Determining whether an arbitrary graph is 2K22K2-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 2K22K2-partition problem parameterized by minimum degree is fixed-parameter tractable. We also show that for C4C4-free graphs, circular-arc graphs, spiders, P4P4-sparse graphs, and bipartite graphs the 2K22K2-partition problem can be solved in polynomial time.