On the number of list‐colorings

Given a list of boxes L for a graph G (each vertex is assigned a finite set of colors that we call a box), we denote by f ( G, L ) the number of L‐ colorings of G (each vertex must be colored wiht a color of its box). In the case where all the boxes are identical and of size k , f (G, L) = p ( G, k ), where P = G , k) is the chromatic polynominal of G . We denote by F ( G, k ) the minimum of f ( G, L ) over all the lists of boxes such that each box has size at least k . It is clear that F ( G , k ) ≤ P ( G, k ) for all G, k , and we will see in the introduction some examples of graphs such that F ( G , k ) < P ( G , k ) for some k . However, we will show, in answer to a problem proposed by A. Kostochka and A. Sidorenko (Fourth Czechoslovak Symposium on Combinatorics, Prachatice, Jin, 1990), that for all G , F ( G , k ) = P ( G , k ) for all k sufficiently large. It will follow in particular that F ( G , k ) is not given by a polynominal in k for all G . The proof is based on the analysis of an algorithm for computing f ( G, L ) analogous to the classical one for computing P ( G , k ).