# Flight Level Assignment Using Graph Coloring
## 2 Flight-Level Assignment as Spectrum Coloring Problem with Hard Constraints
### Graph Coloring Model  
As stated above, the safety considerations in the FL assignment scenario can be translated to an instance of the Spectrum Coloring problems we studied in [5]. Problems in this class are defined by an abstract graph \(G\), a spectrum of colors \(C\), and an interference matrix \(W\). The construction of the graph \(G\) requires further attention and will be detailed in Section 3.1. For the spectrum \(C\) we consider 40 colors, corresponding to the 40 FLs ranging from FL10 (1000 feet) to FL400 (40,000 feet), with 1000 feet separation between adjacent FLs. Finally, in order to define the interference matrix \(W\) we will use a conservative approach, which is coherent with the serious safety considerations in -aviation scenarios. We will assume that there is a distance threshold \(\delta\), expressed in multiples of 1000 feet, below which the risks of incidents are not tolerable, so we will assign an infinite value to the entries of \(W\) corresponding to pairs of colors in which corresponding FLs are closer than the threshold \(\delta\). For \(\delta=0\) the interference matrix \(W^{0}\) will be the null matrix. Recalling Equation (9), in the \(\delta=0\) case only fuel consumption is considered, without taking interferences into account. For \(\delta=1\), the interference matrix \(W^{1}\) has the value \(\infty\) at all the entries of the main diagonal, that is,  
\[W^{1}=\begin{pmatrix}\infty&0&\dots&0&0\\ 0&\infty&\dots&0&0\\ \vdots&&\ddots&&\vdots\\ 0&0&\dots&\infty&0\\ 0&0&\dots&0&\infty\end{pmatrix}. \tag{10}\]  
This corresponds to the classic Proper Coloring problem where no monochromatic edges are allowed. In our setting, this means that no two crossing routes are allowed to be assigned to the same FL. In a similar way, for \(\delta=2\) the interference matrix \(W^{2}\) is a tridiagonal matrix which adds values \(\infty\) at the superdiagonal and subdiagonal, as follows:  
\[W^{2}=\begin{pmatrix}\infty&\infty&0&0&\dots&0\\ \infty&\infty&\infty&0&\dots&0\\ \vdots&\ddots&\ddots&\ddots&&\vdots\\ 0&\dots&\infty&\infty&\infty&0\\ 0&\dots&0&\infty&\infty&\infty\\ 0&\dots&0&0&\infty&\infty\end{pmatrix}. \tag{11}\]  
This corresponds to an \(L(h,k)\)-labeling [30] with \(h=2\) and \(k=0\). In our problem, this means that equal or adjacent FLs are not allowed for crossing routes. Analogously, similar matrices \(W^{\delta}\) can be derived for higher values of \(\delta\).  
Our spectrum coloring model has great expressivity, allowing a number of different possibilities, which we leave for future work. One example is to define a matrix \(\widetilde{W}^{2}\) having infinite values at the diagonal as before, but with finite values at the superdiagonal and the subdiagonal. In such a model, we would be ensuring a separation of at least one flight level between crossing routes and encouraging (instead of forcing) a separation of two FLs between such routes. This would give better flexibilities to pilots, which would be able to move to an adjacent different flight level during the cruise stage in case of, for example, turbulences. Another example would be different decision makers (pilots or airlines) having matrices \(W\) with different finite values, modeling different risk tolerances.