Some exact results of the generalized Turán numbers for paths

Abstract

For graphs $H$ and $F$ with chromatic number $\chi (F)=k$, we call $H$ strictly $F$-Turán-good (or $(H,F)$ strictly Turán-good) if the Turán graph $T_{k-1}(n)$ is the unique $F$-free graph on $n$ vertices containing the largest number of copies of $H$ when $n$ is large enough. Let $F$ be a graph with chromatic number $\chi (F)\ge 3$ and a color-critical edge and let $P_{\ell }$ be a path with $\ell$ vertices. Gerbner and Palmer (2020, arXiv:2006.03756) showed that $(P_3,F)$ is strictly Turán good if $\chi (H)\ge 4$ and they conjectured that (a) this result is true when $\chi (F)=3$, and, moreover, (b) $(P_{\ell },K_k)$ is Turán-good for every pair of integers $\ell$ and $k$. In the present paper, we show that $(H,F)$ is strictly Turán-good when $H$ is a bipartite graph with matching number $\nu (H)=\lfloor \frac{|V(H)|}{2}\rfloor$ and $\chi (F)=3$, as a corollary, this result confirms the conjecture (a); we also prove that $(P_{\ell },F)$ is strictly Turán-good for $2\le \ell \le 6$ and $\chi (F)\ge 4$, this also confirms the conjecture (b) for $2\le \ell \le 6$ and $k\ge 4$.

17 pages