LIST T-COLORINGS OF GRAPHS

A T-coloring of a graph G is a coloring (with positive integers) of V(G) such that the absolute value of the difference between any two colors assigned to adjacent vertices does not belong to a set T of nonnegative integers. Given a set T and an integer k, a graph G is T-k-choosable if, for every assignment of (possibly different) lists of k integers to the vertices of G, there exists a T-coloring of G coloring each vertex with an element from the list assigned to that vertex. Exact values and bounds on the smallest k needed to be T-k-choosable are presented for various classes of graphs and T-sets. T-k-choosability has applications in radio and television frequency assignment.