DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Kℓ--factors in graphs

Daniela Kühn, Deryk Osthus


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

Valid XHTML 1.0 Transitional