The exact Turán number of the even wheel $W_{2k+2}$ among non-$3$-partite graphs

Abstract

Let $\mathrm{ex}(n,H)$ denote the Turán number of $H$. A graph is color-critical if there exists an edge $e\in E(H)$ such that $\chi (H-e)<\chi (H)$. For a color-critical graph $H$ with $\chi (H)=r+1$, Simonovits' chromatic critical edge theorem implies that there exists an $n_0(H)$ such that $\mathrm{ex}(n,H)=e(T_{n,r})$ and the Turán graph $T_{n,r}$ is the only extremal graph provided $n\ge n_0(H).$ Let $W_{2k+2}$ be the even wheel obtained by joining a vertex to a cycle of length $2k+1,$ where $k\ge 1$ is an integer. Since $W_{2k+2}$ is color-critical and $\chi (W_{2k+2})=4$, $T_{n,3}$ is the unique extremal graph for $W_{2k+2}$-free graphs of sufficiently large $n.$ Note that the extremal graph $T_{n,3}$ is 3-partite. In this paper, we determine the exact Turán number of $W_{2k+2}$ in non-$3$-partite graphs and characterize all extremal graphs provided $n$ is sufficiently large.

30 pages, 3 figures