A strengthening of the spectral chromatic critical edge theorem: books and theta graphs

Abstract

The chromatic critical edge theorem of Simonovits states that for a given color critical graph $H$ with $\ddot{I}‡(H)=k+1$, there exists an $n_0(H)$ such that the Turán graph $T_{n,k}$ is the only extremal graph with respect to $ex(n,H)$ provided $n\ge n_0(H)$. Nikiforov's pioneer work on spectral graph theory implies that the color critical edge theorem also holds if $ex(n,H)$ is replaced by the maximum spectral radius and $n_0(H)$ is an exponential function of $|H|$. We want to know which color critical graphs $H$ satisfy that $n_0(H)$ is a linear function of $|H|$. Previous graphs include complete graphs and odd cycles. In this paper, we find two new classes of graphs: books and theta graphs. Namely, we prove that every graph on $n$ vertices with $\ddot{I}(G)>\ddot{I}(T_{n,2})$ contains a book of size greater than $\frac{n}{6.5}$. This can be seen as a spectral version of a 1962 conjecture by Erdős, which states that every graph on $n$ vertices with $e(G)>e(T_{n,2})$ contains a book of size greater than $\frac{n}{6}$. In addition, our result on theta graphs implies that if $G$ is a graph of order $n$ with $\ddot{I}(G)>\ddot{I}(T_{n,2})$, then $G$ contains a cycle of length $t$ for every $t\le \frac{n}{7}$. This is related to an open question by Nikiforov which asks to determine the maximum $c$ such that every graph $G$ of large enough order $n$ with $\ddot{I}(G)>\ddot{I}(T_{n,2})$ contains a cycle of length $t$ for every $t\le cn$.

17 pages