  We study the problem HomsTo$H$ of counting, modulo 2, the homomorphisms from
an input graph to a fixed undirected graph $H$. A characteristic feature of
modular counting is that cancellations make wider classes of instances
tractable than is the case for exact (non-modular) counting, so subtle
dichotomy theorems can arise. We show the following dichotomy: for any $H$ that
contains no 4-cycles, HomsTo$H$ is either in polynomial time or is $\oplus
P$-complete. This confirms a conjecture of Faben and Jerrum that was previously
only known to hold for trees and for a restricted class of treewidth-2 graphs
called cactus graphs. We confirm the conjecture for a rich class of graphs
including graphs of unbounded treewidth. In particular, we focus on square-free
graphs, which are graphs without 4-cycles. These graphs arise frequently in
combinatorics, for example in connection with the strong perfect graph theorem
and in certain graph algorithms. Previous dichotomy theorems required the graph
to be tree-like so that tree-like decompositions could be exploited in the
proof. We prove the conjecture for a much richer class of graphs by adopting a
much more general approach.
