Solving Graph Coloring Problem Using Genetic Algorithm

Authors(2) :-A. Nivetha, T. Ramesh

To Solve the Graph Coloring Problem we use the Genetic Algorithm (GA) that uses the classical crossover operation .Graph Coloring Problem is the interest researcher's area. We use the chromosomes as a binary operators. By Evolutionary Algorithm (EA) of Coloring is an assignment of colors to the vertices of a graph G such that no two Adjacent Vertices have the same color. We reduce the chromatic number (maximum out degree +1) using the Genetic Algorithm till get the optimum solution.

Authors and Affiliations

A. Nivetha
MSc Mathematics, Dr SNS Rajalakshmi College of Arts and Science, Coimbatore, Tamil Nadu, India
T. Ramesh
Assistant Professor, Dr SNS Rajalakshmi College of Arts and Science, Coimbatore, Tamil Nadu, India

Genetic Algorithm, Binary Coding, Graph Coloring.

  1. M. Kubale , "Graph colorings," American Mathematical Society, 2004.
  2. C. W. K. Chen and D. Y. Y. Yun, "Unifying graph-matching problem with a practical solution," in Proc. International Conf. on Systems, Signals, Control, Computers, September 1998.
  3. B. H. Gwee, M. H. Lim, and J. S. Ho, "Solving four-coloring map problem using genetic algorithm," in Proc. Artificial Neural Networks and Expert Systems.
  4. B. Ray, A. J. Pal, D. Bhattacharyya, and T. Kim, "An efficient GA with multipoint guided mutation for graph coloring problems," International Journal of Signal Processing, Image Processing and Pattern Recognition, vol. 3, no. 2, pp. 51-58, 2010.
  5. A. Lim, Y. Zhu, Q. Lou, and B. Rodrigues, "Heuristic methods for graph coloring problems," in Proc. Symposium on Applied Computing, 2005.

Publication Details

Published in : Volume 4 | Issue 10 | September-October 2018
Date of Publication : 2018-09-30
License:  This work is licensed under a Creative Commons Attribution 4.0 International License.
Page(s) : 202-205
Manuscript Number : IJSRSET1841049
Publisher : Technoscience Academy

Print ISSN : 2395-1990, Online ISSN : 2394-4099

Cite This Article :

A. Nivetha, T. Ramesh, " Solving Graph Coloring Problem Using Genetic Algorithm, International Journal of Scientific Research in Science, Engineering and Technology(IJSRSET), Print ISSN : 2395-1990, Online ISSN : 2394-4099, Volume 4, Issue 10, pp.202-205, September-October-2018. Available at doi :
Journal URL :

Article Preview