Extremal graph theory


Extremal graph theory

Extremal graph theory is a branch of mathematics.

In the narrow sense, extremal graph theory studies the graphs which are "extremal" among graphs with a certain property. There are various meanings for the word "extremal": with the largest number of edges, the largest minimum degree, the smallest diameter, etc. In a broader sense, various other related questions can be included into extremal graph theory. In that case, the term extremal graph theory can encompass a large part of graph theory.

A typical result in extremal graph theory is Turán's theorem. It answers the following question. What is the maximum possible number of edges in an undirected graph "G" with "n" vertices which does not contain "K""3" (three vertices "A", "B", "C" with edges "AB", "AC", "BC"; i.e. a triangle) as a subgraph? The bipartite graph where the partite sets differ in their size by at most 1, is the only extremal graph with this property. It contains: leftlfloor frac{n^2}{4} ight floor edges. Similar questions have been studied with various other subgraphs "H" instead of "K""3"; for instance, the Zarankiewicz problem concerns the largest graph that does not contain a fixed complete bipartite graph as a subgraph. Turán also found the (unique) largest graph not containing "K""k" which is named after him, namely Turán graph. This graph has : leftlfloor frac{(k-2) n^2}{2(k-1)} ight floor = leftlfloor left( 1- frac{1}{k-1} ight) frac{n^2}{2} ight floor edges. For "C""4", the largest graph on "n" vertices not containing "C""4" has : left(frac{1}{2}+o(1) ight) n^{3/2} edges.

ee also

*Ramsey's theorem

References

# Béla Bollobás. "Extremal Graph Theory". New York: Academic Press, 1978.
# Béla Bollobás. "Modern Graph Theory", chapter 4: Extremal Problems. New York: Springer, 1998.
#
# M. Simonovits, Slides from the Chorin summer school lectures, 2006. [http://www.renyi.hu/~miki/BerlinG.pdf]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Graph theory — In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and …   Wikipedia

  • Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… …   Wikipedia

  • Clique (graph theory) — A graph with 23 1 vertex cliques (its vertices), 42 2 vertex cliques (its edges), 19 3 vertex cliques (the light blue triangles), and 2 4 vertex cliques (dark blue). Six of the edges and 11 of the triangles form maximal cliques. The two dark blue …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Extremal length — In the mathematical theory of conformal and quasiconformal mappings, the extremal length of a collection of curves Gamma is a conformal invariant of Gamma. More specifically, suppose thatD is an open set in the complex plane and Gamma is a… …   Wikipedia

  • Turán graph — The Turán graph T(13,4) Named after Pál Turán v · …   Wikipedia

  • Triangle-free graph — In the mathematical area of graph theory, a triangle free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4,… …   Wikipedia

  • Uniquely colorable graph — In graph theory, a uniquely colorable graph is a k chromatic graph that has only one possible (proper) k coloring up to permutation of the colors. Example 1 . A minimal imperfect graph is a graph in which every subgraph is perfect. The deletion… …   Wikipedia

  • Ramanujan graph — A Ramanujan graph, named after Srinivasa Ramanujan, is a regular graph whose spectral gap is almost as large as possible (see extremal graph theory). Such graphs are excellent spectral expanders.Examples of Ramanujan graphs include the clique,… …   Wikipedia

  • Grötzsch graph — infobox graph name = Grötzsch graph namesake = Herbert Grötzsch vertices = 11 edges = 20 chromatic number = 4 chromatic index = girth = 4 properties = The Grötzsch graph is a triangle free graph with 11 vertices, 20 edges, and chromatic number 4 …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.