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...
| Asıl Yazarlar: | , , |
|---|---|
| Materyal Türü: | Conference item |
| Baskı/Yayın Bilgisi: |
Schloss Dagstuhl
2016
|