Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4654847 | European Journal of Combinatorics | 2007 | 13 Pages |
Abstract
Let Kr− denote the graph obtained from KrKr by deleting one edge. We show that for every integer r≥4r≥4 there exists an integer n0=n0(r)n0=n0(r) such that every graph GG whose order n≥n0n≥n0 is divisible by rr and whose minimum degree is at least (1−1/χcr(Kr−))n contains a perfect Kr−-packing, i.e. a collection of disjoint copies of Kr− which covers all vertices of GG. Here χcr(Kr−)=r(r−2)r−1 is the critical chromatic number of Kr−. The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large nn.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Oliver Cooley, Daniela Kühn, Deryk Osthus,