The Minimum Degree Threshold for Perfect Graph Packings

Let H be any graph. We determine up to an additive constant the minimum degree of a graph G which ensures that G has a perfect H-packing (also called an H-factor). More precisely, let delta(H, n) denote the smallest integer k such that every graph G whose order n is divisible by vertical bar H vertical bar and with delta(G) >= k contains a perfect H-packing. We show that delta(H, n) = (1-1/chi*(H))n + O(1). The value of chi*(H) depends on the relative sizes of the colour classes in the optimal colourings of H and satisfies chi(H)-1