vertex degree at most three, save for the point , which counts nowhere-zero Z3-flows and is computable in polynomial time. These results contain several notable special cases. For example, the problem of computing the partition function of the Ising model is #P-hard in general, even though celebrated algorithms of Onsager and Fisher solve it for planar lattices. Also, the Jones polynomial is #P-hard to compute. Finally, computing the number of four-colorings of a planar graph is #P-complete, even though the decision problem is trivial by the four color theorem. In contrast, it is easy to see that counting the number of three-colorings for planar graphs is #P-complete because the decision problem is known to be NP-complete via a parsimonious reduction. Approximation The question which points admit a good approximation algorithm has been very well studied. Apart from the points that can be computed exactly in polynomial time, the only approximation algorithm known for is Jerrum and Sinclair’s FPRAS, which works for points on the “Ising” hyperbola for y > 0. If the input graphs are restricted to dense instances, with degree , there is an FPRAS if x ≥ 1, y ≥ 1. Even though the situation is not as well understood as for exact computation, large areas of the plane are known to be hard to approximate. See also Bollobás–Riordan polynomial A Tutte–Grothendieck invariant is any evaluation of the Tutte polynomial Notes References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . External links PlanetMath Chromatic polynomial Steven R. Pagano: Matroids and Signed Graphs Sandra Kingan: Matroid theory. Many links. Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: Computational problems Duality theories Matroid theory Polynomials Graph invariants