Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
The complexity of graph homomorphisms has been a subject of intense study [1], [2], [3], [4], [5], [6], [7], [8]. The partition function Z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</sub> (·) of graph homomorphism is defined by a symmetric matrix A over C. We prove that the complexity dichotomy of [7] extends to …