A complexity trichotomy for approximately counting list H-colourings

DOI10.4230/LIPIcs.ICALP.2016.46zbMath1388.68113arXiv1602.03985MaRDI QIDQ4598185

Andreas Galanis, Leslie Ann Goldberg, Mark R. Jerrum

Publication date: 19 December 2017

Full work available at URL: https://arxiv.org/abs/1602.03985

zbMATH Keywords

graph homomorphismsapproximate countinglist colourings

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

This page was built for publication: A complexity trichotomy for approximately counting list H-colourings