Daniela Kühn ; Deryk Osthus

$K_{\ell}^{}$factors in graphs
dmtcs:3403 
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

https://doi.org/10.46298/dmtcs.3403
$K_{\ell}^{}$factors in graphs
Authors: Daniela Kühn ^{1}; Deryk Osthus ^{1}
NULL##NULL
Daniela Kühn;Deryk Osthus
1 School of Mathematics [Birmingham]
Let $K_ℓ^$ denote the graph obtained from $K_ℓ$ by deleting one edge. We show that for every $γ >0$ and every integer $ℓ≥4$ there exists an integer $n_0=n_0(γ ,ℓ)$ such that every graph $G$ whose order $n≥n_0$ is divisible by $ℓ$ and whose minimum degree is at least $(\frac{ℓ^23ℓ+1}{/ ℓ(ℓ2)}+γ )n$ contains a $K_ℓ^$factor, i.e. a collection of disjoint copies of $K_ℓ^$ which covers all vertices of $G$. This is best possible up to the error term $γn$ and yields an approximate solution to a conjecture of Kawarabayashi.