| Abstract: | 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). |
