Perfect packings with complete graphs minus an edge

Let K-r(-) denote the graph obtained From K-r by deleting one edge. We show that for every integer r >= 4 there exists an integer n(0) = n(0)(r) such that every graph G whose order n >= n(0) is divisible by r and whose minimum degree is at least (1 - 1/X-cr(K-r(-)))n contains a perfect K-r(-)-packing, i.e. a collection of disjoint copies of K-r(-) which covers all vertices of G. Here X-cr(K-r(-)) = r(r-2)/r-1 is the critical chromatic number of K-r(-). The bound on the minimum degree is best possible and confirms a conjecture of Kawarabayashi for large n. (C) 2007 Elsevier Ltd. All rights reserved.