even all complex numbers) except for the three “easy points”. Thus, from the perspective of #P-hardness, the complexity of computing the chromatic polynomial is completely understood. In the expansion the coefficient is always equal to 1, and several other properties of the coefficients are known. This raises the question if some of the coefficients are easy to compute. However the computational problem of computing ar for a fixed r ≥ 1 and a given graph G is #P-hard, even for bipartite planar graphs. No approximation algorithms for computing are known for any x except for the three easy points. At the integer points , the corresponding decision problem of deciding if a given graph can be k-colored is NP-hard. Such problems cannot be approximated to any multiplicative factor by a bounded-error probabilistic algorithm unless NP = RP, because any multiplicative approximation would distinguish the values 0 and 1, effectively solving the decision version in bounded-error probabilistic polynomial time. In particular, under the same assumption, this rules out the possibility of a fully polynomial time randomised approximation scheme (FPRAS). For other points, more complicated arguments are needed, and the question is the focus of active research. , it is known that there is no FPRAS for computing for any x > 2, unless NP = RP holds. Notes References . External links PlanetMath Chromatic polynomial Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: Graph invariants Graph coloring