Title :
An algorithm to approximate the chromatic number of graphs
Author :
Guzman Ponce, Angelica ; Marcial-Romero, J. Raymundo ; Henrandez, Jose A. ; De Ita, Guillermo
Author_Institution :
Fac. de Ing., Univ. Autonoma del Estado de Mexico, Toluca, Mexico
Abstract :
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.
Keywords :
approximation theory; computational complexity; graph colouring; number theory; set theory; average degree approximation; chromatic graph number approximation; maximal independent set; Algorithm design and analysis; Approximation algorithms; Approximation methods; Color; Games; Heuristic algorithms; Proposals;
Conference_Titel :
Electronics, Communications and Computers (CONIELECOMP), 2015 International Conference on
Conference_Location :
Cholula
DOI :
10.1109/CONIELECOMP.2015.7086935
