Editing Extremal graph theory (section)

===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>.