An Ore-type theorem for perfect packings in graphs

DOI10.1137/080731256MaRDI QIDQ3583306zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(20)

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

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)