7 citations · 7 across the 5 of their papers we have counts for
6 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…
A new example of a generic 2-distribution on a 5-manifold with large symmetry algebra
Boris Doubrov, Artem Govorov
We discover a new example of a generic rank 2-distribution on a 5-manifold with a 6-dimensional transitive symmetry algebra, which is not present in Cartan's classical five variabl…