networkx.algorithms.coloring.greedy_color¶

greedy_color(G, strategy='largest_first', interchange=False)[source]¶

Color a graph using various strategies of greedy graph coloring.

Attempts to color a graph using as few colors as possible, where no neighbours of a node can have same color as the node itself. The given strategy determines the order in which nodes are colored.

The strategies are described in [1], and smallest-last is based on [2].

Parameters:

G (NetworkX graph)
strategy (string or function(G, colors)) – A function (or a string representing a function) that provides the coloring strategy, by returning nodes in the ordering they should be colored. G is the graph, and colors is a dictionary of the currently assigned colors, keyed by nodes. The function must return an iterable over all the nodes in G.

If the strategy function is an iterator generator (that is, a function with yield statements), keep in mind that the colors dictionary will be updated after each yield, since this function chooses colors greedily.

If strategy is a string, it must be one of the following, each of which represents one of the built-in strategy functions.
- 'largest_first'
- 'random_sequential'
- 'smallest_last'
- 'independent_set'
- 'connected_sequential_bfs'
- 'connected_sequential_dfs'
- 'connected_sequential' (alias for the previous strategy)
- 'strategy_saturation_largest_first'
- 'DSATUR' (alias for the previous strategy)
interchange (bool) – Will use the color interchange algorithm described by [3] if set to True.

Note that strategy_saturation_largest_first and strategy_independent_set do not work with interchange. Furthermore, if you use interchange with your own strategy function, you cannot rely on the values in the colors argument.

Returns:

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

Examples

>>> G = nx.cycle_graph(4)
>>> d = nx.coloring.greedy_color(G, strategy='largest_first')
>>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}]
True

Raises:	`NetworkXPointlessConcept` – If `strategy` is `strategy_saturation_largest_first` or `strategy_independent_set` and `interchange` is `True`.

References

[1]	Adrian Kosowski, and Krzysztof Manuszewski, Classical Coloring of Graphs, Graph Colorings, 2-19, 2004. ISBN 0-8218-3458-4.

[2]	David W. Matula, and Leland L. Beck, “Smallest-last ordering and clustering and graph coloring algorithms.” J. ACM 30, 3 (July 1983), 417–427. <https://doi.org/10.1145/2402.322385>

[3]	Maciej M. Sysło, Marsingh Deo, Janusz S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983. ISBN 0-486-45353-7.