An Immune System for the general T-coloring problem

Graph coloring Problem is a well known problem from graph theory and admits several generalizations. The generalization we study in this paper is the T-Coloring. Given a graph G and a set T of positive integers associated to each edge of G, a T-Coloring of G is to assign one color to each vertex of G so the distance between the assigned colors does not exist in the associated set T. Since this problem is NP-Complete, heuristic methods must be involved. Only few methods are implemented for a restricted case, in which the sets T are composed from consecutive integers. The field of Artificial Immune Systems (AIS) concerns the study and development of computationally interesting abstractions of the immune system. One of is the clonal selection principle which seems efficient when applied to the multi-modal Optimization. We introduce, in this paper, an evolutionary approach using an artificial immune systems principle for the general T coloring problem, namely the clonal Selection. This approach will be experimented with different parameter´s settings. For this purpose, we´ll use random instances for both restrictive and general T-Coloring Problems.