A New Genetic Algorithm for Graph Coloring

Abstract

Graph coloring problem is a classical example for NP-hard combinatorial optimization. Solution to this graph coloring problem often finds its applications to various engineering fields. This paper exhibits the robustness of genetic algorithm to solve a graph coloring. The proposed genetic algorithm employs an innovative single parent conflict gene crossover and a conflict gene mutation as its operators. The time taken to get a convergent solution of this proposed genetic method has been compared with the existing approaches and has been proved to be effective. The performance of this approximation method is evaluated using some benchmarking graphs, and are found to be competent.