Hybrid evolutionary algorithm for the b-chromatic number
The b-chromatic number of a graph \(G\) is a maximum integer \(\varphi (G)\) for which there exists a proper \(\varphi (G)\)-coloring with the additional property that each color class contains a vertex that is adjacent to one of the vertices within each color class. In contrast to many theoretical results discovered over the last decade and a half there are no computer running experiments on \(\varphi (G)\) in the literature. This work presents a hybrid evolutionary algorithm for graph b-coloring. Its performance has been tested on some instances of regular graphs where their b-chromatic number is theoretically known in advance, as well as by comparing with a brute force algorithm solving the regular graphs up to 12 vertices. In addition, the algorithm has been tested on some larger graphs taken from a DIMACS challenge benchmark that also proved to be challenging for the algorithms searching for the classical chromatic number \(\chi (G)\).
hybrid evolutionary algorithms graph b-coloring local search tabucol