The complexity of counting planar graph homomorphisms of domain size 3

Jin-Yi Cai, Ashwin Maran

We prove a complexity dichotomy theorem for counting planar graph homomorphisms of domain size 3. Given any 3 by 3 real valued symmetric matrix $H$ defining a graph homomorphism fr…