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 $(\chi (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,P_k,C_{2\ell +1})$ and $ex(n,C_{2k},C_{2\ell +1})$ exactly, if $n$ is large enough. We also study the case when $F$ has a vertex whose deletion decreases the chromatic number.

12 pages