Theory of Computing
-------------------
Title     : The Complexity of Parity Graph Homomorphism: An Initial Investigation
Authors   : John Faben and Mark Jerrum
Volume    : 11
Number    : 2
Pages     : 35-57
URL       : https://theoryofcomputing.org/articles/v011a002

Abstract
--------

Given a graph  G, we investigate the problem of determining the
parity of the number of homomorphisms from  G  to some other fixed
graph  H. We conjecture that this problem exhibits a complexity
dichotomy, such that all parity graph homomorphism problems are either
polynomial-time solvable or  (+)P--complete, and provide a
conjectured characterisation of the easy cases.

We show that the conjecture is true for the restricted case in which
the graph  H  is a tree, and provide some tools that may be useful in
further investigation into the parity graph homomorphism problem, and
the problem of counting homomorphisms for other moduli.