Vertex partition of a complete multipartite graph into two kinds of induced subgraphs

AbstractLet k, ℓ be positive integers. Let G be a graph of order kℓ. It is shown that if G is a complete multipartite graph, G has a vertex partition V(G)=V1∪V2∪⋯∪Vℓ such that for some pair of graphs H1 and H2 of order k, the subgraph of G induced by Vi is isomorphic to H1 or H2 for any i with 1≤i≤ℓ. Furthermore, for graphs not necessarily complete multipartite, similar problems are discussed