Graph Colouring in the Limelight of Degree Sequence

Design and analysis of new algorithms are an ever going phenomena in the life of computer scientists. NP problems are attracting designers to design both heuristic and approximate algorithms that can result in better optimal and time-space efficient algorithms. Deterministic graph colouring algorithms are generally of contraction and sequential type in nature. Sequential algorithms can be extended by backtracking to relatively eûective algorithms for the chromatic number of a graph. Incomplete backtracking leads to new heuristic for graph colouring. In this paper we describe a heuristic algorithm to colour the vertices of a graph which relies upon the comparison of the degrees and structure of the graph. We have compared it with the maximum-degree-node-first and minimum-degree-node-last criteria based algorithms. This paper reviews a broad spectrum of sequential vertex colouring algorithms based on heuristics.