Note
This documents the development version of NetworkX. Documentation for the current release can be found here.
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
 GNetworkX graph
 strategystring 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.
 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.
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