Edge decompositions into two kinds of graphs

AbstractLet H be an arbitrary graph and let K1,2 be the 2-edge star. By a {K1,2,H}-decomposition of a graph G we mean a partition of the edge set of G into subsets inducing subgraphs isomorphic to K1,2 or H. Let J be an arbitrary connected graph of odd size. We show that the problem to decide if an instance graph G has a {K1,2,H}-decomposition is NP-complete if H has a component of an odd size and H≠pK1,2∪qJ, where pK1,2∪qJ is the disjoint union of p copies of K1,2 and q copies of J. Moreover, we prove polynomiality of this problem for H=qJ