The Complexity of Counting Planar Graph Homomorphisms of Domain Size 3

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 from all planar graphs G → Z H (G), we completely classify the computational complexity of this problem according to the matrix H. We show that for every H, the problem is either polynomial time computable or #P-hard. The P-time computable cases consist of precisely those that are P-time computable for general graphs (a complete classification is known [25] ) or computable by Valiant's holographic algorithm via matchgates. We also prove several results about planar graph homomorphisms for general domain size q. The proof uses mainly analytic arguments.