Turán-Type Bounds for Graphs Containing Large $F$-Sparse Sets

Abstract

We study Turán-type extremal problems for graphs containing a large $F$-sparse vertex set, meaning a vertex set whose induced subgraph contains few copies of $F$. For integers $r>s\ge 1$, we prove that if a $K_{r+1}$-free graph $G$ on $n$ vertices contains a set $M$ of size $m\ge \lceil sn/r\rceil$ such that $G[M]$ is $K_{s+1}$-free, then \[ e(G)\le m(n-m)+t_s(m)+t_{r-s}(n-m). \] We characterize the equality cases as the complete $r$-partite graphs whose vertex classes split into two balanced groups of total sizes $m$ and $n-m$, consisting of $s$ and $r-s$ classes, respectively. We also prove a color-critical extension for forbidden graphs that embed into a join of two edge-critical graphs, together with an asymptotic extension for general $H$-free graphs in which the prescribed large vertex set spans few copies of a fixed graph $F$ with $\ddot{I}‡(F)<\ddot{I}‡(H)$.

21 pages