Editing Extremal graph theory (section)

==Topics and concepts==

===Graph coloring===
{{main|Graph coloring}}

[[File:Petersen graph 3-coloring.svg|thumb|right|The [[Petersen graph]] has chromatic number 3.]]

A '''proper (vertex) coloring''' of a graph <math>G</math> is a coloring of the vertices of <math>G</math> such that no two adjacent vertices have the same color. The minimum number of colors needed to properly color <math>G</math> is called the '''chromatic number''' of <math>G</math>, denoted <math>\chi(G)</math>. Determining the chromatic number of specific graphs is a fundamental question in extremal graph theory, because many problems in the area and related areas can be formulated in terms of graph coloring.<ref name="pcm" />

Two simple lower bounds to the chromatic number of a graph <math>G</math> is given by the [[clique number]] <math>\omega(G)</math>—all vertices of a clique must have distinct colors—and by <math>|V(G)|/\alpha(G)</math>, where <math>\alpha(G)</math> is the independence number, because the set of vertices with a given color must form an [[Independent set (graph theory)|independent set]].

A [[greedy coloring]] gives the upper bound <math>\chi(G) \le \Delta(G) + 1</math>, where <math>\Delta(G)</math> is the maximum degree of <math>G</math>. When <math>G</math> is not an odd cycle or a clique, [[Brooks' theorem]] states that the upper bound can be reduced to <math>\Delta(G)</math>. When <math>G</math> is a [[planar graph]], the [[four-color theorem]] states that <math>G</math> has chromatic number at most four.

In general, determining whether a given graph has a coloring with a prescribed number of colors is known to be [[NP-hard]].

In addition to vertex coloring, other types of coloring are also studied, such as [[edge coloring|edge colorings]]. The '''chromatic index''' <math>\chi'(G)</math> of a graph <math>G</math> is the minimum number of colors in a proper edge-coloring of a graph, and [[Vizing's theorem]] states that the chromatic index of a graph <math>G</math> is either <math>\Delta(G)</math> or <math>\Delta(G)+1</math>.

===Forbidden subgraphs===
{{main|Forbidden subgraph problem}}

The '''forbidden subgraph problem''' is one of the central problems in extremal graph theory. Given a graph <math>G</math>, the forbidden subgraph problem asks for the maximal number of edges <math>\operatorname{ex}(n,G)</math> in an <math>n</math>-vertex graph that does not contain a subgraph isomorphic to <math>G</math>. 

When <math>G = K_r</math> is a complete graph, [[Turán's theorem]] gives an exact value for <math>\operatorname{ex}(n,K_r)</math> and characterizes all graphs attaining this maximum; such graphs are known as [[Turán graph|Turán graphs]]. 
For non-bipartite graphs <math>G</math>, the [[Erdős–Stone theorem]] gives an asymptotic value of <math>\operatorname{ex}(n, G)</math> in terms of the chromatic number of <math>G</math>. 
The problem of determining the asymptotics of <math>\operatorname{ex}(n, G)</math> when <math>G</math> is a [[bipartite graph]] is open; when <math>G</math> is a complete bipartite graph, this is known as the [[Zarankiewicz problem]].

===Homomorphism density===
{{main|Homomorphism density}}

The '''homomorphism density''' <math>t(H, G)</math> of a graph <math>H</math> in a graph <math>G</math> describes the probability that a randomly chosen map from the vertex set of <math>H</math> to the vertex set of <math>G</math> is also a [[graph homomorphism]]. It is closely related to the '''subgraph density''', which describes how often a graph <math>H</math> is found as a subgraph of <math>G</math>.

The forbidden subgraph problem can be restated as maximizing the edge density of a graph with <math>G</math>-density zero, and this naturally leads to generalization in the form of '''graph homomorphism inequalities''', which are inequalities relating <math>t(H, G)</math> for various graphs <math>H</math>.
By extending the homomorphism density to [[graphon|'''graphons''']], which are objects that arise as a limit of [[dense graph|dense graphs]], the graph homomorphism density can be written in the form of integrals, and inequalities such as the [[Cauchy-Schwarz inequality]] and [[Hölder's inequality]] can be used to derive homomorphism inequalities.

A major open problem relating homomorphism densities is [[Sidorenko's conjecture]], which states a tight lower bound on the homomorphism density of a bipartite graph in a graph <math>G</math> in terms of the edge density of <math>G</math>.

===Graph regularity===
{{main|Szemerédi regularity lemma}}

[[File:Epsilon regular partition.png|alt=regularity partition|thumb|200x200px|The edges between parts in a regular partition behave in a "random-like" fashion.]]

'''Szemerédi's regularity lemma''' states that all graphs are 'regular' in the following sense: the vertex set of any given graph can be partitioned into a bounded number of parts such that the bipartite graph between most pairs of parts behave like [[random graph|random bipartite graphs]].<ref name="pcm" />
This partition gives a structural approximation to the original graph, which reveals information about the properties of the original graph.

The regularity lemma is a central result in extremal graph theory, and also has numerous applications in the adjacent fields of [[additive combinatorics]] and [[computational complexity theory]]. In addition to (Szemerédi) regularity, closely related notions of graph regularity such as strong regularity and Frieze-Kannan weak regularity have also been studied, as well as extensions of regularity to [[hypergraphs]]. 

Applications of graph regularity often utilize forms of counting lemmas and removal lemmas. In simplest forms, the [[Graph removal lemma#graph counting lemma|graph counting lemma]] uses regularity between pairs of parts in a regular partition to approximate the number of subgraphs, and the [[graph removal lemma]] states that given a graph with few copies of a given subgraph, we can remove a small number of edges to eliminate all copies of the subgraph.

{{-}}