Coloring

greedy_color(G[, strategy, interchange])

Color a graph using various strategies of greedy graph coloring.

equitable_color(G, num_colors)

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

Some node ordering strategies are provided for use with greedy_color().

strategy_connected_sequential(G, colors[, …])

Returns an iterable over nodes in G in the order given by a breadth-first or depth-first traversal.

strategy_connected_sequential_dfs(G, colors)

Returns an iterable over nodes in G in the order given by a depth-first traversal.

strategy_connected_sequential_bfs(G, colors)

Returns an iterable over nodes in G in the order given by a breadth-first traversal.

strategy_independent_set(G, colors)

Uses a greedy independent set removal strategy to determine the colors.

strategy_largest_first(G, colors)

Returns a list of the nodes of G in decreasing order by degree.

strategy_random_sequential(G, colors[, seed])

Returns a random permutation of the nodes of G as a list.

strategy_saturation_largest_first(G, colors)

Iterates over all the nodes of G in “saturation order” (also known as “DSATUR”).

strategy_smallest_last(G, colors)

Returns a deque of the nodes of G, “smallest” last.