T-COLORINGS OF GRAPHS - RECENT RESULTS AND OPEN PROBLEMS

Suppose G is a graph and T is a set of nonnegative integers. A T-coloring of G is an assignment of a positive integer f(x) to each vertex x of G so that if x and y are joined by an edge of G, then \f(x) - f(y)\ is not in T. T-colorings were introduced by Hale in connection with the channel assignment problem in communications. Here, the vertices of G are transmitters, an edge represents interference, f(x) is a television or radio channel assigned to x, and T is a set of disallowed separations for channels assigned to interfering transmitters. One seeks to find a T-coloring which minimizes either the number of different channels f(x) used or the distance between the smallest and largest channel. This paper surveys the results and mentions open problems concerned with T-colorings and their variations and generalizations.