On perfect packings in dense graphs

zbMATH Open1266.05115arXiv1110.3490MaRDI QIDQ1953444FDOQ1953444

Andrew Treglown, Alexandr Kostochka, József Balogh

Publication date: 7 June 2013

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

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 positive integers n, r, D, we characterise the edge density threshold that ensures a perfect K_r-packing in any graph G on n vertices and with minimum degree at least 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 K_r-free graphs that satisfy a certain degree sequence condition.

Full work available at URL: https://arxiv.org/abs/1110.3490

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

equitable colouringssubgraph packings

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (20)

• Denser packings obtained in \(O(n \log \log n)\) time
• Packings and perfect path double covers of maximal planar graphs
• Perfect packings in quasirandom hypergraphs. I.
• Perfect Packings in Quasirandom Hypergraphs II
• Downhill domination problem in graphs
• A degree sequence Hajnal-Szemerédi theorem
• Minimum number of edges guaranteeing the existence of a \(K_{1, t}\)-factor in a graph
• Title not available (Why is that?)
• Title not available (Why is that?)
• More-than-nearly-perfect packings and partial designs
• Graphs with unique maximum packing of closed neighborhoods
• On a degree sequence analogue of Pósa's conjecture
• Integer and fractional packings in dense graphs
• A Degree Sequence Komlós Theorem
• On Degree Sequences Forcing The Square of a Hamilton Cycle
• A degree sequence version of the Kühn-Osthus tiling theorem
• Packing \(K_r\)s in bounded degree graphs
• Near packings of graphs
• On sufficient conditions for spanning structures in dense graphs
• A Degree Sequence Strengthening of the Vertex Degree Threshold for a Perfect Matching in 3-Uniform Hypergraphs

This page was built for publication: On perfect packings in dense graphs

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