Assigning airport gates during a pandemic using tolerance graphs

Tolerance graphs, introduced by M. C. Golumbic and C. L. Monma in 1982, are a generalization of interval graphs. In this paper, we propose an application of coloring of tolerance graphs together with machine learning, in particular supervised learning, in solving problems of airport gate assignment during a pandemic of an airborne disease. The idea is to minimize a contact between passengers at the gates, in order to slow down a spread of the disease. This application includes calculating the chromatic number of a graph and finding a clique of a given size in the graph. As a result, we obtain the minimum number of gates needed under the given assumptions and the corresponding gate assignment. Further, we propose an application of list coloring, a generalization of a coloring, of tolerance graphs in solving these problems. Besides the theoretical approach, the corresponding algorithms are given. The algorithms developed may take into account several parameters, such as the number of passengers on a flight, the number of newly infected people per 1000 inhabitants. A similar approach can be taken for classroom assignment during a pandemic, scheduling meetings, etc.