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

DOI10.1016/J.DISC.2008.01.054MaRDI QIDQ1024436zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• NP-completeness of graph decomposition problems
• Edge decompositions and rooted packings of graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• On the complexity of some edge-partition problems for graphs

Cites work

• scientific article; zbMATH DE number 3974987 (Why is no real title available?)
• scientific article; zbMATH DE number 3720936 (Why is no real title available?)
• scientific article; zbMATH DE number 3537708 (Why is no real title available?)
• scientific article; zbMATH DE number 398969 (Why is no real title available?)
• 3K2-decomposition of a graph
• A Characterization in of Upper-Embeddable Graphs
• A note on the decomposition of graphs into isomorphic matchings
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• Edge-disjoint packings of graphs
• General factors of graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• Graph theory
• NP-completeness of graph decomposition problems
• On the Complexity of General Graph Factor Problems
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(12)

• On rooted packings, decompositions, and factors of graphs
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• On some multigraph decomposition problems and their computational complexity
• Graph decomposition of slim graphs
• Decomposing subcubic graphs into claws, paths or triangles
• Edge decompositions and rooted packings of graphs
• Solving a special case of the P conjecture using dependency graphs with dissolution
• On the complexity of deciding whether the regular number is at most two
• Towards a solution of the Holyer's problem
• Graphs having the local decomposition property
• Induced decompositions of graphs
• Decomposing semi-complete multigraphs and directed graphs into paths of length two

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1024436)