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.