A Complexity Trichotomy for Approximately Counting List H -Colorings

DOI10.1145/3037381zbMath1427.68121OpenAlexW2963938859MaRDI QIDQ4973886

Leslie Ann Goldberg, Andreas Galanis, Mark R. Jerrum

Publication date: 6 December 2019

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3037381

zbMATH Keywords

graph homomorphismsapproximate countinglist colorings

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)

Related Items (4)

Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

This page was built for publication: A Complexity Trichotomy for Approximately Counting List H -Colorings