Turán number of books in non-bipartite graphs

Abstract

Let $\mathrm{ex}(n,H)$ be the Turán number of $H$ for a given graph $H$. A graph is color-critical if it contains an edge whose removal reduces its chromatic number. Simonovits' chromatic critical edge theorem states that if $H$ is color-critical with $\chi (H)=k+1$, then there exists an $n_0(H)$ such that ex$(n,H)=e(T_{n,k})$ and the Turán graph $T_{n,k}$ is the only extremal graph provided $n\ge n_0(H).$ A book graph $B_{r+1}$ is a set of $r+1$ triangles with a common edge, where $r\ge 0$ is an integer. Note that $B_{r+1}$ is a color-critical graph with $\chi (B_{r+1})=3$. Simonovits' theorem implies that $T_{n,2}$ is the only extremal graph for $B_{r+1}$-free graphs of sufficiently large order $n$. Furthermore, Edwards and independently Khadžiivanov and Nikiforov completely confirmed Erdős' booksize conjecture and obtained that ex$(n,B_{r+1})=e(T_{n,2})$ for $n\ge n_0(B_{r+1})=6r$. Recently, Zhai and Lin [J. Graph Theory 102 (2023) 502-520] investigated the problem of booksize from a spectral perspective. Note that the extremal graph $T_{n,2}$ is bipartite. Motivated by the above elegant results, we in this paper focus on the Turán problem of non-bipartite $B_{r+1}$-free graphs of order $n$. For $r=0,$ Erdős proved a nice result: If $G$ is a non-bipartite triangle-free graph on $n$ vertices, then $e(G)\le \lfloor \frac{(n-1{)}^2}{4}\rfloor +1$. For general $r\ge 1,$ we determine the exact value of Turán number of $B_{r+1}$ in non-bipartite graphs and characterize all extremal graphs provided $n$ is sufficiently large. An interesting phenomenon is that the Turán numbers and extremal graphs are completely different for $r=0$ and general $r\ge 1.$

16 pages, 6 figures