  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 trivially in
polynomial time. Otherwise, if H is an irreflexive bipartite permutation graph
or a reflexive proper interval graph then approximately counting list
H-colourings is equivalent to #BIS, the problem of approximately counting
independent sets in a bipartite graph. This is a well-studied problem which is
believed to be of intermediate complexity -- it is believed that it does not
have an FPRAS, but that it is not as difficult as approximating the most
difficult counting problems in #P. For every other graph H, approximately
counting list H-colourings is complete for #P with respect to
approximation-preserving reductions (so there is no FPRAS unless NP=RP). Two
pleasing features of the trichotomy are (i) it has a natural formulation in
terms of hereditary graph classes, and (ii) the proof is largely self-contained
and does not require any universal algebra (unlike similar dichotomies in the
weighted case). We are able to extend the hardness results to the
bounded-degree setting, showing that all hardness results apply to input graphs
with maximum degree at most 6.
