Are there any vertex colouring algorithms which colour regular graphs optimally? As the question suggests I am looking for a vertex colouring algorithm preferably exact, which can colour regular graphs optimally. Is there any which is known in literature?
 A: No hope. The line graph of a cubic graph is 4-regular, and so its chromatic number is three if and only the cubic graph has an edge 3-coloring. Deciding this is NP-complete. 
A: Here is what Wiki says on Graph Colorings

Graph coloring is computationally hard. It is NP-complete to decide if a given graph admits a $k$-coloring for a given $k$ except for the cases $k = 1$ and $k = 2$. In particular, it is NP-hard to compute the chromatic number.[19] The 3-coloring problem remains NP-complete even on planar graphs of degree 4.[20] However, k-coloring of a planar graph is in P, for every k>3, since every planar graph has a 4-coloring.

Further MathWorks knows about Minimum Vertex Coloring

Brelaz's heuristic algorithm can be used to find a good, but not necessarily minimum vertex coloring. Finding a minimal coloring can be done using brute-force search (Christofides 1971; Wilf 1984; Skiena 1990, p. 214), though more sophisticated methods can be substantially faster. A minimal vertex coloring can be found for small graphs using backtracking with MinimumVertexColoring[g] in the Wolfram Language package Combinatorica and Brelaz's algorithm can be applied using BrelazColoring[g]. 

On Mathematica.SE they had an example for the first mentioned function...
