Edge decompositions into two kinds of graphs

Redirect to:

• Edge decompositions into two kinds of graphs

DOI10.1016/J.DISC.2008.10.024MaRDI QIDQ1045169zbMATH OpenOpenAlexFDO

Authors Zbigniew Lonc, Monika Pszczoła

Publication date 15 December 2009

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

computational complexityedge decompositions of graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) 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
• On the complexity of some edge-partition problems for graphs
• Edge decompositions and rooted packings of graphs
• NP-completeness of graph decomposition problems
• scientific article; zbMATH DE number 398969

Cites work

• scientific article; zbMATH DE number 3974987 (Why is no real title available?)
• scientific article; zbMATH DE number 398969 (Why is no real title available?)
• scientific article; zbMATH DE number 1033810 (Why is no real title available?)
• 3K2-decomposition of a graph
• A note on the decomposition of graphs into isomorphic matchings
• Delta-system decompositions of graphs
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• Efficient subgraphs packing
• Graph Decomposition is NP-Complete: A Complete Proof of Holyer's Conjecture
• NP-completeness of graph decomposition problems
• On the Complexity of General Graph Factor Problems
• On the complexity of some edge-partition problems for graphs
• Packing subgraphs in a graph
• Packings by Complete Bipartite Graphs
• Packings by cliques and by finite families of graphs
• The NP-Completeness of Some Edge-Partition Problems

Cited in

(13)

• Edge decompositions and rooted packings of graphs
• Decomposing cubic graphs into connected subgraphs of size three
• Repeated edges in 2-factorizations
• Algorithmic problems in right-angled Artin groups: complexity and applications
• Multigraph decomposition into stars and into multistars
• Decomposing subcubic graphs into claws, paths or triangles
• Decompositions into two linear forests of bounded lengths
• Graph decomposition of slim graphs
• scientific article; zbMATH DE number 2190098 (Why is no real title available?)
• Decomposition of class II graphs into two class I graphs
• Graphs having the local decomposition property
• Colorful edge decomposition of graphs: some polynomial cases
• Decompositions of multigraphs into parts with two edges

This page was built for publication: Edge decompositions into two kinds of graphs

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