The paper is organised as
Graph colouring is one of the extensively studies areas of research, yet many studies have been emerging. Many techniques have been proposed for solving many variants of GCP. Exact approaches tend to fail particularly while solving large instances, hence many researchers have been working on heuristic approaches. For example, recursive largest fit is a well-known greedy heuristic introduced by Leighton (1979). Hertz and Werra (1987) presented the first tabu search implementation which outperforms another local search method, simulated annealing on random dense graph instances. Davis and Mitchell (1991) proposed a coding as an ordering of vertices which could be used in a genetic algorithm. Johnson, Aragon, Mcgeoctt, and Schevon (1991) presented three simulated annealing implementations based on three neighbouring approaches. Galinier and Hao (1999) have shown that BIO 1211 hybridisation of GAs with local search methods are more promising than GAs on their own. In such hybridisation, local search operators are used as intensification methods to explore promising areas of the search space mutation have found by the GA operators. Avanthay, Hertz, and Zufferey (2003) proposed a variable neighbourhood search algorithm for graph colouring problem. Studies in ülker et al., 2006, ülker et al., 2008, Korkmaz, 2010 and Kirovski and Potkonjak, 1998 apply generic GAs using some of the genetic representations discussed in Section 2.1.1 to solve graph colouring problem. Ülker et al. (2006) proposed special crossover operators for graph colouring, namely Lowest Index Max Crossover (LIMX), Greedy Partition Crossover Lowest Index (GPX-LI) and Greedy Partition Crossover Cardinality Based (GPX-CB). Külahç?o?lu (2007) proposed two modified versions of the LLE representation which are Linear Linkage Encoding With Ending Node Links (LLE-e) and Linear Linkage Encoding With Backward Links (LLE-b), and both of them are tested using genetic operators.