Solving the graph b-coloring problem with hybrid genetic algorithm

摘要

A b-coloring of a graph G with k colors is a proper coloring of its vertices such that each color class contains a vertex that has a neighbor in all the other color classes. The b-chromatic number of a graph G is the largest integer k such that the graph has a b-coloring with k colors. The graph b-coloring is a NP-hard problem and there is no heuristic used to solve it in literature. In this paper, a hybrid approach based on genetic algorithm, recursive largest first heuristic (RLF), and specific heuristic for mutation, is proposed, to solve the b-coloring problem. The problem is formulated as a bi-objective optimization problem in which two objectives are considered. To validate our work, the proposed algorithm was tested and compared with relative proven and known theorical results for specific graphs, such as regular graphs and trees. In addition the algorithm was tested for some general graphs, and the obtained results are encouraging.