Mohamed Al-Ibrahim, Naser Al-Ibrahim, Yousef Rafique, Omar Al-Sumait
International Journal of Computer, vol. 23, no. 1, pp. 42-52, Nov. 2016
Publication year: 2016

The objective of the Graph Coloring problem is to colour vertices of a graph in such a way that no two vertices that share an edge are assigned the same colour. Aircraft Scheduling, Frequency Assignment, register allocation are all real-life applications that can be solved using graph colouring. Graph Coloring is a well-known NP-complete problem in academia in computer science and mathematics. In this paper, we use the concept of complementary graphs to come up with a new heuristic for graph colouring. Our results are compared with an exact algorithm and other heuristic algorithms to evaluate our algorithm’s performance.