greedy_color¶

greedy_color
(G, strategy=<function strategy_largest_first>, interchange=False)[source]¶ Color a graph using various strategies of greedy graph coloring. The strategies are described in [1].
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.
Parameters:  G (NetworkX graph) –
 strategy (function(G, colors)) –
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 dict of the currently assigned colors, keyed by nodes.
You can pass your own ordering function, or use one of the built in:
 strategy_largest_first
 strategy_random_sequential
 strategy_smallest_last
 strategy_independent_set
 strategy_connected_sequential_bfs
 strategy_connected_sequential_dfs
 strategy_connected_sequential (alias of strategy_connected_sequential_bfs)
 strategy_saturation_largest_first (also known as DSATUR)
 interchange (bool) –
Will use the color interchange algorithm described by [2] if set to true.
Note that saturation largest first and 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=nx.coloring.strategy_largest_first) >>> d in [{0: 0, 1: 1, 2: 0, 3: 1}, {0: 1, 1: 0, 2: 1, 3: 0}] True
References
[1] Adrian Kosowski, and Krzysztof Manuszewski, Classical Coloring of Graphs, Graph Colorings, 219, 2004. ISBN 0821834584. [2] Maciej M. Syslo, Marsingh Deo, Janusz S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, 415424, 1983. ISBN 0486453537.