The Graph Coloring Problem (GCP) is a well-known NP-complete problem. Graph coloring includes both vertex coloring and edge coloring. However, the term graph coloring usually refers to vertex coloring rather than edge coloring.
Given a number of vertices, which form a connected graph, the objective is to color each vertex such that if two vertices are connected in the graph (i.e. adjacent) they will be colored with different colors. Moreover, the number of different colors that can be used to color the vertices is limited.
Given a graph G and the number of colors k output a colored graph. In this mini project, GA has been applied with the following properties to this problem:
Recombination -> Single-point
Mutation -> set new random color for each adjacent vertex with the same color
Population -> size 100