Perfect packings with complete graphs minus an edge (Q2461771)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Perfect packings with complete graphs minus an edge
scientific article

    Statements

    Perfect packings with complete graphs minus an edge (English)
    0 references
    0 references
    0 references
    0 references
    21 November 2007
    0 references
    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)].
    0 references
    packing
    0 references
    perfect packing
    0 references

    Identifiers