2021/02/08 by Mingqing Zhai, Huiqiu Lin, Zhai, Mingqing +1 · 8 citations
Computer Science · Mathematics · #05C50 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2102.04041
openalex publication_date 2021/02/08 · openalex created_date 2022/09/04 · openalex updated_date 2026/07/28
The chromatic critical edge theorem of Simonovits states that for a given color critical graph H with χ(H)=k+1, there exists an n0(H) such that the Turán graph Tn,k is the only extremal graph with respect to ex(n,H) provided n ≥ n0(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 n0(H) is an exponential function of |H|. We want to know which color critical graphs H satisfy that n0(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 ρ(G)>ρ(Tn,2) contains a book of size greater than (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(Tn,2) contains a book of size greater than (n)/(6). In addition, our result on theta graphs implies that if G is a graph of order n with ρ(G)>ρ(Tn,2), then G contains a cycle of length t for every t≤ (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 ρ(G)>ρ(Tn,2) contains a cycle of length t for every t≤ cn.