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

• Published in: Computers & operations research 2020-08, Vol.120, p.104850-30, Article 104850
• Main Authors: Mostafaie, Taha, Modarres Khiyabani, Farzin, Navimipour, Nima Jafari
• Format: Article
• Language: English
• Subjects: Algorithms; Apexes; Directed graph; Edge joints; Graph coloring; Graph theory; Heuristic; Heuristic methods; High runtime; Literature reviews; Meta-heuristic; Operations research; Optimal coloring; Optimization; Robust GCP
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2019.104850

•Providing an outline of the challenges available in the problem domain associated with the coloring of the graph.•Providing a synopsis of insights and implementation of optimization techniques in the graph coloring, as well as describing trends in applications of the meta-heuristic algorithms for GCP.•Highlighting the significance of meta-heuristic optimization algorithms, and several advantages they provide to tackle challenges encountered in the graph coloring.•Organizing related open issues and a few insights to solve current problems of reviewed algorithms. 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.