An algorithm to approximate the chromatic number of graphs
Angélica Guzmán-Ponce, J. Raymundo Marcial‐Romero, José Antonio Hernández Servín, Guillermo De Ita Luna · 2015
In this paper, we present an algorithm to approximate the chromatic number of a graph. Our proposal is based on the construction of maximal independent set. We experimentally show that our proposal improves the average degree approximation proposed by De Ita et. al. [10]. Finally, our proposal is compared against JGraphT and Sage which contain a model for computing the chromatic number of a graph.