Article ID Journal Published Year Pages File Type
4654847 European Journal of Combinatorics 2007 13 Pages PDF
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
, , ,