Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

networkx.algorithms.coloring.equitable_color

equitable_color(G, num_colors)[source]

Provides equitable (r + 1)-coloring for nodes of G in O(r * n^2) time if deg(G) <= r. The algorithm is described in [1].

Attempts to color a graph using r colors, where no neighbors of a node can have same color as the node itself and the number of nodes with each color differ by at most 1.

Parameters
GnetworkX graph

The nodes of this graph will be colored.

num_colorsnumber of colors to use

This number must be at least one more than the maximum degree of nodes in the graph.

Returns
A dictionary with keys representing nodes and values representing
corresponding coloring.
Raises
NetworkXAlgorithmError

If the maximum degree of the graph G is greater than num_colors.

References

1

Kierstead, H. A., Kostochka, A. V., Mydlarz, M., & Szemerédi, E. (2010). A fast algorithm for equitable coloring. Combinatorica, 30(2), 217-224.

Examples

>>> G = nx.cycle_graph(4)
>>> d = nx.coloring.equitable_color(G, num_colors=3)
>>> nx.algorithms.coloring.equitable_coloring.is_equitable(G, d)
True