Variable space search for graph coloring

Let G=(V,E)G=(V,E) be a graph with vertex set VV and edge set EE. The kk-coloring problem is to assign a color (a number chosen in {1,…,k}{1,…,k}) to each vertex of GG so that no edge has both endpoints with the same color. We propose a new local search methodology, called Variable Space Search, which we apply to the kk-coloring problem. The main idea is to consider several search spaces, with various neighborhoods and objective functions, and to move from one to another when the search is blocked at a local optimum in a given search space. The kk-coloring problem is thus solved by combining different formulations of the problem which are not equivalent, in the sense that some constraints are possibly relaxed in one search space and always satisfied in another. We show that the proposed algorithm improves on every local search used independently (i.e., with a unique search space), and is competitive with the currently best coloring methods, which are complex hybrid evolutionary algorithms.