Graph Coloring with Distance Constraints

Given an undirected graph G - (V,E), a constant a > 1, and a non-negative values 61,62, ··· ,6 a, the L(6\, 62, ..., 6 a)-coloring problem is defined as follows: find a node coloring f: V-»C such that \f(u) - f{v)\ > 6i if nodes u and v have distance i in G, where C = {0,1,... A/} is a set of colors and 1 < i < a. The op- timization problem consists in minimizing the value Xf 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 a and Jj. In this paper we consider different cases of the L(6i, 62,..., <5 CT)- coloring problem arising in different fields, such as fre- quency assignment in wireless networks, data distribution in multiprocessor parallel memory systems, and scalability of optical networks. After defining the values of a and 6jfor these specific cases, we survey the results known in the lit- erature with respect to grids, trees, hypercubes, and planar graphs, and we point out some interrelationships between apparently different distance constraints.