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

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
0
=n
0
(γ,ℓ)
such that every graph
G
whose order
n≥n
0
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