2K22K2-partition of some classes of graphs

We consider the problem of partitioning the vertex-set of a graph into four non-empty sets A,B,C,DA,B,C,D such that every vertex of AA is adjacent to every vertex of BB and every vertex of CC is adjacent to every vertex of DD. The complexity of deciding if a graph admits such a partition is unknown. We show that it can be solved in polynomial time for several classes of graphs: K4K4-free graphs, diamond-free graphs, planar graphs, graphs with bounded treewidth, claw-free graphs, (C5,P5)(C5,P5)-free graphs and graphs with few P4P4’s.