Bounds for the frequency assignment problem (Q1356496)

The problem of assigning radio frequencies to a set of transmitters is related to the theory of vertex colourings of graphs. Let \(F=\{0,1,\ldots,K\}\) be the set of available frequencies and \(\{0\} \subseteq T_0 \subseteq T_1 \subseteq \cdots \subseteq T_L \subseteq F\). The constraint graph has one vertex for each transmitter and edges with labels in \(\{0,1,\ldots,L\}\) describing interference. A frequency assignment in a constraint graph \(G=(V,E)\) is a mapping \(f : V \to F\) such that \(|f(x)-f(y)|\notin T_i\) if edge \(\{x,y\}\) has label \(i\). For a given constraint graph \(G\) with edge labels and sets \(T_i\) the minimum value of \(K\) such that a frequency assignment exists is called the span of \(G\). For a large number of transmitters heuristic methods are used to find assignments with small \(K\). This paper proves lower bounds for the span and describes methods to reduce the size of the problem.