Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
Let \(H\) be a fixed graph. We say that a graph \(G\) admits an \(H\)-decomposition if the set of edges of \(G\) can be partitioned into subsets generating graphs isomorphic to \(H\). Denote by \({\mathcal P}_H\) the problem of existence of an \(H\)-decomposition of a graph. The Holyer problem is to classify the problems \({\mathcal P}_H\) according to their computational complexities. In this paper we show that the problem \({\mathcal P}_H\) is polynomial when \(H\) is the union of \(s\) disjoint 2-edge paths.
scientific article; zbMATH DE number 1006755
scientific article