We study the problem of computing the parity of the number of homomorphisms
from an input graph *G* to a fixed graph *H*. Faben and Jerrum [ToC’15]
introduced an explicit criterion on the graph *H* and conjectured that, if
satisfied, the problem is solvable in polynomial time and, otherwise, the
problem is complete for the complexity class ⊕P of parity
problems.

We verify their conjecture for all graphs *H* that exclude the complete graph
on 4 vertices as a minor. Further, we rule out the existence of a
subexponential-time algorithm for the ⊕P-complete cases,
assuming the randomised Exponential Time Hypothesis.

Our proofs introduce a novel method of deriving hardness from globally defined
substructures of the fixed graph *H*. Using this, we subsume all prior progress
towards resolving the conjecture (Faben and Jerrum [ToC’15]; Göbel, Goldberg
and Richerby [ToCT’14, ‘16]). As special cases, our machinery also yields a
proof of the conjecture for graphs with maximum degree at most 3, as well as a
full classification for the problem of counting list homomorphisms, modulo 2.