Counting homomorphisms to K4-minor-free graphs, modulo 2 - Focke, J; Goldberg, LA; Roth, M; Zivny, S (Society for Industrial and Applied Mathematics, 2021)
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.