Package org.jgrapht.alg.color

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 java.lang.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