Can you suggest a good rough graph colouring algorithm? What are the best such algorithms nowadays?

An interesting approximation algorithm is the one by Wigderson. It shows how to color a 3colorable graph with $O(\sqrt{n})$ colors. It's very simple: If the maximum degree is less than $\sqrt{n}$, you're done (just color greedily). If there is a node of degree larger than $\sqrt{n}$, you know that it's neighborhood is twocolorable so twocolor it and never use those colors again. Remove the vertex and its neighbors from the graph and continue. There have been several followup works by Blum and the latest improvements use semidefinite programming. See, for instance, http://www.cs.cmu.edu/~anupamg/advapprox/lecture15.pdf or, http://www.cs.princeton.edu/~chlamtac/accstoc.ps for the semidefinite programming approach. 


There are a number of heuristics that work fairly well. They all work by prescribing some kind of ordering on the vertices, and then coloring the vertices one by one, using the least unused color to color the next one.
The latter two heuristics require the order to be rebuilt after each step, and so are more expensive, but there's empirical evidence suggesting that they do reasonably well, especially in parallel. None of these algorithms come with any kind of formal guarantees, so be warned. 


For practical nonoptimal purposes you might want to look at DSATUR, and this paper, which briefly describes some simple methods: http://www.math.tuclausthal.de/Arbeitsgruppen/DiskreteOptimierung/publications/2002/gca.pdf 


You might find this survey article of use: 


If “heuristic graph coloring algorithms” means approximation algorithms for the chromatic number, it is very useful to read “A compendium of NP optimization problems” edited by Pierluigi Crescenzi and Viggo Kann (http://www.csc.kth.se/~viggo/wwwcompendium/node15.html), which provides references for the bestknown approximability and inapproximability results as of 2000. 


Oleg, there are also stochastic parallel approaches where you color all vertices simultaneously and randomly and apply the heuristic in parallel to all of the vertices. This mimics parallel distributed information processing in networks. Can you give some details about the heuristic which you are working on? 


How to write an algorithm for coloring vertices of a graph in C#? 

