Resolution of the general T-coloring problem using an MBO based algorithm

A generalization of the classical graph coloring model is studied in this paper. The problem we are interested in is the T-coloring problem related in the literature. It consists on coloring the vertices of a graph in such a way that the two colors assigned to two adjacent vertices i and j does not appear in Tij, where Tij is a set of positive integers associated to the edge [i,j]. The T-Coloring problem is to find the minimum length of the spectrum of colors used. Honey-bees are among the most closely studied social insects. Honey bee mating may also be considered as a typical swarm-based approach to optimization, in which the search algorithm (Marriage Bees Optimization: MBO) is inspired by the process of marriage in real bees´ colonies. In this paper, an MBO algorithm is presented for three coloring problems: graph coloring, Restricted T-colorings and general T-colorings. Several experiments are performed in order to study the efficiency of the proposed algorithm. The results are compared with optimal colorings obtained by well-known methods on well-known benchmarks for each problem. Results show encouraging results.