Fig. 2.9 from R.M.R. Lewis, "A Guide to Graph Colouring," Springer (2016).

by Kevin Ly

DSATUR

DSATUR (degree of saturation) is a heuristic, easy-to-follow algorithm for coloring simple graphs.

Presentation Summary

In these slides, I introduce the graph coloring problem and DSATUR. I also demo the Networkx package for Python for graphs and networks, which contains its own implementation of DSATUR (among many other algorithms!). I give an example in grouping names, with a naive solution, and then a graphical solution using DSATUR. Also included is the Mathematica notebook that I used to generate most of the graphs seen in my presentation.

Examples

References

All Graph Theory