Counting $k$-Colorings $\mathcal{O}(\phi^{n + m})$ Solution
Use an adjacency list representation, together with a Union-Find data structure on the vertices.  Augment the Union-Find data structure so you can quickly enumerate the list of all edges incident on any vertex within a particular partition (you can keep track of them with a doubly linked list, and splice the lists together whenever you do a Union operation).  Now edge contraction can be done in $O(\alpha(n))$ time, by simply doing a Union operation on the two vertices.  Edge removal can be done in $O(1)$ time, due to the adjacency list representation.  You can also find an arbitrary edge in $O(1)$ time, thanks to the augmentation of the Union-Find data structure.

This avoids the factor of $n$.  You still pay a factor of $O(\alpha(n))$ instead of $O(1)$, but $O(\alpha(n))$ is so small that it might as well be $O(1)$ for all practical purposes, and in any case it is far smaller than $n$.

Actually, I think you pay more than that, because you'll need to undo the Union operations after returning from the recursive call.  To deal with that, you can use a persistent Union-Find data structure.  I'm not familiar with the asymptotic running time for those data structures, but I think given how it is used here it will be pretty close to as efficient as the plain Union-Find.

Usually we don't worry too much about polynomial factors when analyzing exponential-time algorithms, because the polynomial factor is tiny compared to the exponential factor, so a polynomial speedup won't change much in practice.  But here is a case where the polynomial speedup you desired can be achieved.