TOPICS
Search

Extremal Graph Theory

Extremal graph theory studies how the intrinsic structure of graphs ensures certain types of properties (e.g., clique-formation and graph colorings) under appropriate conditions.

A basic quantity is the extremal number ex(n,H), the largest number of edges in an n-vertex simple graph containing no copy of a specified graph H. The possible power-law growth rates of this quantity are the subject of the rational exponents conjecture (Conlon et al. 2026).

See also

Erdős Degeneracy Conjecture, Erdős-Simonovits Compactness Conjecture, Erdős-Stone Theorem, Extremal Graph, Extremal Number, Ramsey Theory, Rational Exponents Conjecture, Simonovits Product Conjecture, Structural Ramsey Theory, Szemerédi's Regularity Lemma, Turán Graph, Turán's Theorem

Explore with Wolfram|Alpha

WolframAlpha

More things to try:

References

Bollobás, B. Extremal Graph Theory. New York: Academic Press, 1978.Bollobás, B. Extremal Graph Theory with Emphasis on Probabilistic Methods. Providence, RI: Amer. Math. Soc., 1986.Conlon, D.; Janzer, O.; Jiang, T.; Kim, J.; Lee, J.; Liu, H.; Longbrake, S.; and Yepremyan, L. "A Proof of the Rational Exponents Conjecture." 13 Oct 2026. https://arxiv.org/abs/2610.18713.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 143, 1990.

Referenced on Wolfram|Alpha

Extremal Graph Theory

Cite this as:

Weisstein, Eric W. "Extremal Graph Theory." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/ExtremalGraphTheory.html

Subject classifications