DSatur explained

DSatur is a graph colouring algorithm put forward by Daniel Brélaz in 1979.^[1] Similarly to the greedy colouring algorithm, DSatur colours the vertices of a graph one after another, adding 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 colours in its neighbourhood and colours this vertex next. Brélaz defines this number as the degree of saturation of a given vertex. The contraction of the term "degree of saturation" forms the name of the algorithm.^[2] DSatur is a heuristic graph colouring algorithm, yet produces exact results for bipartite, cycle, and wheel graphs. DSatur has also been referred to as saturation LF in the literature.^[3]

Pseudocode

compromising a vertex set and edge set , the algorithm assigns colors to all of the vertices using color labels . The algorithm operates as follows:^[4]

1. Let

be the uncolored vertex in 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.

1. Assign

to the lowest color label not being used by any of its neighbors.

1. 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.

Example

Consider the graph

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

(color 1)

1. Vertex

(color 2)

1. Vertex

(color 3)

1. Vertex

(color 2)

1. Vertex

(color 3)

1. Vertex

(color 2)

1. Vertex

(color 3)

This gives the final three-colored solution

.

Performance

The worst-case complexity of DSatur is

, where is the number of vertices in the graph. This is because the process of selecting the next vertex to colour takes time, and this process is carried out times. The algorithm can also be implemented using a binary heap to store saturation degrees, operating in , or using Fibonacci heap, where is the number of edges in the graph. This produces much faster runs with sparse graphs.

DSatur is known to be exact for bipartite graphs, as well as for cycle and wheel graphs. In an empirical comparison by Lewis in 2021, DSatur produced significantly better vertex colourings than the greedy algorithm on random graphs with edge probability

, while in turn producing significantly worse colourings than the recursive largest first algorithm.

External links

• 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)

Notes and References

1. Brélaz. Daniel. 1979-04-01. New methods to color the vertices of a graph. Communications of the ACM. 22. 4. 251–256. 10.1145/359094.359101. 14838769 . 0001-0782. free.
2. Book: Lewis, R.M.R.. A Guide to Graph Colouring: Algorithms and Applications. Texts in Computer Science . Springer. 2021. 978-3-030-81053-5. 2. Berlin. 10.1007/978-3-030-81054-2. 57188465 .
3. Book: Graph Colorings (Vol.352). American Mathematical Society. 2004. 978-0-8218-3458-9. Kubale. Providence. 13.
4. Web site: Constructive Algorithms for Graph Colouring. Lewis. Rhyd. 2019-01-19. youtube.com. 3:49.