5 papers
The Complexity of Counting Edge Colorings for Simple Graphs
Jin-Yi Cai, Artem Govorov
We prove #P-completeness results for counting edge colorings on simple graphs. These strengthen the corresponding results on multigraphs from [4]. We prove that for any $κ\ge r \ge…
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
Jin-Yi Cai, Artem Govorov
The complexity of graph homomorphisms has been a subject of intense study [11, 12, 4, 42, 21, 17, 6, 20]. The partition function of graph homomorphism is def…
A dichotomy for bounded degree graph homomorphisms with nonnegative weights
Artem Govorov, Jin-Yi Cai, Martin Dyer
We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix . Each symmetric matrix defines a graph homomorphism function ,…
On a Theorem of Lovász that Determines the Isomorphism Type of
Jin-Yi Cai, Artem Govorov
Graph homomorphism has been an important research topic since its introduction [17]. Stated in the language of binary relational structures in that paper [17], Lovász proved a fund…
Perfect Matchings, Rank of Connection Tensors and Graph Homomorphisms
Jin-Yi Cai, Artem Govorov
We develop a theory of graph algebras over general fields. This is modeled after the theory developed by Freedman, Lovász and Schrijver in [22] for connection matrices, in the stud…