Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
type: Item
instance of: scholarly article
title: Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
zbMATH Open document ID: 0868.05041
author: Zbigniew Lonc
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-06-03T00:00:00Z
review text: 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.
reviewed by: Zbigniew Lonc
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 1006755
zbMATH Keywords: edge decomposition
zbMATH Keywords: Holyer problem
zbMATH Keywords: computational complexities
zbMATH Keywords: paths
MaRDI profile type: Publication
full work available at URL: jctb.1996.1735
OpenAlex ID: W2058339086
cites work: A note on the decomposition of graphs into isomorphic matchings
cites work: Q4097307
cites work: 3K2-decomposition of a graph
cites work: Q3999150
cites work: Q3915022
cites work: NP-completeness of graph decomposition problems
cites work: Edge-disjoint packings of graphs
cites work: Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
cites work: Q3741644
cites work: On the Complexity of General Graph Factor Problems
cites work: The NP-Completeness of Some Edge-Partition Problems
cites work: Q4201584
DOI: 10.1006/JCTB.1996.1735
description: scientific article; zbMATH DE number 1006755