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)'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
saturation_largest_first
andindependent_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 – If
strategy
issaturation_largest_first
orindependent_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.