On the complexity of some edge-partition problems for graphs

AbstractFor 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 G. 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