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 n
such that every graph 0
=n0
(γ,ℓ)G
whose order n≥n
is divisible by 0
ℓ
and whose minimum degree is at least (ℓ
contains a 2
-3ℓ+1 / ℓ(ℓ-2)+γ)nK
-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