On Turán-good graphs

Abstract

For graphs H and F, the generalized Turán number ex(n,H,F) is the largest number of copies of H in an F-free graph on n vertices. We say that H is F-Turán-good if ex(n,H,F) is the number of copies in the (χ(F)−1)-partite Turán graph, provided n is large enough. We present a general theorem in case F has an edge whose deletion decreases the chromatic number. In particular, this determines ex(n,Pk,C2ℓ+1) and ex(n,C2k,C2ℓ+1) exactly, if n is large enough. We also study the case when F has a vertex whose deletion decreases the chromatic number.

Topics & Concepts