Update: This is now merged into networkx package (via networkx/#3127). See networkx.algorithms.coloring.equitable_color.

docs
tests
package

Equitable coloring for networkX graphs.

From Wikipedia:

In graph theory [..] an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

• No two adjacent vertices have the same color, and
• The numbers of vertices in any two color classes differ by at most one.

Kierstead et. al. have provided a fast polynomial time algorithm for uncovering an equitable coloring using r + 1 colors for a graph with maximum degree r. This package is an implementation of the algorithm for networkX graphs.

• Free software: MIT license

pip install equitable-coloring

To use equitable-coloring:

>>> import networkx as nx
>>> from equitable_coloring import equitable_color
>>> from equitable_coloring.utils import is_equitable
>>> G = nx.cycle_graph(4)
>>> d = equitable_color(G, num_colors=3)
>>> is_equitable(G, d)
True

https://equitable-coloring.readthedocs.io/

To run the all tests run:

pip install pytest-cov  # Needed the first time.
python setup.py test

Or, you can use tox.