equitable_color(G, num_colors)[source]#

Provides an equitable coloring for nodes of G.

Attempts to color a graph using num_colors 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. num_colors must be greater than the maximum degree of G. The algorithm is described in [1] and has complexity O(num_colors * n**2).

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.

A dictionary with keys representing nodes and values representing
corresponding coloring.

If num_colors is not at least the maximum degree of the graph G



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


>>> G = nx.cycle_graph(4)
>>> nx.coloring.equitable_color(G, num_colors=3)  
{0: 2, 1: 1, 2: 2, 3: 0}