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 smallestlast 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, andcolors
is a dictionary of the currently assigned colors, keyed by nodes. The function must return an iterable over all the nodes inG
.If the strategy function is an iterator generator (that is, a function with
yield
statements), keep in mind that thecolors
dictionary will be updated after eachyield
, 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 builtin 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
andstrategy_independent_set
do not work with interchange. Furthermore, if you use interchange with your own strategy function, you cannot rely on the values in thecolors
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
– Ifstrategy
isstrategy_saturation_largest_first
orstrategy_independent_set
andinterchange
isTrue
.References
[1] Adrian Kosowski, and Krzysztof Manuszewski, Classical Coloring of Graphs, Graph Colorings, 219, 2004. ISBN 0821834584. [2] David W. Matula, and Leland L. Beck, “Smallestlast 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, 415424, 1983. ISBN 0486453537.