Editing Graph coloring (section)

=== Contraction ===
The  [[contraction (graph theory)|contraction]] <math>G/uv</math> of a graph ''G'' is the graph obtained by identifying the vertices ''u'' and ''v'', and removing any edges between them. The remaining edges originally incident to ''u'' or ''v'' are now incident to their identification (''i.e.'', the new fused node ''uv''). This operation plays a major role in the analysis of graph coloring.

The chromatic number satisfies the [[recurrence relation]]:
: <math>\chi(G) = \text{min} \{  \chi(G+uv), \chi(G/uv)\}</math>
due to {{harvtxt|Zykov|1949}}, where ''u'' and ''v'' are non-adjacent vertices, and <math>G+uv</math> is the graph with the edge {{mvar|uv}} added. Several algorithms are based on evaluating this recurrence and the resulting computation tree is sometimes called a Zykov tree. The running time is based on a heuristic for choosing the vertices ''u'' and ''v''.

The chromatic polynomial satisfies the following recurrence relation
: <math>P(G-uv, k)= P(G/uv, k)+ P(G, k)</math>
where ''u'' and ''v'' are adjacent vertices, and <math>G-uv</math> is the graph with the edge {{mvar|uv}} removed. <math>P(G - uv, k)</math> represents the number of possible proper colorings of the graph, where the vertices may have the same or different colors. Then the proper colorings arise from two different graphs. To explain, if the vertices ''u'' and ''v'' have different colors, then we might as well consider a graph where ''u'' and ''v'' are adjacent. If ''u'' and ''v'' have the same colors, we might as well consider a graph where ''u'' and ''v'' are contracted. Tutte's curiosity about which other graph properties satisfied this recurrence led him to discover a bivariate generalization of the chromatic polynomial, the [[Tutte polynomial]].

These expressions give rise to a recursive procedure called the ''deletion–contraction algorithm'', which forms the basis of many algorithms for graph coloring. The running time satisfies the same recurrence relation as the [[Fibonacci numbers]], so in the worst case the algorithm runs in time within a polynomial factor  of <math>\left(\tfrac{1+\sqrt{5}}2\right)^{n+m}=O(1.6180^{n+m})</math> for ''n'' vertices and ''m'' edges.{{sfnp|Wilf|1986}} The analysis can be improved to within a polynomial factor of the number <math>t(G)</math> of [[spanning tree (mathematics)|spanning trees]] of the input graph.{{sfnp|Sekine|Imai|Tani|1995}} In practice, [[branch and bound]] strategies and [[isomorphism|graph isomorphism]] rejection are employed to avoid some recursive calls. The running time depends on the heuristic used to pick the vertex pair.