The exact Turán number of generalized book graph $B_{r,k}$ in non-$r$-partite graphs

Abstract

Given a graph $H,$ we say that a graph is \textit{$H$-free} if it does not contain $H$ as a subgraph. The Turán number $\ex(n,H)$ of $H$ is the maximum number of edges in an $n$-vertex $H$-free graph, the set of all the corresponding extremal graphs is denoted by $\Ex(n, H)$. The study of Turán number of graphs is a central topic in extremal graph theory. A graph is \textit{color-critical} if it contains an edge whose deletion reduces its chromatic number. Simonovits showed that if $H$ is a color-critical graph of chromatic number $r+1,$ then for sufficiently large $n,$ $\Ex(n, H)=\{T_r(n)\},$ the $r$-partite Turán graph of order $n.$ Given a color-critical graph $H$ with chromatic number $r+1,$ it is interesting to determine $H$-free non-$r$-partite graphs with maximum number of edges. For a graph $H$ with chromatic number $r+1,$ denote $\ex_{r+1}(n,H)$ the maximum number of edges in non-$r$-partite $H$-free graphs of order $n,$ the set of all non-$r$-partite $H$-free graphs of order $n$ and size $\ex_{r+1}(n,H)$ is denoted by $\Ex_{r+1}(n, H)$. For $r\ge 3,k\ge 1,$ the generalized book graph \({B}_{r,k}\) is a graph obtained by joining every vertex of $K_r$ to every vertex of an independent set of size \(k\). Note that \({B}_{r,k}\) is a color-critical graph of chromatic number $r+1.$ In this paper, based on the stability theory and local structure characterization, the exact value of $\ex_{r+1}(n,B_{r,k})$ is determined and all the corresponding extremal graphs are identified, where $r\ge 3,k\ge 1$ and $n$ is sufficiently large.

15 pages