Editing Chromatic polynomial (section)

===Computational complexity===
The problem of computing the number of 3-colorings of a given graph is a canonical example of a [[Sharp-P|#P]]-complete problem, so the problem of computing the coefficients of the chromatic polynomial is #P-hard. Similarly, evaluating <math>P(G, 3)</math> for given ''G'' is #P-complete. On the other hand, for <math>k=0,1,2</math> it is easy to compute <math>P(G, k)</math>, so the corresponding problems are polynomial-time computable. For integers <math>k>3</math> the problem is #P-hard, which is established similar to the case <math>k=3</math>. In fact, it is known that <math>P(G, x)</math> is #P-hard for all ''x'' (including negative integers and even all [[complex number]]s) except for the three “easy points”.<ref>{{harvtxt|Jaeger|Vertigan|Welsh|1990}}, based on a reduction in {{harv|Linial|1986}}.</ref> Thus, from the perspective of #P-hardness, the complexity of computing the chromatic polynomial is completely understood.

In the expansion

:<math>P(G, x)= a_1 x + a_2x^2+\cdots +a_nx^n,</math>

the coefficient <math>a_n</math> 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 ''a<sub>r</sub>'' for a fixed ''r ≥ 1'' and a given graph ''G'' is #P-hard, even for bipartite planar graphs.<ref>{{harvtxt|Oxley|Welsh|2002}}</ref>

No [[approximation algorithms]] for computing <math>P(G, x)</math> are known for any ''x'' except for the three easy points. At the integer points <math>k=3,4,\ldots</math>, 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&nbsp;=&nbsp;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 [[FPRAS|fully polynomial time randomised approximation scheme (FPRAS)]]. There is no [[FPRAS]] for computing <math>P(G, x)</math> for any ''x'' > 2, unless [[NP (complexity class)|NP]]&nbsp;=&nbsp;[[RP (complexity class)|RP]] holds.<ref>{{harvtxt|Goldberg|Jerrum|2008}}</ref>