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\) $|q-1|>1$ or \(\Re(q)>\frac{3}{2}\) $\Re (q)>\frac{3}{2}$ 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|\leq 1\) $|q-1|\le 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.