Edge decompositions into two kinds of graphs

DOI10.1016/j.disc.2008.10.024zbMath1210.05111OpenAlexW2029914950MaRDI QIDQ1045169

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

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Algorithmic problems in right-angled Artin groups: complexity and applications ⋮ Colorful edge decomposition of graphs: some polynomial cases ⋮ Edge decompositions and rooted packings of graphs ⋮ Decomposing subcubic graphs into claws, paths or triangles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on the decomposition of graphs into isomorphic matchings
• Packings by cliques and by finite families of graphs
• Packing subgraphs in a graph
• NP-completeness of graph decomposition problems
• Efficient subgraphs packing
• Edge decomposition into isomorphic copies of \(sK_{1,2}\) is polynomial
• Delta-system decompositions of graphs
• On the complexity of some edge-partition problems for graphs
• On the Complexity of General Graph Factor Problems
• Packings by Complete Bipartite Graphs
• 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