  Given a graph G, we investigate the question 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 parityP-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.
