A Common Extension of the Erdős–Stone Theorem and the Alon–Yuster Theorem for Unbounded Graphs

The Erdős–Stone theorem (1946, Bull. Am. Math. Soc., 52, 1089–1091) and the Alon–Yuster theorem (1992, Graphs Comb., 8, 95–102 ) are both very fundamental in extremal graph theory. We give a common extension of them, which states as follows: For everyϵ > 0 and r ≥ 2, there exists c = cϵ, r > 0 such that, for any 0 ≤ θ ≤ 1, if H is a graph of order | H | ≤ clogn and with chromatic number r then every n -vertex graph G with minimum degree at least ( 1 − 1 __ r − 1 + θ ____ r(r − 1)) n contains at least (θ − ϵ)n / | H | vertex-disjoint copies of H. = ϵr (r − 1) or θ = 1, it would imply the two theorems. portant point is that our theorem enables us to deal with a larger graph H of order | H | → ∞(as n → ∞), while | H | was fixed in the Alon–Yuster theorem (and in another common extension by Komlós (2000, Combinatorica,20, 203–218)). unds clogn and ( 1 − 1 __ r − 1 + θ ____r (r − 1)) n are both essentially the best possible.