The Complexity of Perfect Packings in Dense Graphs

摘要

Let H be a graph of order h and let G be a graph of order n such that h | n. A perfect H-packing in G is a collection of vertex disjoint copies of H in G that covers all vertices of G. Hell and Kirk-patrick showed that the decision problem whether a graph G has a perfect H-packing is NP-complete if and only if H has a component which contains at least 3 vertices. We consider the decision problem of containment of a perfect H-packing in graphs G under the additional minimum degree condition. Our main result shows that given any γ > 0 and any n-vertex graph G with minimum degree at least (1 — 1/χ_(cr)(H) + γ)n, the problem of determining whether G has a perfect H-packing can be solved in polynomial time, where χ_(cr)(H) is the critical chromatic number of H. This answers a question of Yuster negatively. Moreover, a hardness result of Kuhn and Osthus shows that our main result is essentially best possible and closes a long-standing hardness gap for all complete multi-partite graphs H whose second smallest color class has size at least 2.