Some new results in extremal graph theory

By Vladimir Nikiforov. 2011

151 citations recorded by the source corpus.

In recent years several classical results in extremal graph theory have been improved in a uniform way and their proofs have been simplified and streamlined. These results include a new Erd\H{o}s-Stone-Bollob\'as theorem, several stability theorems, several saturation results and bounds for the number of graphs with large forbidden subgraphs. Another recent trend is the expansion of spectral extremal graph theory, in which extremal properties of graphs are studied by means of eigenvalues of various matrices. One particular achievement in this area is the casting of the central results above in spectral terms, often with additional enhancement. In addition, new, specific spectral results were found that have no conventional analogs. All of the above material is scattered throughout various journals, and since it may be of some interest, the purpose of this survey is to present the best of these results in a uniform, structured setting, together with some discussions of the underpinning ideas.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/2ced07a295025f46ae51efa0a61679815c0866c5

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

1. Yongtao Li
2. Xiaodong Zhang
3. Ya-Lei Jin
4. Bian He
5. Bo Ning
6. Binlong Li
7. Dheer Noal Desai
8. Michael Tait

In Discrete Mathematics and Combinatorics

1. Yongtao Li
2. Vladimir Nikiforov
3. Xiaodong Zhang
4. Bian He
5. Ya-Lei Jin
6. Bo Ning
7. Dheer Noal Desai
8. Michael Tait

In Geometry and Topology

1. Yongtao Li
2. Xiaodong Zhang
3. Vladimir Nikiforov
4. Ya-Lei Jin
5. Bian He
6. Bo Ning
7. Dheer Noal Desai
8. Michael Tait

Citations in the corpus

• The spectral radius of graphs without long cycles (2017, unknown): “A survey about the subject can be found in [4].”
• Merging the A- and Q-spectral theories (2016, background): “, the second part of the survey paper [25].”
• Spectral analogues of Erdős’ and Moon–Moser’s theorems on Hamilton cycles (2015, background): “For a comprehensive survey on this area, we refer the reader to [6] by Nikiforov.”
• Sharp Bounds for the Signless Laplacian Spectral Radius in Terms of Clique Number (2012, background): “For instance, he determined [13] the maximum spectral radius of graphs without paths of given length and presented [15] a comprehensive survey on these topics.”
• Spectral extremal graphs for intersecting cliques (2021, background): “In addition, Fiedler and Nikiforov [16] obtained tight sufficient conditions for graphs to be Hamiltonian or traceable.”