Perfect packings with complete graphs minus an edge

DOI10.1016/J.EJC.2007.04.002MaRDI QIDQ2461771zbMATH OpenOpenAlexFDO

Authors Oliver Cooley, Deryk Osthus, Daniela Kühn

Publication date 21 November 2007

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

packingperfect packing

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let K_r^- denote the graph obtained from K_r by deleting one edge. We show that for every integer rge 4 there exists an integer n_0=n_0(r) such that every graph G whose order nge n_0 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.

Review text

Let \(G\) be a graph of order \(n\) and \(K^{-}_{r}\) be the complete graph \(K_r\) minus one edge. Then \(G\) contains a perfect \(K^{-}_{r}\)-packing if the vertex set of \(G\) can be partitioned into \(n/r\) subsets such that the graph induced by each of these subsets contains a subgraph isomorphic to \(K^{-}_{r}\). It is shown that for every \(r\geq 4\) there is a constant \(n_0=n_0(r)\) such that every \(G\) of order \(n\geq n_0\) with \(n\) divisible by \(r\) and \(\delta (G)\geq 1 -1/{\chi _{cr}(K^{-}_{r})}\) contains a perfect \(K^{-}_{r}\)-packing. \(\chi _{cr}{(K^{-}_{r})}=\frac{r(r-2)}{r-1}\) is the critical chromatic number of \(K^{-}_{r}\). It is also shown that the bound on the minimum bound is the best possible, which confirms a conjecture by \textit{Ken-ichi Kawarabayashi} [J. Graph Theory 39, 111--128 (2002; Zbl 0992.05059)].

Recommendations

• The minimum degree threshold for perfect graph packings
• On perfect packings in dense graphs
• Packings in Dense Regular Graphs
• K_^--factors in graphs
• The complexity of perfect packings in dense graphs

Cites work

• K₄⁻‐factor in a graph
• \(H\)-factors in dense graphs
• Critical chromatic number and the complexity of perfect packings in graphs
• scientific article; zbMATH DE number 4191728 (Why is no real title available?)
• scientific article; zbMATH DE number 3344609 (Why is no real title available?)
• On the maximal number of independent circuits in a graph
• Proof of the Alon-Yuster conjecture
• The Blow-up Lemma
• Tiling Turán theorems

Cited in

(10)

• The minimum degree threshold for perfect graph packings
• The complexity of perfect matchings and packings in dense hypergraphs
• Minimum number of edges guaranteeing the existence of a \(K_{1, t}\)-factor in a graph
• The complexity of perfect packings in dense graphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• K_^--factors in graphs
• Combinatorial and computational aspects of graph packing and graph decomposition
• Packings in Dense Regular Graphs
• Graph Tilings in Incompatibility Systems
• H-factors in graphs with small independence number

This page was built for publication: Perfect packings with complete graphs minus an edge

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