2K2-partition of some classes of graphs

AbstractWe consider the problem of partitioning the vertex-set of a graph into four non-empty sets A,B,C,D such that every vertex of A is adjacent to every vertex of B and every vertex of C is adjacent to every vertex of D. 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: K4-free graphs, diamond-free graphs, planar graphs, graphs with bounded treewidth, claw-free graphs, (C5,P5)-free graphs and graphs with few P4’s