Extremal graphs without long paths and a given graph

Abstract

For a family of graphs $\mathcal{F}$, the Turán number $ex(n,\mathcal{F})$ is the maximum number of edges in an $n$-vertex graph containing no member of $\mathcal{F}$ as a subgraph. The maximum number of edges in an $n$-vertex connected graph containing no member of $\mathcal{F}$ as a subgraph is denoted by $e{x}_{conn}(n,\mathcal{F})$. Let $P_k$ be the path on $k$ vertices and $H$ be a graph with chromatic number more than $2$. Katona and Xiao [Extremal graphs without long paths and large cliques, European J. Combin., 2023 103807] posed the following conjecture: Suppose that the chromatic number of $H$ is more than $2$. Then $ex(n,\{H,P_k\})=n\max \{\lfloor \frac{k}{2}\rfloor -1,\frac{ex(k-1,H)}{k-1}\}+O_k(1)$. In this paper, we determine the exact value of $e{x}_{conn}(n,\{P_k,H\})$ for sufficiently large $n$. Moreover, we obtain asymptotical result for $ex(n,\{P_k,H\})$, which solves the conjecture proposed by Katona and Xiao.

arXiv comment16 pages, 6 conferences