DSatur

DSatur
Class	Graph coloring
Worst-case space complexity	Ο(n2)

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

Pseudocode[]

Define the degree of saturation of a vertex as the number of different colours in its neighbourhood. Given a simple, undirected graph G compromising vertex set V and edge set E:^[4]

Generate a degree ordering of V.
Select a vertex of maximal degree and colour it with the first colour.
Consider a vertex with the highest degree of saturation. Break ties by considering that vertex with the highest degree. Further ties are broken randomly.
Loop through the colour classes created so far, and colour the selected vertex with the first suitable colour.
Unless V is all coloured, return to step 3

Performance[]

The worst-case complexity of DSatur is $O(n^{2})$ , where $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)$ where $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 $p=0.5$ , while in turn producing significantly worse colourings than the Recursive Largest First algorithm.^[2]

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

References[]

^ ^a ^b ^c ^d Brélaz, Daniel (1979-04-01). "New methods to color the vertices of a graph". Communications of the ACM. 22 (4): 251–256. doi:10.1145/359094.359101. ISSN 0001-0782.
^ ^a ^b ^c ^d ^e Lewis, R.M.R. (2021). A Guide to Graph Colouring: Algorithms and Applications (2 ed.). Berlin: Springer. doi:10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5.
^ Kubale, ed. (2004). Graph Colorings (Vol.352). Providence: American Mathematical Society. p. 13. ISBN 978-0-8218-3458-9.
^ Lewis, Rhyd (2019-01-19). "Constructive Algorithms for Graph Colouring". youtube.com. Event occurs at 3:49.

[:0-1] Brélaz, Daniel (1979-04-01). "New methods to color the vertices of a graph". Communications of the ACM. 22 (4): 251–256. doi:10.1145/359094.359101. ISSN 0001-0782.

[:1-2] Lewis, R.M.R. (2021). A Guide to Graph Colouring: Algorithms and Applications (2 ed.). Berlin: Springer. doi:10.1007/978-3-030-81054-2. ISBN 978-3-030-81053-5.

[3] Kubale, ed. (2004). Graph Colorings (Vol.352). Providence: American Mathematical Society. p. 13. ISBN 978-0-8218-3458-9.

[4] Lewis, Rhyd (2019-01-19). "Constructive Algorithms for Graph Colouring". youtube.com. Event occurs at 3:49.

[1]

[2]

[3]

[4]