7 citations · 7 across the 5 of their papers we have counts for
Showing 2020Show all
3 papers · 1 filter
cs.CC2020
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…
cs.CC2020
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…
cs.CC2020
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 ,…