Tolerance graphs were introduced in 1982 by Golumbic and Monma as a generalization of interval graphs. In this paper, we propose several applications of tolerance graphs in fighting COVID-19. These applications include finding cliques of a certain size, and calculating the chromatic number of a graph, the problems that are in general NP-complete but for tolerance graphs can be solved in polynomial time.
Keywords: Chromatic number; Clique; Pandemic; Perfect graph; Tolerance graph.
© The Author(s), under exclusive licence to Springer Nature Singapore Pte Ltd. part of Springer Nature 2021.