Approximating the chromatic polynomial is as hard as computing it exactly

We show that for any non-real algebraic number q, such that | q- 1 | > 1 or ℜ(q)>32 it is #P-hard to computea multiplicative (resp. additive) approximation to the absolutevalue (resp. argument) of the chromatic polynomial evaluated at q on planar graphs. This implies #P-hardness for allnon-real algebraic q on the family of all graphs. We, moreover,prove several hardness results for q, such that | q- 1 | ≤ 1 . 

Our hardness results are obtained by showing that a polynomial timealgorithm for approximately computing the chromaticpolynomial of a planar graph at non-real algebraic q (satisfyingsome properties) leads to a polynomial time algorithm forexactly computing it, which is known to be hard by a resultof Vertigan. Many of our results extend in fact to the more generalpartition function of the random cluster model, a well-knownreparametrization of the Tutte polynomial.