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

DOI10.1002/JGT.22883MaRDI QIDQ6046685zbMATH OpenWikidataFDO

Authors Mingqing Zhai, Huiqiu Lin

Publication date 6 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.04041

zbMATH Keywords

booktheta graphconsecutive cycleschromatic critical edge theoremspectral extrema

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Abstract: The chromatic critical edge theorem of Simonovits states that for a given color critical graph $H$ with $chi(H)=k+1$, there exists an $n_0(H)$ such that the Tur'an graph $T_{n,k}$ is the only extremal graph with respect to $ex(n,H)$ provided $ngeq{n}_0(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 $n_0(H)$ is an exponential function of $|H|$. We want to know which color critical graphs $H$ satisfy that $n_0(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 $ho(G)>ho(T_{n,2})$ contains a book of size greater than $fracn6.5$. This can be seen as a spectral version of a 1962 conjecture by ErdH{o}s, which states that every graph on $n$ vertices with $e(G)>e(T_{n,2})$ contains a book of size greater than $fracn6$. In addition, our result on theta graphs implies that if $G$ is a graph of order $n$ with $ho(G)>ho(T_{n,2})$, then $G$ contains a cycle of length $t$ for every $tleqfracn7$. 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 $ho(G)>ho(T_{n,2})$ contains a cycle of length $t$ for every $tleqcn$.

Recommendations

• Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs
• The spectral radius of edge chromatic critical graphs
• Turán numbers of theta graphs
• Counting substructures. I: Color critical graphs
• Spectral radii of graphs with given chromatic number

Cites work

• scientific article; zbMATH DE number 3652373 (Why is no real title available?)
• scientific article; zbMATH DE number 3652374 (Why is no real title available?)
• scientific article; zbMATH DE number 3659602 (Why is no real title available?)
• scientific article; zbMATH DE number 881161 (Why is no real title available?)
• scientific article; zbMATH DE number 3262986 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• A complete solution to the Cvetković–Rowlinson conjecture
• A contribution to the Zarankiewicz problem
• A spectral Erdős-Stone-Bollobás theorem
• A spectral condition for odd cycles in graphs
• Books in graphs
• Bounds on graph eigenvalues. II
• Eigenvalues and triangles in graphs
• Eigenvalues of \(K_{1,k}\)-free graphs and the connectivity of their independence complexes
• Extensions of the Erdős-Gallai theorem and Luo's theorem
• Extremal numbers for odd cycles
• Extremal problems and generalized degrees
• Graphs without theta subgraphs
• On a class of degenerate extremal graph problems
• On a theorem of Rademacher-Turán
• On maximal paths and circuits of graphs
• On some Ramsey and Turán-type numbers for paths and cycles
• On the Turán number of forests
• On the spectral radius of graphs without a star forest
• Path Ramsey numbers in multicolorings
• Proof of a conjecture on the spectral radius of \(C_4\)-free graphs
• Regular graphs, eigenvalues and regular factors
• Some new results in extremal graph theory
• Spectral bounds for the clique and independence numbers of graphs
• Spectral conditions for the existence of specified paths and cycles in graphs
• Spectral extrema for graphs: the Zarankiewicz problem
• Spectral extrema of graphs: forbidden hexagon
• Spectral extremal results with forbidding linear forests
• Spectral saturation: inverting the spectral Turán theorem
• Spektren endlicher Grafen
• The Turán number for spanning linear forests
• The Turán number of disjoint copies of paths
• The Turán number of star forests
• The maximum spectral radius of graphs without friendship subgraphs
• The spectral radius of graphs with no odd wheels
• The spectral radius of graphs without paths and cycles of specified length
• Three conjectures in extremal spectral graph theory
• Turán numbers of multiple paths and equibipartite forests
• Turán numbers of theta graphs

Cited in

(14)

• A spectral Erdős-Rademacher theorem
• Stability of Woodall's theorem and spectral conditions for large cycles
• On the spectral radius of graphs without a gem
• Spectral extrema of graphs with fixed size: forbidden triangles and pentagons
• Eigenvalues and cycles of consecutive lengths
• Spectral extremal graphs without intersecting triangles as a minor
• Turán-type problems on \([a, b]\)-factors of graphs, and beyond
• Spectral extremal problem on disjoint color-critical graphs
• Spectral extremal graphs for the bowtie
• Spectral strengthening of a theorem on transversal critical graphs
• A spectral condition for the existence of cycles with consecutive odd lengths in non-bipartite graphs
• Counting substructures and eigenvalues. I: Triangles
• Forbidden theta graph, bounded spectral radius and size of non-bipartite graphs
• The spectral radius, maximum average degree and cycles of consecutive lengths of graphs

This page was built for publication: A strengthening of the spectral chromatic critical edge theorem: Books and theta graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6046685)