Graph Coloring with Distance Constraints

Given an undirected graph G=(V,E), a constant sigma <= 1, and sigma non-negative values d1, d2, ... , dsigma, the L(d1, d2, ... , dsigma)-coloring problem is defined as follows: find a node coloring f:V --> C such that | f(u) - f(v) | <= di if nodes u and v have distance i in G, where C= {0, 1, ... lf } is a set of colors and 1 <= i <= sigma. The optimization problem consists in minimizing the value lf over all functions f. This problem has been proved to be NP-hard even in its simplest versions, and research has focused on finding optimal or approximate solutions on restricted classes of graphs for special values of sigma and di. In this paper we consider different cases of the L(d1, d2, ... , dsigma)-coloring problem arising in different fields, such as frequency assignment in wireless networks, data distribution in multiprocessor parallel memory systems, and scalability of optical networks. After defining the values of \sigma and di for these specific cases, we survey the results known in the literature with respect to grids, trees, hypercubes, and planar graphs, and we point out some interrelationships between apparently different distance constraints.