DIFFERENTIAL EVOLUTION FOR GRAPH COLORING PROBLEM

Graph coloring problem (GCP) is a well-known hard-to-solve problem in literature. In short, it consists of coloring a graph using the minimum number of colors such that no adjacent vertices have the same colors. The literature presents several applications to GCP.  Differential Evolution (DE) is a populational-based evolutionary algorithm originally proposed for solving continuous optimization problems. This work presents a study of an adaptation of DE to GCP. The algorithm, called DE-GCP is compared with literature algorithms using well-known instances benchmark. DE-GCP was able to find the chromatic number (optimum solution with the minimum number of colors) for all 11 instances in the literature used in the experiments, presenting competitive results with other literature methods.