text: We introduce and explore a family of vertex-coloring problems, which, surprisingly enough, have not been considered before despite stemming from the problem of Wi-Fi channel assignment. Given a spectrum of colors, endowed with a matrix of interferences between each pair of colors, the Threshold Spectrum Coloring problem fixes the number of colors available and aims to minimize the interference threshold, i.e., the maximum of the interferences at the vertices. Conversely, the Chromatic Spectrum Coloring problem fixes a threshold and aims to minimize the number of colors for which respecting that threshold is possible. As the main theoretical results, we prove tight upper bounds for the solutions to each problem. Since both problems turn out to be NP-hard, we complete the scene with experimental results. We propose a DSATUR-based heuristic and study its performance to minimize the maximum vertex interference in Wi-Fi channel assignment, both for randomly-generated graphs and for a real-world scenario. Further, for all these graphs, we experimentally check the goodness of the theoretical bounds.
  @cite_1: This work establishes the complexity class of several instances of the S -packing coloring problem: for a graph G , a positive integer k and a nondecreasing list of integers S = ( s 1 , ? , s k ) , G is S -colorable if its vertices can be partitioned into sets S i , i = 1 , ? , k , where each S i is an s i -packing (a set of vertices at pairwise distance greater than s i ). In particular we prove a dichotomy between NP-complete problems and polynomial-time solvable problems for lists of at most four integers.
  @cite_4: Abstract 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 ƒ( x ) to each vertex x of G so that if x and y are joined by an edge of G , then |ƒ(x) - ƒ(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, ƒ( 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 ƒ( 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.
  @cite_2: This paper surveys the most important algorithmic and computational results on the Vertex Coloring Problem (VCP) and its generalizations. The first part of the paper introduces the classical models for the VCP, and discusses how these models can be used and possibly strengthened to derive exact and heuristic algorithms for the problem. Computational results on the best performing algorithms proposed in the literature are reported. The second part of the paper is devoted to some generalizations of the problem, which are obtained by considering additional constraints [Bandwidth (Multi) Coloring Problem, Bounded Vertex Coloring Problem] or an objective function with a special structure (Weighted Vertex Coloring Problem). The extension of the models for the classical VCP to the considered problems and the best performing algorithms from the literature, as well as the corresponding computational results, are reported.
summary: For a different setting, in a @cite_2 a distance @math is associated to each particular edge @math , forcing its endpoints to get colors @math apart. A similar flavor has the @cite_4 , where adjacent vertices must get colors whose distance is not in a prescribed set @math , and the @cite_1 , where the vertices have to be partitioned into sets with prescribed pairwise distances.