Kℓ--factors in graphs
Daniela Kühn, Deryk Osthus
Abstract
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 n0=n0(γ,ℓ) such that every graph G whose order n≥n0 is divisible by ℓ and whose minimum degree is at least (ℓ2-3ℓ+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.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page