Abstract :
Given a set T of nonnegative integers, a T-coloring of a graph G is a labeling of the vertices of G with positive integers such that no pair of adjacent vertices is labeled with integers differing by a number in T. Let TG(λ) denote the number of ways to T-color G with numbers from the set {1, 2,…,λ}. We show that there is a polynomial, QG(λ), such that QG(λ) = TG(λ) provided that λ is big enough.
