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_5: Wireless communication is used in many different situations such as mobile telephony, radio and TV broadcasting, satellite communication, wireless LANs, and military operations. In each of these situations a frequency assignment problem arises with application specific characteristics. Researchers have developed different modeling ideas for each of the features of the problem, such as the handling of interference among radio signals, the availability of frequencies, and the optimization criterion.
summary: Of independent interest are the works on the Frequency Assignment Problem, which use different models to fit the characteristics of specific applications. The bibliography about this problem is too extensive to include here even a selection. Instead, we prefer referring the reader to the comprehensive survey by @cite_5 .