Processing math: 26%

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

  • 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.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: graph packing,factor,critical chromatic number,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]

Consultation statistics

This page has been seen 249 times.
This article's PDF has been downloaded 232 times.