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

DOI10.1002/JGT.22883zbMATH Open1522.05285arXiv2102.04041WikidataQ113915756 ScholiaQ113915756MaRDI QIDQ6046685FDOQ6046685

Authors: Mingqing Zhai, Huiqiu Lin 

Publication date: 6 October 2023

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

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$.

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

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

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)

Cites Work

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

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)