equitable_color#
- 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 ofG
. The algorithm is described in [1] and has complexity O(num_colors * n**2).- 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
num_colors
is not at least the maximum degree of the graphG
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) >>> nx.coloring.equitable_color(G, num_colors=3) {0: 2, 1: 1, 2: 2, 3: 0}