  Given graphs $H$ and $G$, possibly with vertex-colors, a homomorphism is a
function $f:V(H)\to V(G)$ that preserves colors and edges. Many interesting
counting problems (e.g., subgraph and induced subgraph counts) are finite
linear combinations $p(\cdot)=\sum_{H}\alpha_{H}\hom(H,\cdot)$ of homomorphism
counts, and such linear combinations are known to be hard to evaluate iff they
contain a large-treewidth graph $S$. The hardness can be shown in two steps:
First, the problems $\hom(S,\cdot)$ for colorful (i.e., bijectively colored)
large-treewidth graphs $S$ are shown to be hard. In a second step, these
problems are reduced to finite linear combinations of homomorphism counts that
contain the uncolored version $S^{\circ}$ of $S$. This step can be performed
via inclusion-exclusion in $2^{|E(S)|}\mathrm{poly}(n,s)$ time, where $n$ is
the size of the input graph and $s$ is the maximum number of vertices among all
graphs in the linear combination.
  We show that the second step can be performed even in time
$4^{\Delta(S)}\mathrm{poly}(n,s)$, where $\Delta(S)$ is the maximum degree of
$S$. Our reduction is based on graph products with Cai-F\"urer-Immerman graphs,
a novel technique that is likely of independent interest. For colorful graphs
$S$ of constant maximum degree, this technique yields a polynomial-time
reduction from $\hom(S,\cdot)$ to linear combinations of homomorphism counts
involving $S^{\circ}$. Under certain conditions, it actually suffices that a
supergraph $T$ of $S^{\circ}$ is contained in the target linear combination.
  The new reduction yields $\mathsf{\#P}$-hardness results for several counting
problems that could previously be studied only under parameterized complexity
assumptions. This includes the problems of counting, on input a graph from a
restricted graph class and a general graph $G$, the homomorphisms or (induced)
subgraph copies from $H$ in $G$.
