Editing Chromatic polynomial (section)

==Definition==
[[File:Chromatic polynomial of all 3-vertex graphs BW with colorings.png|thumb|300px|right|All proper vertex colorings of vertex graphs with 3 vertices using ''k'' colors for <math>k=0,1,2,3</math>. The chromatic polynomial of each graph interpolates through the number of proper colorings.]]

For a graph ''G'', <math>P(G,k)</math> counts the number of its (proper) [[vertex coloring|vertex ''k''-colorings]]. 
Other commonly used notations include <math>P_G(k)</math>, <math>\chi_G(k)</math>, or <math>\pi_G(k)</math>.
There is a unique [[polynomial]] <math>P(G,x)</math> which evaluated at any integer ''k'' ≥ 0 coincides with <math>P(G,k)</math>; it is called the '''chromatic polynomial''' of ''G''.

For example, to color the [[path graph]] <math>P_3</math> on 3 vertices with ''k'' colors, one may choose any of the ''k'' colors for the first vertex, any of the <math>k - 1</math> remaining colors for the second vertex, and lastly for the third vertex, any of the <math>k - 1</math> colors that are different from the second vertex's choice.
Therefore, <math>P(P_3,k) = k \cdot (k-1) \cdot (k-1)</math> is the number of ''k''-colorings of <math>P_3</math>.
For a variable ''x'' (not necessarily integer), we thus have <math>P(P_3,x)=x(x-1)^2=x^3-2x^2+x</math>.
(Colorings which differ only by permuting colors or by [[graph automorphism|automorphisms]] of ''G'' are still counted as different.)

===Deletion–contraction===
{{Main|Deletion–contraction formula}}
The fact that the number of ''k''-colorings is a polynomial in ''k'' follows from a recurrence relation called the '''[[Deletion–contraction formula|deletion–contraction recurrence]]''' or '''Fundamental Reduction Theorem'''.<ref>{{harvtxt|Dong|Koh|Teo|2005}}</ref> It is based on [[edge contraction]]: for a  pair of vertices <math>u</math> and <math>v</math> the graph <math>G/uv</math> is obtained by merging the two vertices and removing any edges between them. 
If <math>u</math> and <math>v</math> are adjacent in ''G'', let <math>G-uv</math> denote the graph obtained by removing the edge <math>uv</math>.
Then the numbers of ''k''-colorings of these graphs satisfy:
:<math>P(G,k)=P(G-uv, k)- P(G/uv,k)</math>
Equivalently, if <math>u</math> and <math>v</math> are not adjacent in ''G'' and <math>G+uv</math> is the graph with the edge <math>uv</math> added, then
:<math>P(G,k)= P(G+uv, k) + P(G/uv,k)</math>
This follows from the observation that every ''k''-coloring of ''G'' either gives different colors to <math>u</math> and <math>v</math>, or the same colors. In the first case this gives a (proper) ''k''-coloring of <math>G+uv</math>, while in the second case it gives a coloring of <math>G/uv</math>.
Conversely, every ''k''-coloring of ''G'' can be uniquely obtained from a ''k''-coloring of <math>G+uv</math> or <math>G/uv</math> (if <math>u</math> and <math>v</math> are not adjacent in ''G'').

The chromatic polynomial can hence be recursively defined as 
:<math>P(G,x)=x^n</math> for the edgeless graph on ''n'' vertices, and 
:<math>P(G,x)=P(G-uv, x)- P(G/uv,x)</math> for a graph ''G'' with an edge <math>uv</math> (arbitrarily chosen).
Since the number of ''k''-colorings of the edgeless graph is indeed <math>k^n</math>, it follows by induction on the number of edges that for all ''G'', the polynomial <math>P(G,x)</math> coincides with the number of ''k''-colorings at every integer point ''x''&nbsp;=&nbsp;''k''. In particular, the chromatic polynomial is the unique [[interpolating polynomial]] of degree at most ''n'' through the points
:<math>\left \{ (0, P(G, 0)), (1, P(G, 1)), \ldots, (n, P(G, n)) \right \}.</math>

[[Tutte]]’s curiosity about which other [[graph invariant]]s satisfied such recurrences led him to discover a bivariate generalization of the chromatic polynomial, the [[Tutte polynomial]] <math>T_G(x,y)</math>.