A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs. Issue 3 (2nd September 2022) - Zhai, Mingqing; Lin, Huiqiu
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 χ (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 ) nn_0(H) . Nikiforov proved a spectral chromatic critical edge theorem. It asserts that if H H is color‐critical and χ ( H ) = k + 1 χ (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 ) ex_sp(n, H)=ρ (T_n, k) and T n, k T_n, k is the only extremal graph provided n ≥ n 0 ( H ) nn_0(H), where ρ ( G ) ρ (G) is the spectral radius of G G and e x s p ( n, H ) = max ρ ( G ) : | V ( G ) | = n and H ⊈ G ex_sp(n, H)={ρ (G):|V(G)|=n and H subseteq 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 θ _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 θ _r are color‐critical. In this article, we prove that if ρ ( G ) ≥ ρ ( T n, 2 ) ρ (G)ρ (T_n, 2), then G G contains a book B r B_r with r > 2 13 n r213n unless G = T n, 2 G=T_n, 2 . Similarly, we prove that if ρ ( G ) ≥ ρ ( T n, 2 ) ρ (G)ρ (T_n, 2), then G G contains a theta graph θ r θ _r with r > n 10 rn10 for odd r r and r > n 7 rn7 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)||E(T_n, 2)| contains a book graph B r B_r with r > n 6 . rn6. Moreover, our result for theta graphs yields that every graph with ρ ( G ) > ρ ( T n, 2 ) ρ (G)ρ (T_n, 2) contains a cycle of length t t for each t ≤ n 7 tn7 . 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 ) ρ (G)ρ (T_n, 2) contains a cycle of length t t for every t ≤ c n tcn .