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

A graph is color‐critical if it contains an edge whose removal reduces its chromatic number. LetT n , k${T}_{n,k}$ be the Turán graph withn $n$ vertices andk $k$ parts. Given a graphH $H$ , lete x ( n , H )$ex(n,H)$ be the Turán number ofH $H$ . Simonovits' chromatic critical edge theorem states that ifH $H$ is color‐critical withχ ( H ) = k + 1 $\chi (H)=k+1$ , then there exists ann 0 ( H )${n}_{0}(H)$ such thate x ( n , H ) = | E ( T n , k ) | $ex(n,H)=|E({T}_{n,k})|$ and the Turán graphT n , k${T}_{n,k}$ is the only extremal graph providedn ≥ n 0 ( H )$n\ge {n}_{0}(H)$ . Nikiforov proved a spectral chromatic critical edge theorem. It asserts that ifH $H$ is color‐critical andχ ( H ) = k + 1 $\chi (H)=k+1$ , then there exists ann 0 ( H )${n}_{0}(H)$ (which is exponential with| V ( H ) | $|V(H)|$ ) such thate x s p( n , H ) = ρ ( T n , k )$e{x}_{sp}(n,H)=\rho ({T}_{n,k})$ andT n , k${T}_{n,k}$ is the only extremal graph providedn ≥ n 0 ( H )$n\ge {n}_{0}(H)$ , whereρ ( G )$\rho (G)$ is the spectral radius ofG $G$ ande x s p( n , H ) = max { ρ ( G ) : | V ( G ) | = n and H ⊈ G }$e{x}_{sp}(n,H)=\max \{\rho (G):|V(G)|=n\,\text{and}\,H \nsubseteq G\}$ . In addition, ifH $H$ is either a complete graph or an odd cycle, thenn 0 ( H )${n}_{0}(H)$ is linear with| V ( H ) | $|V(H)|$ . A book graphB r${B}_{r}$ is a set ofr $r$ triangles sharing a common edge and a theta graphθ r${\theta }_{r}$ is a graph which consists of two vertices connected by three internally disjoint paths with length one, two, andr $r$ . Notice that bothB r${B}_{r}$ andθ r${\theta }_{r}$ are color‐critical. In this article, we prove that ifρ ( G ) ≥ ρ ( T n , 2 )$\rho (G)\ge \rho ({T}_{n,2})$ , thenG $G$ contains a bookB r${B}_{r}$ withr > 2 13 n $r\gt \frac{2}{13}n$ unlessG = T n , 2$G={T}_{n,2}$ . Similarly, we prove that ifρ ( G ) ≥ ρ ( T n , 2 )$\rho (G)\ge \rho ({T}_{n,2})$ , thenG $G$ contains a theta graphθ r${\theta }_{r}$ withr > n 10$r\gt \frac{n}{10}$ for oddr $r$ andr > n 7$r\gt \frac{n}{7}$ for evenr $r$ unlessG = T n , 2$G={T}_{n,2}$ . Our results imply thatn 0 ( H )${n}_{0}(H)$ in the spectral chromatic critical edge theorem is linear with| V ( H ) | $|V(H)|$ for book graphs and theta graphs. Our result for book graphs can be viewed as a spectral version of an Erdős conjecture (1962) stating that everyn $n$ ‐vertex graph with| E ( G ) | > | E ( T n , 2 ) | $|E(G)|\gt |E({T}_{n,2})|$ contains a book graphB r${B}_{r}$ withr > n 6 . $r\gt \frac{n}{6}.$ Moreover, our result for theta graphs yields that every graph withρ ( G ) > ρ ( T n , 2 )$\rho (G)\gt \rho ({T}_{n,2})$ contains a cycle of lengtht $t$ for eacht ≤ n 7$t\le \frac{n}{7}$ . This is related to an open question by Nikiforov (2008) which asks for the maximumc $c$ such that every graph of large enough ordern $n$ withρ ( G ) > ρ ( T n , 2 )$\rho (G)\gt \rho ({T}_{n,2})$ contains a cycle of lengtht $t$ for everyt ≤ c n $t\le cn$ .