Variations on Memetic Algorithms for Graph Coloring Problems

Given an undirected graph G (V, E) with V a set of vertices and E a set of edges, graph vertex coloring involves assigning each vertex with a color so that two adjacent vertices (linked by an edge) feature different colors. The Graph Vertex Coloring Problem (GVCP) consists in finding the minimum number of colors, called chromatic number χ(G), required to color the graph G while respecting these binary constraints. The GVCP is a well-documented and much-studied problem because this simple formalization can be applied to various issues such as frequency assignment problems [1, 2], scheduling problems [3, 4, 5] and flight level allocation problems [6, 7]. Most problems that involve sharing a rare resource (colors) between different operators (vertices) can be modeled as a GVCP.