Perfect packings with complete graphs minus an edge

2006/05/08 by Cooley, Oliver, Kühn, Daniela, Osthus, Deryk · 1 citation
#05C15 #05C35 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.math/0605189

Abstract

Let K_r^- denote the graph obtained from K_r by deleting one edge. We show that for every integer r≥ 4 there exists an integer n₀=n₀(r) such that every graph G whose order n≥ n₀ is divisible by r and whose minimum degree is at least (1-1/chi_cr(K_r^-))n contains a perfect K_r^- packing, i.e. a collection of disjoint copies of K_r^- which covers all vertices of G. Here chi_cr(K_r^-)=r(r-2)/(r-1) is the critical chromatic number of K_r^-. The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n.

Cited by

• Perfect Matchings in Random Sparsifications of Dense Hypergraphs

Related

• On perfect packings in dense graphs
• The minimum degree threshold for perfect graph packings
• Graphs that are critical for the packing chromatic number
• A degree sequence Hajnal--Szemerédi theorem
• S-packing chromatic critical graphs