Polynomial cases of graph decomposition: A complete solution of Holyer's problem

DOI10.1016/j.disc.2008.01.054zbMath1214.05112OpenAlexW1979065875MaRDI QIDQ1024436

Krzysztof Bryś, Zbigniew Lonc

Publication date: 17 June 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2008.01.054

zbMATH Keywords

computational complexityedge decompositions of graphsholyer problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (6)

Edge decompositions and rooted packings of graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles ⋮ Decomposing Semi-complete Multigraphs and Directed Graphs into Paths of Length Two ⋮ On the complexity of deciding whether the regular number is at most two ⋮ Induced Decompositions of Graphs ⋮ On Rooted Packings, Decompositions, and Factors of Graphs

Cites Work

• A note on the decomposition of graphs into isomorphic matchings
• General factors of graphs
• NP-completeness of graph decomposition problems
• Edge-disjoint packings of graphs
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• On the Complexity of General Graph Factor Problems
• 3K2-decomposition of a graph
• The NP-Completeness of Some Edge-Partition Problems
• A Characterization in of Upper-Embeddable Graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Polynomial cases of graph decomposition: A complete solution of Holyer's problem