Delta-system decompositions of graphs (Q1356709)

A graph \(G\) has a decomposition into graphs \(G_1,\dots,G_t\), if \(G\) is an edge-disjoint union of graphs each of which is isomorphic to some graph \(G_i\). Let \(c\) be a fixed positive integer. The main result of the paper states that the problem to decide whether a graph \(G\) has an edge decompositions into graphs \(K_{1,c}\) and \(cK_2\) (the only two \(\Delta\)-systems of size \(c\) in the case of graphs) is in the class P.