z-logo
Premium
On the number of list‐colorings
Author(s) -
Donner Quentin
Publication year - 1992
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190160307
Subject(s) - combinatorics , mathematics , vertex (graph theory) , graph , chromatic scale , discrete mathematics
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 ).

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here