Refining the Graph Density Condition for the Existence of Almost $K$-factors

Abstract

Alon and Yuster {[4]} have proven that if a fixed graph $K$ on $g$ vertices is $(h+1)$-colorable, then any graph $G$ with $n$ vertices and minimum degree at least $\frac{h}{h+1}n$ contains at least $(1-ϵ)\frac{n}{g})$ vertex disjoint copies of $K$, provided $n>N(ϵ)$. It is shown here that the required minimum degree of $G$ for this result to follow is closer to $\frac{h-1}{h}n$, provided $K$ has a proper $(h+1)$-coloring in which some of the colors occur rarely. A conjecture regarding the best possible result of this type is suggested.