Using a Genetic Algorithm Approach to Solve the Chromatic Number Problem
Anand Kumar · 2009
least number of colors needed to color a graph G is called its chromatic number, χ(G). For example the chromatic number of a complete graph Kn of n vertices (a graph with an edge between every two vertices), is χ(Kn) = n. A graph that can be assigned a (proper) k-coloring is k-colorable, and it is k-chromatic if its chromatic number is exactly k. This paper presents a genetic algorithm approach to solve the Chromatic Number Problem. The Chromatic Number Problem is NP complete problem and - one of the hardest problems in the class NP (non-deterministic polynomial problems). A genetic algorithm is simply the algorithm used to simulate evolution. It takes candidate solutions, selects some of the best using user-defined evaluation functions, applies user-defined transformations (often called mutation and crossover, but implementations of these depend on the problem), and makes new candidate solutions. Genetic Algorithms are being used extensively in optimization problem as an alternative to traditional heuristics. It is an appealing idea that the natural concepts of evolution may be borrowed for use as a computational optimization technique, which is based on the principle Survival of the fittest given by Darvin. In this paper I have used genetic algorithm as an optimization technique to provide the solution for Chromatic Number Problem. I have tried to show that genetic algorithm is an alternative solution for this NP hard problem where conventional deterministic methods are not able to provide the optimal solution.