Perfect packings with complete graphs minus an edge (Q2461771)

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)].