Abstract
H-colourings of a graph G (a.k.a. homomorphisms from G to H) generalise familiar proper vertex colourings of G. More than 15 years ago, Dyer and Greenhill presented a dichotomy for exactly counting H-colourings. That was for exact counting, and, even now, there is only a partial complexity classification for approximate counting. A familiar theme in the study of CSPs is that the “conservative” case is often easier to resolve. This is one reason to look at list H-colourings. The decision problem for list H-colourings was studied by Feder, Hell and Huang, who proved a dichotomy result. In this talk, I’ll present a classification for the problem of approximately counting list H-colourings of a graph, and briefly consider weighted variants.
This is joint work with Andreas Galanis and Leslie Ann Goldberg (Oxford), and others.