We 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.
展开▼
