Degree Sequences of F-Free Graphs - Pikhurko, Oleg; Taraz, Anusch (The Electronic Journal of Combinatorics, 2005)
Let F be a fixed graph of chromatic number r+1. We prove that for all large n the degree sequence of any F-free graph of order n is, in a sense, close to being dominated by the degree sequence of some r-partite graph. We present two different proofs: one goes via the Regularity Lemma and the other uses a more direct counting argument. Although the latter proof is longer, it gives better estimates and allows F to grow with n. As an application of our theorem, we present new results on the generalization of the Turán problem introduced by Caro and Yuster [Electronic J. Combin. 7 (2000)].