Critical chromatic number and the complexity of perfect packings in graphs
Daniela Kühn, Deryk Osthus · 2006
Abstract. Let H be any non-bipartite graph. We determine asymptotically the minimum degree of a graph G which ensures that G has a perfect H-packing. More precisely, we determine the smallest number τ having the following property: For every positive constant γ there exists an integer n0 = n0(γ, H) such that every graph G whose order n ≥ n0 is divisible by |H | and whose minimum degree is at least (τ + γ) n contains a perfect H-packing. The value of τ depends on the relative sizes of the colour classes in the optimal colourings of H. The proof is algorithmic, which shows that the problem of finding a maximum H-packing is polynomially solvable for graphs G whose minimum degree is at least (τ + γ)n. On the other hand, given any positive constant γ, we show that for infinitely many (non-bipartite) graphs H the corresponding decision problem becomes NP-complete if one considers input graphs G of minimum degree at least (τ − γ)n. 1.