Packing K_rs in bounded degree graphs

DOI10.1016/J.DAM.2024.03.010MaRDI QIDQ6497939zbMATH OpenFDO

Authors Michael McKay, David F. Manlove

Publication date 6 May 2024

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

zbMATH Keywords

claw-free graphstriangle packingclique packingvertex-disjoint trianglesedge-disjoint triangles\(K_r\)-packing

Mathematics Subject Classification ID

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

Recommendations

• Approximation algorithms and hardness results for the clique packing problem
• Packing triangles in bounded degree graphs.
• Approximation algorithms and hardness results for the clique packing problem
• The \(K_r\)-packing problem
• scientific article; zbMATH DE number 89406

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 910871 (Why is no real title available?)
• scientific article; zbMATH DE number 6783420 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Approximation algorithms and hardness results for the clique packing problem
• Automata, languages and programming. 26th international colloquium, ICALP `99. Prague, Czech Republic, July 11--15, 1999. Proceedings
• Combinatorial and computational aspects of graph packing and graph decomposition
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Matching theory
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• On maximal independent sets of vertices in claw-free graphs
• On perfect packings in dense graphs
• On the Complexity of General Graph Factor Problems
• On the Computational Complexity of Combinatorial Problems
• On the Size of Systems of Sets Every t of which Have an SDR, with an Application to the Worst-Case Ratio of Heuristics for Packing Problems
• On the completeness of a generalized matching problem
• Packing triangles in bounded degree graphs.
• Packing triangles in low degree graphs and indifference graphs
• Packings by cliques and by finite families of graphs
• Partition into triangles on bounded degree graphs
• Paths, Trees, and Flowers
• The \(K_r\)-packing problem

This page was built for publication: Packing \(K_r\)s in bounded degree graphs

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