Cellular Learning Automata-based Graph Coloring Problem

Abstract. The vertex coloring problem is a well-known classical problem in graph theory in which a color is assigned to each vertex of the graph such that no two adjacent vertices have the same color. The minimum vertex coloring problem is known to be an NP-hard problem in an arbitrary graph. In this paper, an irregular cellular learning automata (ICLA) based approximation algorithm is proposed for solving the minimum (vertex) coloring problem. It is shown that by a proper choice of the parameters of the algorithm, the probability of approximating the optimal solution is as close to unity as possible. Our proposed algorithm is compared with some well-known coloring algorithms and the results show the superiority of the proposed algorithm both in terms of the color set size and running time of algorithm over the existing methods.