## Class SaturationDegreeColoring<V,​E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
VertexColoringAlgorithm<V>

public class SaturationDegreeColoring<V,​E>
extends Object
implements VertexColoringAlgorithm<V>
The Dsatur greedy coloring algorithm.

This is the greedy coloring algorithm using saturation degree ordering. The saturation degree of a vertex is defined as the number of different colors to which it is adjacent. The algorithm selects always the vertex with the largest saturation degree. If multiple vertices have the same maximum saturation degree, a vertex of maximum degree in the uncolored subgraph is selected.

Note that the DSatur is not optimal in general, but is optimal for bipartite graphs. Compared to other simpler greedy ordering heuristics, it is usually considered slower but more efficient w.r.t. the number of used colors. See the following papers for details:

• D. Brelaz. New methods to color the vertices of a graph. Communications of ACM, 22(4):251–256, 1979.
• The smallest hard-to-color graph for algorithm DSATUR. Discrete Mathematics, 236:151--165, 2001.

This implementation requires $O(n^2)$ running time and space. The following paper discusses possible improvements in the running time.

• J. S. Turner. Almost all $k$-colorable graphs are easy to color. Journal of Algorithms. 9(1):63--82, 1988.
Author:
Dimitrios Michail

• ### Nested classes/interfaces inherited from interface org.jgrapht.alg.interfaces.VertexColoringAlgorithm

VertexColoringAlgorithm.Coloring<V>, VertexColoringAlgorithm.ColoringImpl<V>
• ### Constructor Summary

Constructors
Constructor Description
SaturationDegreeColoring​(Graph<V,​E> graph)
Construct a new coloring algorithm.
• ### Method Summary

All Methods
Modifier and Type Method Description
VertexColoringAlgorithm.Coloring<V> getColoring()
Computes a vertex coloring.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### SaturationDegreeColoring

public SaturationDegreeColoring​(Graph<V,​E> graph)
Construct a new coloring algorithm.
Parameters:
graph - the input graph
• ### Method Detail

• #### getColoring

public VertexColoringAlgorithm.Coloring<V> getColoring()
Computes a vertex coloring.
Specified by:
getColoring in interface VertexColoringAlgorithm<V>
Returns:
a vertex coloring