Article Preview
Top1. Introduction
The graph coloring problem (GCP) is one of the most interesting and difficult combinatorial optimization problems in computer science, mathematics, and operations research. It has been widely used for modeling and solving many significant real-world problems like time tabling (de Werra, An introduction to timetabling, 1985), scheduling (Lotfi & Sarin, 1986), (Dowsland & Thompson, 2005), computer register allocation (Chaitin, Cocke, Hopkins, & Markstein, 1981), (de Werra, Eisenbeis, Lelait, & Marmol, 1999), radio frequency assignment (Gamst, 1986), (Smith, Hurley, & Thiel, 1998), printed circuit board-testing (Garey, Johnson, & So, 1976), communication networks (Woo, Su, & Newman-Wolfe, 1991), and many others. The graph coloring problem consists in assigning a color to each vertex of a given graph with the limitation that no two adjacent vertices gain same colors and the number of different colors used is minimized. The minimum number of colors by which a graph is colored is called its chromatic number, it is denoted by χ(G). A graph G is K-colorable, if it can be legally colored using at most K colors. The problem of finding the chromatic number χ(G) of any graph is known to be an NP-Hard problem (Garey & Johnson, 1979) and has recently drawn an increasing attention from researchers, so several methods have been adopted for solving this problem including greedy constructive approaches, local search heuristics, metaheuristics, and hybrid approaches.
Constructive approaches are based on greedy approach which color the vertices of the graph one by one using a predefined greedy function. The most constructive algorithms employed to solve the GCP are the Recursive Largest First algorithm (RLF) proposed by Leighton (Leighton, 1979) and the largest saturation degree algorithm (DSATUR) developed by Brélaz (Brélaz, 1979). These constructive methods are recently used to generate initial solutions for advanced metaheuristic.
A large number of local search methods have been widely proposed for solving the GCP. The Tabu Search Algorithm proposed by Hertz and Werra (Hertz & de Werra, 1987) was the first local search algorithm applied to solve the graph coloring problem. It is called TABUCOL and has been enhanced by several authors and used as a subcomponent of more other graph coloring algorithms.
Moreover, many efficient metaheuristics such as Genetic Algorithm (GA) (Abbasian & Mouhoub, 2013), (Zhang, Qiu, Li, & Liu, 2014), Cuckoo Search algorithm (CS) (Zhou, Zheng, Luo, & Wu, 2013), (Djelloul, Layeb, & Chikhi, 2014), (Mahmoudi & Lotfi, 2015), Artificial Bee Colony (ABC) (Faraji & Javadi, 2011), (Dorrigiv & Markib, 2012), Particle Swarm Optimization (PSO) (Aoki, Aranha, & Kanoh, 2015), Memetic Algorithm (MA) (Lü & Hao, 2010), and combining algorithms (Mabrouk, Hasni, & Mahjoub, 2009), (Ge, Wei, Tian, & Huang, 2010), (Qin, Yin, & Ban, 2011), (Douiri & Elbernoussi, 2015) have been employed to solve the Graph coloring problem.