Graph Coloring Visualization and Heuristics

As seen above, the DSatur Algorithm is a graph coloring heuristic algorithm which prioritises the non-colored vertex with the highest number of uniquely colored neighbors. This number is called the Degree of Saturation, which is where the algorithm gets its name from. The degree of saturation can be stored with each vertex and updated after every round, so the algorith takes quadratic time.

Below are some resources on DSatur:

• Geeks for Geeks article with simple example
• Good landing page for general graph coloring algorithms, by Parker J. Rule

The Recursive Largest First (RLF) Algorithm is a graph coloring heuristic algorithm which prioritises the largest independent set of vertices that has not been colored yet. However, identifying the largest independent set of a graph is NP-hard so the best results using this algorithm come from approximations.

Below are some resources on RLF:

• A new efficient RLF-like Algorithm for the Vertex Coloring Algorithm by Adegbindin, Hertz, Bellaïche
• Implementation by Duc Huy Nguyen

Equitable coloring is when we color a graph such that each color is used as equally as possible, while still minimizing the number of colors used. The size of color classes should differ by at most one.

Below are some resources on Equitable Coloring:

• A fast algorithm for equitable coloring by Kierstead, Kostochka, Mydlarz, and Szemerédi
• Equitable ∆-coloring of graphs by Chen and Hen

Unit Disk graphs are graphs of intersecting circles that are all the same size. Following along with the radio station application above, this would be the case if each radio station had the same broadcasting range. This restriction can have various implications on the coloring of the graph.

In Graph Coloring Algorithms, Matula, Marble, and Isaacson introduce a parameter which Gräf, Stumpf, and Weißenfels, in the paper listed below, call the span of a graph, which they define as the maximum number of edges that connect a vertex to vertices that come before it in the given ordering of a graph. Gräf, Stumpf, and Weißenfels go on to claim that a sequential coloring algorithm has the property that Chi(G) ≤ span(G)+1. They then mention that Peeters, in his paper listed below, shows that an ordering of the vertices of a UD graph has a span ≤ 3ω(G)-3, so it follows that "each UD graph G can be colored with at most 3ω(G)-2 colors in linear time."

Below are some resources on Unit Disk Coloring:

• On Coloring Unit Disk Graphs by Gräf, Stumpf, and Weißenfels
• On Coloring j-Unit Sphere Graphs by Peeters
• Simple Heuristics for Unit Disk Graphs by Marathe, Breu, Hunt III, Ravi, and Rosenkratz
• Distributed Coloring and the Local Structure of Unit-Disk Graphs by Esperet, Julliot, and de Mesmay
• Approximation Algorithms for Unit Disk Graphs by van Leeuwen