DSatur

Let the "degree of saturation" of a vertex be the number of different colours being used by its neighbors. Given a simple, undirected graph ${\displaystyle G}$ compromising a vertex set ${\displaystyle V}$ and edge set ${\displaystyle E}$, the algorithm assigns colors to all of the vertices using color labels ${\displaystyle 1,2,3,...}$. The algorithm operates as follows:[4]

1. Let ${\displaystyle v}$ be the uncolored vertex in ${\displaystyle G}$ with the highest degree of saturation. In cases of ties, choose the vertex among these with the largest degree in the subgraph induced by the uncolored vertices.
2. Assign ${\displaystyle v}$ to the lowest color label not being used by any of its neighbors.
3. If all vertices have been colored, then end; otherwise return to Step 1.

Step 2 of this algorithm assigns colors to vertices using the same scheme as the greedy colouring algorithm. The main differences between the two approaches arises in Step 1 above, where vertices seen to be the most "constrained" are coloured first.

Wheel graph with seven vertices and twelve edges

Consider the graph ${\displaystyle G=(V,E)}$ shown on the right. This is a wheel graph and will therefore be optimally colored by the DSatur algorithm. Executing the algorithm results in the vertices being selected and colored as follows. (In this example, where ties occur in both of DSatur's heuristics, the vertex with lowest lexicographic labelling among these is chosen.)

1. Vertex ${\displaystyle g}$ (color 1)
2. Vertex ${\displaystyle a}$ (color 2)
3. Vertex ${\displaystyle b}$ (color 3)
4. Vertex ${\displaystyle c}$ (color 2)
5. Vertex ${\displaystyle d}$ (color 3)
6. Vertex ${\displaystyle e}$ (color 2)
7. Vertex ${\displaystyle f}$ (color 3)

This gives the final three-colored solution ${\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}}$.

The worst-case complexity of DSatur is ${\displaystyle O(n^{2})}$, where ${\displaystyle n}$ is the number of vertices in the graph. This is because the process of selecting the next vertex to colour takes ${\displaystyle O(n)}$ time, and this process is carried out ${\displaystyle n}$ times. The algorithm can also be implemented using a binary heap to store saturation degrees, operating in ${\displaystyle O((n+m)\log n)}$, or ${\displaystyle O(m+n\log n)}$ using Fibonacci heap, where ${\displaystyle m}$ is the number of edges in the graph.[2] This produces much faster runs with sparse graphs.

DSatur is known to be exact for bipartite graphs,[1] as well as for cycle and wheel graphs.[2] In an empirical comparison by Lewis in 2021, DSatur produced significantly better vertex colourings than the greedy algorithm on random graphs with edge probability ${\displaystyle p=0.5}$, while in turn producing significantly worse colourings than the recursive largest first algorithm.[2]

• High-Performance Graph Colouring Algorithms Suite of graph colouring algorithms (implemented in C++) used in the book A Guide to Graph Colouring: Algorithms and Applications (Springer International Publishers, 2021).
• C++ implementation of the DSatur Algorithm, presented as part of the article The DSatur Algorithm for Graph Coloring, Geeks for Geeks (2021)