文献类型：期刊文献

英文题名：A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs

作者：Zhai, Mingqing[1];Lin, Huiqiu[2]

机构：[1]Chuzhou Univ, Sch Math & Finance, Dept Appl Math, Chuzhou, Anhui, Peoples R China;[2]East China Univ Sci & Technol, Sch Math, Dept Math, Shanghai 200237, Peoples R China

年份：2023

卷号：102

期号：3

起止页码：502

外文期刊名：JOURNAL OF GRAPH THEORY

收录：;EI(收录号：20223812757473);WOS:【SCI-EXPANDED(收录号:WOS:000849625400001)】；

基金：Anhui Provincial Natural Science Foundation; National Nature Science Foundation of China; Natural Science Foundation of Shanghai

语种：英文

外文关键词：book; chromatic critical edge theorem; consecutive cycles; spectral extrema; theta graph

摘要：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 Turan graph with n $n$ vertices and k $k$ parts. Given a graph H $H$, let e x ( n , H ) $ex(n,H)$ be the Turan number of H $H$. Simonovits' chromatic critical edge theorem states that if H $H$ is color-critical with chi ( 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 Turan 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 chi ( 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 ) = rho ( 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 rho ( G ) $\rho (G)$ is the spectral radius of G $G$ and e x s p ( n , H ) = max { rho ( G ) : | V ( G ) | = n and H not subset of 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 theta 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 theta r ${\theta }_{r}$ are color-critical. In this article, we prove that if rho ( G ) >= rho ( 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 rho ( G ) >= rho ( T n , 2 ) $\rho (G)\ge \rho ({T}_{n,2})$, then G $G$ contains a theta graph theta 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 Erdos 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 rho ( G ) > rho ( 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 rho ( G ) > rho ( 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$.