7.9.9. networkx.algorithms.coloring.strategy_smallest_last¶

networkx.algorithms.coloring.strategy_smallest_last(G, colors)[source]¶

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

Specifically, the node of minimum degree is repeatedly popped from the graph, then this order is reversed.

G is a NetworkX graph. colors is ignored.

This implementation of the strategy runs in O(n^2) time.

This strategy is related to strategy_independent_set(): if we interpret each node removed as an independent set of size one, then this strategy chooses an independent set of size one instead of a maximal independent set.