Approximate the chromatic number of a graph using maximal independent sets
Angélica Guzmán-Ponce, J. Raymundo Marcial‐Romero, Guillermo De Ita Luna, José Antonio Hernández Servín · 2016
In this paper, we present an algorithm to approximate the chromatic number of a graph. The proposed approach initially removes even cycles and acyclic subgraphs, this process is called debugging, later to colour the remaining graph, we present a strategy to obtain maximal independent sets. We experimentally show that our proposal improves the results compare to JGraphT and Sage which contain a module for computing the chromatic number of a graph.