Editing Chromatic polynomial (section)

===Deletion–contraction===
The [[deletion-contraction recurrence]] gives a way of computing the chromatic polynomial, called the ''deletion–contraction algorithm''. In the first form (with a minus), the recurrence terminates in a collection of empty graphs. In the second form (with a plus), it terminates in a collection of complete graphs. 
This forms the basis of many algorithms for graph coloring. The ChromaticPolynomial function in the Combinatorica package of the computer algebra system [[Mathematica]] uses the second recurrence if the graph is dense, and the first recurrence if the graph is sparse.<ref>{{harvtxt|Pemmaraju|Skiena|2003}}</ref> The worst case running time of either formula 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>\varphi^{n+m}=\left (\frac{1+\sqrt{5}}{2} \right)^{n+m}\in O\left(1.62^{n+m}\right),</math>

on a graph with ''n'' vertices and ''m'' edges.<ref>{{harvtxt|Wilf|1986}}</ref> 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.<ref>{{harvtxt|Sekine|Imai|Tani|1995}}</ref> 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.