graphs. 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. 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 on a graph with n vertices and m edges. The analysis can be improved to within a polynomial factor of the number of spanning trees of the input graph. In practice, branch and bound strategies and graph isomorphism rejection are employed to avoid some recursive calls, the running time depends on the heuristic used to pick the vertex pair. Cube method There is a natural geometric perspective on graph colorings by observing that, as an assignment of natural numbers to each vertex, a graph coloring is a vector in the integer lattice. Since two vertices and being given the same color is equivalent to the ’th and ’th coordinate in the coloring vector being equal, each edge can be associated with a hyperplane of the form . The collection of such hyperplanes for a given graph is called its graphic arrangement. The proper colorings of a graph are those lattice points which avoid forbidden hyperplanes. Restricting to a set of colors, the lattice points are contained in the cube . In this context the chromatic polynomial counts the number of lattice points in the -cube that avoid the graphic arrangement. Computational complexity The problem of computing the number of 3-colorings of a given graph is a canonical example of a #P-complete problem, so the problem of computing the coefficients of the chromatic polynomial is #P-hard. Similarly, evaluating for given G is #P-complete. On the other hand, for it is easy to compute , so the corresponding problems are polynomial-time computable. For integers the problem is #P-hard, which is established similar to the case . In fact, it is known that is #P-hard for all x (including negative integers and