Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial

DOI10.1006/jctb.1996.1735zbMath0868.05041OpenAlexW2058339086MaRDI QIDQ1354723

Zbigniew Lonc

Publication date: 3 June 1997

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.1996.1735

zbMATH Keywords

pathsedge decompositioncomputational complexitiesHolyer problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (7)

Edge decompositions and rooted packings of graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ Combinatorial and computational aspects of graph packing and graph decomposition ⋮ On Rooted Packings, Decompositions, and Factors of Graphs ⋮ Multigraph decomposition into stars and into multistars ⋮ Polynomial cases of graph decomposition: A complete solution of Holyer's problem ⋮ Edge decompositions into two kinds of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the decomposition of graphs into isomorphic matchings
• NP-completeness of graph decomposition problems
• Edge-disjoint packings of graphs
• On the Complexity of General Graph Factor Problems
• 3K2-decomposition of a graph
• The NP-Completeness of Some Edge-Partition Problems
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture

This page was built for publication: Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial