On perfect packings in dense graphs

József Balogh, Alexandr V. Kostochkay, Andrew Treglown

Research output: Contribution to journalArticlepeer-review

Abstract

We say that a graph G has a perfect H-packing if there exists a set of vertex- disjoint copies of H which cover all the vertices in G. We consider various problems concerning perfect H-packings: Given n; r;D ∈ ℕ, we characterise the edge density threshold that ensures a perfect Kr-packing in any graph G on n vertices and with minimum degree δ(G) ≥ D. We also give two conjectures concerning degree sequence conditions which force a graph to contain a perfect H-packing. Other related embedding problems are also considered. Indeed, we give a structural result concerning Kr-free graphs that satisfy a certain degree sequence condition.

Original languageEnglish (US)
JournalElectronic Journal of Combinatorics
Volume20
Issue number1
DOIs
StatePublished - Mar 8 2013

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'On perfect packings in dense graphs'. Together they form a unique fingerprint.

Cite this