On the complexity of some edge-partition problems for graphs

For a family g of stars, a g-decomposition of a graph H is a partition of the edge set of H into subgraphs isomorphic to members of V. We show that, if g contains neither the 1-edge nor the 2-edge star, it is NP-complete to decide whether a bipartite graph admits a g-decomposition. This result enables us to strengthen a result of Hell and Kirkpatrick on partitioning the vertex set of a graph into complete graphs of certain orders. If g contains a 2-edge star, we obtain a good characterization of graphs (not necessarily bipartite) that admit g-decompositions. This characterization yields a linear time algorithm for constructing such a decomposition, if it exists.