The Computational Complexity of Counting List H-Colourings, and Related Problems
summary
Gives a concrete trichotomy for approximating list H‑colourings: if every component of H is trivial it is in FP; if H is an irreflexive bipartite permutation graph or a reflexive proper interval graph the problem is AP‑equivalent to counting independent sets in bipartite graphs (BIS); otherwise the problem is #SAT‑hard. Proofs use hereditary/excluded‑subgraph characterizations, staircase biadjacency matrices, small gadget encodings of the antiferromagnetic Ising model, and degree‑bounded (∆≤6) hardness.
AI-written summary · about