DSATUR

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

• elements: data for the scripts
• nongraphical: naive solution
• graphical: graphical solution

References

All Graph Theory

• by Kevin Ly · DSATUR
• by Kiel Williams · Dijkstra