Counting large cliques in graphs with a forbidden tree

Abstract

Given graphs $H$ and $F$, the generalized Turán number $\mathrm{ex}(n,H,F)$ is the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Alon and Shikhelman (J. Combin. Theory Ser. B, 2016) initiated the systematic study of generalized Turán problems. Let $T$ be a tree on $k$ vertices, and write $n=a(k-1)+b$, where $0\le b<k-1$. Recently, Gerbner and Palmer (Electron. J. Combin., 2026) proposed the following conjecture: for every $r\ge 3$, the graph $a{K}_{k-1}\cup K_b$ maximizes the number of copies of $K_r$ among all $n$-vertex $T$-free graphs. In this paper, we verify their conjecture when $r=k-2$ or $r=k-3\ge 5$. More precisely, we show that $\mathrm{ex}(n,K_r,T)=a\left(\genfrac{}{}{0ex}{}{k-1}{r}\right)+\left(\genfrac{}{}{0ex}{}{b}{r}\right)$ and characterize all extremal graphs.

8 pages