A systematic study on meta-heuristic approaches for solving the graph coloring problem

摘要

Typically, Graph Coloring Problem (GCP) is one of the key features for graph stamping in graph theory. The general approach is to paint at least edges, vertices, or the surface of the graph with some colors. In the simplest case, a kind of coloring is preferable in which two vertices are not adjacent to the same color. Similarly, the two edges in the same joint should not have the same color. In addition, the same goes for the surface color of the graph. This is one of the NP-hard issues well studied in graph theory. Therefore, many different meta-heuristic techniques are presented to solve the problem and provide high performance. Seemingly, regardless of the importance of the nature-stimulated meta-heuristic methods to solve the GCP, there is not any inclusive report and detailed review about overviewing and investigating the crucial problems of the field. As a result, the present study introduces a wide-ranging reporting of nature- stimulated meta-heuristic methods, which are used throughout the graph coloring. The literature review contains a classification of significant techniques. This study mainly aims at emphasizing the optimization algorithms to handle the GCP problems. Furthermore, the advantages and disadvantages of the meta-heuristic algorithms in solving the GCP and their key issues are examined to offer more advanced meta-heuristic techniques in the future. (C) 2019 Published by Elsevier Ltd.