The complexity of counting surjective homomorphisms and compactions
A homomorphism from a graph G to a graph H is a function from the vertices of G to the vertices of H that preserves edges. A homomorphism is surjective if it uses all of the vertices of H and it is a compaction if it uses all of the vertices of H and all of the non-loop edges of H. Hell and Neˇsetˇr...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Society for Industrial and Applied Mathematics
2017
|