Genetic algorithm for black and white coloring problem on graphs

Abstract

A classical problem in graph theory and combinatorial optimization is the known as Graph Coloring Problem (GC). This problem consists in assigning colors to vertices of a graph such that two adjacent vertices must have different colors. The objective in this problem is to find the minimum number of colors needed to coloring the graph under the coloring condition. In the case of the Graph Anti-Coloring Problem (GAC) the color assignment is opposite. In this case two adjacent vertices must have the same color or one of them does not have any color. In this problem the objective is different in the sense of number of colors which is fixed. This problem can be turned in an optimization problem. The GAC is NP-Complete, even with two colors[2]. In this work we deal with two colors special case of GAC with genetic algorithms and compare with Tabú Search which is the state of the art solution for this problem[3].

Keywords

• Anticoloring
• Genetic Algorithm
• BWC