Daniela Kühn ; Deryk Osthus
-
K−ℓ-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−ℓ-factors in graphsConference paper
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{ℓ^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.