An Ore-type theorem for perfect packings in graphs

DOI10.1137/080731256zbMATH Open1207.05059arXiv0807.4907OpenAlexW2056485055MaRDI QIDQ3583306FDOQ3583306

Authors: Daniela Kühn, Deryk Osthus, Andrew Treglown 

Publication date: 27 August 2010

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: We say that a graph G has a perfect H-packing (also called an H-factor) if there exists a set of disjoint copies of H in G which together cover all the vertices of G. Given a graph H, we determine, asymptotically, the Ore-type degree condition which ensures that a graph G has a perfect H-packing. More precisely, let delta_{ m Ore} (H,n) be the smallest number k such that every graph G whose order n is divisible by |H| and with d(x)+d(y)geq k for all non-adjacent x ot = y in V(G) contains a perfect H-packing. We determine lim_{n o infty} delta_{ m Ore} (H,n)/n.

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

Recommendations

• The minimum degree threshold for perfect graph packings
• On perfect packings in dense graphs
• A degree sequence Hajnal-Szemerédi theorem
• Embedding graphs having Ore-degree at most five
• The complexity of perfect packings in dense graphs

zbMATH Keywords

regularity Lemma\(H\)-packings\(H\)-factorsOre-type conditions

Mathematics Subject Classification ID

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

Cited In (20)

• Sharp minimum degree conditions for the existence of disjoint theta graphs
• Degree sum and graph linkage with prescribed path lengths
• Embedding graphs having Ore-degree at most five
• Placing specified vertices at precise locations on a Hamiltonian cycle
• A geometric theory for hypergraph matching
• A degree sequence Hajnal-Szemerédi theorem
• Note on semi-linkage with almost prescribed lengths in large graphs
• Embedding spanning bipartite graphs of small bandwidth
• Note on Enomoto and Ota's conjecture for short paths in large graphs
• On directed versions of the Hajnal-Szemerédi theorem
• On perfect packings in dense graphs
• The minimum degree threshold for perfect graph packings
• Enomoto and Ota's conjecture holds for large graphs
• An Ore-type theorem on Hamiltonian square cycles
• Degree conditions for the existence of vertex-disjoint cycles and paths: a survey
• Sufficient conditions for perfect mixed tilings
• Dirac-type results for tilings and coverings in ordered graphs
• On sufficient conditions for spanning structures in dense graphs
• Extremal graph packing problems: Ore-type versus Dirac-type
• Graph Tilings in Incompatibility Systems

This page was built for publication: An Ore-type theorem for perfect packings in graphs

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