Hybrid evolutionary algorithm for the b-chromatic number

作者：Fister Iztok^*; Peterin Iztok; Mernik Marjan; Crepinsek Matej

来源：Journal of Heuristics, 2015, 21(4): 501-521.

DOI：10.1007/s10732-015-9288-z

• Graph b-coloring
• Local search
• Hybrid evolutionary algorithms
• Tabucol

The b-chromatic number of a graph is a maximum integer for which there exists a proper phi(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 phi(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).

• 出版日期2015-8