Approximating the chromatic polynomial is as hard as computing it exactly

Ferenc Bencs, Jeroen Huijben, Guus Regts

We show that for any non-real algebraic number $q$ such that $|q-1|>1$ or $\Re (q)>\frac{3}{2}$ it is \textsc{\#P}-hard to compute a multiplicative (resp. additive) approximation to…