Approximately counting H-colourings is BIS-Hard
We consider counting <em>H</em>-colourings from an input graph G to a target graph <em>H</em>. We show that for any fixed graph <em>H</em> without trivial components, this is as hard as the well-known problem #BIS, the problem of (approximately) counting independe...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Sprog: | English |
| Udgivet: |
2015
|