A complexity trichotomy for approximately counting list H-colourings
We examine the computational complexity of approximately counting the list H-colourings of a graph. We discover a natural graph-theoretic trichotomy based on the structure of the graph H. If H is an irreflexive bipartite graph or a reflexive complete graph then counting list H-colourings is triviall...
| Hlavní autoři: | , , |
|---|---|
| Médium: | Conference item |
| Vydáno: |
Schloss Dagstuhl
2016
|