Suggest effective heuristic (not precise) graph colouring algorithm

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.

• First Fit does precisely the above, with an arbitrary initial ordering. It's fast, but needless to say performs rather poorly.


• LDO orders the vertices in decreasing order of degree, the idea being that the large degree vertices can be colored more easily.


• SDO (saturation degree ordering) is a variant on LDO where the vertices are ordered in decreasing order by "saturation degree", defined as the number of distinct colors in the vertex neighborhood.


• IDO (incidence degree ordering) is a variant of SDO where the "degree" of a vertex is defined as the number of colored vertices in its neighborhood.

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.