- Extremal graph theory
Extremal graph theory is a branch of
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
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 bipartitegraph where the partite sets differ in their size by at most 1, is the only extremal graph with this property. It contains: edges. Similar questions have been studied with various other subgraphs "H" instead of "K""3"; for instance, the Zarankiewicz problemconcerns the largest graph that does not contain a fixed complete bipartite graphas a subgraph. Turánalso found the (unique) largest graph not containing "K""k" which is named after him, namely Turán graph. This graph has : edges. For "C""4", the largest graph on "n" vertices not containing "C""4" has : edges.
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