Solution to Graph Coloring Problem using Divide and Conquer based Genetic Method

Some of the engineering applications warrant the solution of Graph Coloring Problem. This paper investigates a new genetic procedure using divide and conquer strategy on some of the intermediate (100 <= n <= 500) and large scale benchmark graphs (n >= 500) to obtain the near optimal chromatic number. Finding the chromatic number is an NP-hard and combinatorial optimization problem. The divide & conquer strategy is implemented by partitioning the vertex set V(G) into some subsets and the subsets are solved heuristically. Single Parent Conflict Gene Crossover & Conflict Gene Mutation genetic operators with Conflict Gene Removal constraints reduce the problem search space, the mean number of genetic generations ((g) over bar), mean crossovers ((C) over bar) & mutations ((m) over bar) and also to increase the amount of successful runs in terms of percentages. The devised method is compared with some of the existing well known approaches and also the results are found to be better. The devised method significantly reduces complexity in obtaining the near optimal solution.