Brélaz minimum colouring

Question

I've finished implementing Brélaz algorithm to try coloring a graph with the least colors possible. The fact is, until now, all the tests I've ran for it color it successfully with the minimum number of colors needed. But I've read several times that Brélaz, yet being a good algorithm does not necessarily achieve minimum coloring for a graph.

Could someone confirm this, and give me an example of a graph that would prove it?

Answer 1

Brélaz is a heuristic for vertex coloring from the 70s, also known as DSATUR (degree of saturation). It is known to be specially good with Erdös-Rényi graphs (uniform random) and achieves a good compromise between effort and tightness.

However it is only just that, a heuristic, and cannot certify an optimum.

Brélaz can be also used inside a full enumeration scheme, as described in [Randall-Brown 72], but I guess this is not what you have implemented.

There have also been some improvements over DSATUR, mainly concerning tiebreaks

1. Sewell 1996
2. San Segundo 2012 (algorithm PASS)