Packing K_rs in bounded degree graphs

DOI10.1016/J.DAM.2024.03.010MaRDI QIDQ6497939FDOQ6497939

Authors: Michael McKay, David F. Manlove 

Publication date: 6 May 2024

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

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

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)

Cites Work

• Title not available (Why is that?)
• On perfect packings in dense graphs
• On the Complexity of General Graph Factor Problems
• A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
• Paths, Trees, and Flowers
• Title not available (Why is that?)
• Maximum bounded 3-dimensional matching is MAX SNP-complete
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Matching theory
• On the completeness of a generalized matching problem
• Title not available (Why is that?)
• On maximal independent sets of vertices in claw-free graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Packings by cliques and by finite families of graphs
• A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
• Combinatorial and computational aspects of graph packing and graph decomposition
• Packing triangles in bounded degree graphs.
• Title not available (Why is that?)
• 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
• Matching and multidimensional matching in chordal and strongly chordal graphs
• Packing triangles in low degree graphs and indifference graphs
• Partition into triangles on bounded degree graphs
• 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)