structural:summarization, information:classification
Heuristic algorithms

Two well-known polynomial-time heuristics for graph colouring are the DSatur and recursive largest first (RLF) algorithms.

Similarly to the greedy colouring algorithm, DSatur colours the vertices of a graph one after another, expending a previously unused colour when needed. Once a new vertex has been coloured, the algorithm determines which of the remaining uncoloured vertices has the highest number of different colours in its neighbourhood and colours this vertex next. This is defined as the degree of saturation of a given vertex.

The recursive largest first algorithm operates in a different fashion by constructing each color class one at a time. It does this by identifying a maximal independent set of vertices in the graph using specialised heuristic rules. It then assigns these vertices to the same color and removes them from the graph. These actions are repeated on the remaining subgraph until no vertices remain.

The worst-case complexity of DSatur is O (n 2) {\displaystyle O(n^{2})}, where n {\displaystyle n} is the number of vertices in the graph. The algorithm can also be implemented using a binary heap to store saturation degrees, operating in O ((n + m) log n) {\displaystyle O((n+m)\log n)} where m {\displaystyle m} is the number of edges in the graph. This produces much faster runs with sparse graphs. The overall complexity of RLF is slightly higher than DSatur at O (m n) {\displaystyle O(mn)}.

DSatur and RLF are exact for bipartite, cycle, and wheel graphs.