The chromatic number of a graph 
is the smallest number of colors needed to color the vertices
of 
so that no two adjacent vertices share the same color
(Harary and Palmer 1973, p. 269; Skiena 1990, p. 210), i.e., the smallest
value of 
possible to obtain a k-coloring. Minimal colorings
and chromatic numbers for a sample of graphs are illustrated
above.
The chromatic number of a graph 
is most commonly denoted 
(e.g., Skiena 1990, West 2000, Godsil and Royle 2001,
Pemmaraju and Skiena 2003), but occasionally also 
.
Empty graphs have chromatic number 1, while non-empty bipartite graphs have chromatic number 2.
The chromatic number of a graph 
is also the smallest positive
integer 
for which the chromatic polynomial 
. The optimization problem of finding a minimum
vertex coloring, and hence calculating the chromatic number, is the vertex
coloring problem.
Computation of the chromatic number of a graph is implemented in the Wolfram Language as VertexChromaticNumber[g]. Precomputed chromatic numbers for many named graphs can be obtained using GraphData[graph, "ChromaticNumber"].
The chromatic number of a graph must be greater than or equal to its clique number. A graph
is called a perfect graph if, for each of its induced subgraphs 
, the chromatic number of 
equals the largest number of pairwise adjacent vertices
in 
.
A graph for which the clique
number is equal to the chromatic number (with no further restrictions on induced
subgraphs) is said to be weakly perfect.
By definition, the edge chromatic number of a graph 
equals the chromatic number of the line
graph 
.
Brooks' theorem states that the chromatic number of a graph is at most the maximum
vertex degree 
,
unless the graph is complete
or an odd cycle, in which case 
colors are required.
A graph with chromatic number 
is said to be bicolorable,
and a graph with chromatic number 
is said to be three-colorable.
In general, a graph with chromatic number 
is said to be an k-chromatic
graph, and a graph with chromatic number 
is said to be k-colorable.
The following table gives the chromatic numbers for some named classes of graphs.
, 
, 
, 
For any two positive integers 
and 
, there exists a graph of girth
at least 
and chromatic number at least 
(Erdős 1961; Lovász 1968; Skiena 1990, p. 215).
The chromatic number of a surface of genus 
is given by the Heawood
conjecture,
 |
where 
is the floor function. 
is sometimes also denoted 
(which is unfortunate, since 
commonly refers to the Euler
characteristic). For 
, 1, ..., the first few values of 
are 4, 7, 8, 9, 10, 11, 12, 12, 13, 13, 14, 15, 15, 16,
... (OEIS A000934).
Erdős (1959) proved that there are graphs with arbitrarily large girth and chromatic number (Bollobás and West 2000).
