\(H\)-factors in dense graphs (Q1924126): Difference between revisions

The following asymptotic result is proved. For every \(\varepsilon> 0\), and for every positive integer \(h\), there exists an \(n_0= n_0(\varepsilon, h)\) such that for every graph \(H\) with \(h\) vertices and for every \(n> n_0\), any graph \(G\) with \(hn\) vertices and with minimum degree \[ d\geq \Biggl({\chi(H)- 1\over \chi(H)}+ \varepsilon\Biggr)hn \] contains \(n\) vertex disjoint copies of \(H\). This result is asymptotically tight and its proof supplies a polynomial time algorithm for the corresponding algorithmic problem.