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.