Skip to Main content Skip to Navigation
Conference papers

$K_{\ell}^{-}$-factors in graphs

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 $(\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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184359
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:37:20 AM
Last modification on : Thursday, May 11, 2017 - 1:02:53 AM
Long-term archiving on: : Sunday, November 15, 2015 - 10:59:58 AM

File

dmAE0139.pdf
Publisher files allowed on an open archive

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

  • HAL Id : hal-01184359, version 1

Collections

Citation

Daniela Kühn, Deryk Osthus. $K_{\ell}^{-}$-factors in graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.199-202. ⟨hal-01184359⟩

Share

Metrics

Record views

392

Files downloads

605