Forbidden subgraph decomposition (Q1598796)

Let \(F=(X,Y)\) be a bipartite graph with bipartite sets \(X\) and \(Y\). Given a graph \(G=(V,E)\) and a partitition \(P = V_1 \cup V_2\) of its vertices, let \(G_P = (V,E*)\) be the graph with edges consisting of all those edges in \(G\) with one vertex in \(V_1\) and the other in \(V_2\). We say \(F\) is tidily induced in \(G_P\) if there exists an isomorphism \(f\) from \(F\) to an induced subgraph \(H\) of \(G_P\) so that \(f(x) \in V_1\) for all \(x \in X\) and \(f(y) \in V_2\) for all \(y \in Y\). We say \(P\) is an \(F\)-free decomposition of \(G\) if \(|V_1|\geq |X|\), \(|V_2|\geq |Y|\) and \(F\) is not tidily induced in \(G_P\). The authors study the complexity of recognising \(F\)-free decompositions for small \(F\), in particular bipartite graphs with at most 4 vertices. The main result is that deciding whether a graph has a \(2K_2\)-free decomposition is NP-complete.