On the complexity of some edge-partition problems for graphs (Q1923590)

Let \(F\) be a family of graphs. An \(F\)-decomposition of a graph \(G\) is a partition of the edge set of \(G\) into subgraphs isomorphic to members of \(F\). The paper concentrates on some complexity problems concerning \(F\)-decompositions. It is shown that if \(F\) contains neither the 1-edge nor the 2-edge star, it is NP-complete to decide whether a bipartite graph admits an \(F\)-decomposition, thereby strengthening a result of P. Hell and D. G. Kirkpatrick on partitioning the node set of a graph into complete graphs of certain orders. If \(F\) contains a 2-edge star, it yields a good characterization of graphs, not necessarily bipartite, that admit \(F\)-decompositions. This characterization gives a linear time algorithm for constructing such a decomposition, if one exists.