A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs. Issue 3 (2nd September 2022)

• Record Type: Journal Article
• Authors: Zhai, Mingqing; Lin, Huiqiu
• Is Part Of: Journal of graph theory. Volume 102:Issue 3(2023)
• Page Start: 502
• Page End: 520
• Publication Date: 2022-09-02
• Subjects: book -- chromatic critical edge theorem -- consecutive cycles -- spectral extrema -- theta graph; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22883
• Languages: English
• ISSNs: 0364-9024

Abstract

Abstract: A graph is color‐critical if it contains an edge whose removal reduces its chromatic number. Let T n, k ${T}_{n, k}$ be the Turán graph with n $n$ vertices and k $k$ parts. Given a graph H $H$, let e x ( n, H ) $ex(n, H)$ be the Turán number of H $H$ . Simonovits' chromatic critical edge theorem states that if H $H$ is color‐critical with χ ( H ) = k + 1 $\chi (H)=k+1$, then there exists an n 0 ( H ) ${n}_{0}(H)$ such that e x ( n, H ) = | E ( T n, k ) | $ex(n, H)=|E({T}_{n, k})|$ and the Turán graph T n, k ${T}_{n, k}$ is the only extremal graph provided n ≥ n 0 ( H ) $n\ge {n}_{0}(H)$ . Nikiforov proved a spectral chromatic critical edge theorem. It asserts that if H $H$ is color‐critical and χ ( H ) = k + 1 $\chi (H)=k+1$, then there exists an n 0 ( H ) ${n}_{0}(H)$ (which is exponential with | V ( H ) | $|V(H)|$ ) such that e x s p ( n, H ) = ρ ( T n, k ) $e{x}_{sp}(n, H)=\rho ({T}_{n, k})$ and T n, k ${T}_{n, k}$ is the only extremal graph provided n ≥ n 0 ( H ) $n\ge {n}_{0}(H)$, where ρ ( G ) $\rho (G)$ is the spectral radius of G $G$ and e 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, if H $H$ is either a complete graph or an odd cycle, then n 0 ( H ) ${n}_{0}(H)$ is linear with | V ( H ) | $|V(H)|$ . A book graph B r ${B}_{r}$ is a set of r $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, and r $r$ . Notice that both B 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})$, then G $G$ contains a book B r ${B}_{r}$ with r > 2 13 n $r\gt \frac{2}{13}n$ unless G = T n, 2 $G={T}_{n, 2}$ . Similarly, we prove that if ρ ( G ) ≥ ρ ( T n, 2 ) $\rho (G)\ge \rho ({T}_{n, 2})$, then G $G$ contains a theta graph θ r ${\theta }_{r}$ with r > n 10 $r\gt \frac{n}{10}$ for odd r $r$ and r > n 7 $r\gt \frac{n}{7}$ for even r $r$ unless G = T n, 2 $G={T}_{n, 2}$ . Our results imply that n 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 every n $n$ ‐vertex graph with | E ( G ) | > | E ( T n, 2 ) | $|E(G)|\gt |E({T}_{n, 2})|$ contains a book graph B r ${B}_{r}$ with r > 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 length t $t$ for each t ≤ n 7 $t\le \frac{n}{7}$ . This is related to an open question by Nikiforov (2008) which asks for the maximum c $c$ such that every graph of large enough order n $n$ with ρ ( G ) > ρ ( T n, 2 ) $\rho (G)\gt \rho ({T}_{n, 2})$ contains a cycle of length t $t$ for every t ≤ c n $t\le cn$ .