Skip to main content
`Ctrl`+`K`

# greedy_color

greedy_color(G, strategy='largest_first', interchange=False)

  Color a graph using various strategies of greedy graph coloring.

  Attempts to color a graph using as few colors as possible, where no neighbors 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)

      - `'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` 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.
  Raises:
    NetworkXPointlessConcept

      If `strategy` is `saturation_largest_first` or `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, Narsingh Deo, Janusz S. Kowalik, Discrete Optimization Algorithms with Pascal Programs, 415-424, 1983. ISBN 0-486-45353-7.

  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