Coloring¶

Algorithms¶

The following algorithms are available:

jgrapht.algorithms.coloring.backtracking_brown(graph)[source]¶

Brown backtracking graph coloring algorithm.

Parameters: graph – The input graph. Either directed or undirected.
Returns: A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.

jgrapht.algorithms.coloring.chordal_min_coloring(graph)[source]¶

Find a minimum vertex coloring for a chordal graph.

The algorithms first computes a perfect elimination ordering and then a vertex coloring. Running time $\mathcal{O}(n+m)$.

Parameters: graph – the chordal graph. If the graph is not chordal an error is raised
Returns: A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.

jgrapht.algorithms.coloring.color_refinement(graph)[source]¶

Color refinement algorithm. Finds the coarsest stable coloring of a graph based on a given $\alpha$ coloring as described in the following paper:

C. Berkholz, P. Bonsma, and M. Grohe. Tight lower and upper bounds for the complexity of canonical colour refinement. Theory of Computing Systems, 60(4), p581–614, 2017.

The complexity of this algorithm is $\mathcal{O}((n + m) \log n)$.

Parameters: graph – The input graph. Either directed or undirected.
Returns: A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.

jgrapht.algorithms.coloring.greedy_dsatur(graph)[source]¶

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:

1. 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 $\mathcal{O}(n^2)$ running time and space. The following paper discusses possible improvements in the running time.

1. 1. Turner. Almost all $k$-colorable graphs are easy to color. Journal of Algorithms. 9(1):63–82, 1988.

Parameters: graph – The input graph. Either directed or undirected.
Returns: A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.

jgrapht.algorithms.coloring.greedy_largestdegreefirst(graph)[source]¶

The largest degree first greedy coloring algorithm.

This is the greedy coloring algorithm which orders the vertices by non-increasing degree. See the following paper for details.

D. J. A. Welsh and M. B. Powell. An upper bound for the chromatic number of a graph and its application to timetabling problems. The Computer Journal, 10(1):85–86, 1967.

Parameters: graph – The input graph. Either directed or undirected.
Returns: A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.

jgrapht.algorithms.coloring.greedy_random(graph, seed=None)[source]¶

The greedy coloring algorithm with a random vertex ordering.

Parameters

graph – The input graph. Either directed or undirected.
seed – Seed for the random number generator. If None then the time is used to select a seed.

Returns

A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.

jgrapht.algorithms.coloring.greedy_smallestdegreelast(graph)[source]¶

The smallest degree last greedy coloring algorithm.

This is the greedy coloring algorithm with the smallest-last ordering of the vertices. The basic idea is as follows: Assuming that vertices $v_{k+1}, \dotso, v_n$ have been already selected, choose $v_k$ so that the degree of $v_k$ in the subgraph induced by $V - $(v_{k+1}, \dotso, v_n)$ is minimal. See the following paper for details.

D. Matula, G. Marble, and J. Isaacson. Graph coloring algorithms in Graph Theory and Computing. Academic Press, 104–122, 1972.

Parameters: graph – The input graph. Either directed or undirected.
Returns: A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.

jgrapht.algorithms.coloring.greedy_smallestnotusedcolor(graph)[source]¶

The greedy coloring algorithm.

The algorithm iterates over all vertices and assigns the smallest possible color that is not used by any neighbors. Subclasses may provide a different vertex ordering.

Parameters: graph – The input graph. Either directed or undirected.
Returns: A vertex coloring as a tuple. First component is the number of colors, second is a dictionary from vertices to integers.