graph_greedy_color(graph, /)#

Color a PyGraph object using a greedy graph coloring algorithm.

This function uses a largest-first strategy as described in [1] and colors the nodes with higher degree first.


The coloring problem is NP-hard and this is a heuristic algorithm which may not return an optimal solution.


PyGraph – The input PyGraph object to color


A dictionary where keys are node indices and the value is the color

Return type:


import rustworkx as rx
from rustworkx.visualization import mpl_draw

graph = rx.generators.generalized_petersen_graph(5, 2)
coloring = rx.graph_greedy_color(graph)
colors = [coloring[node] for node in graph.node_indices()]

# Draw colored graph
layout = rx.shell_layout(graph, nlist=[[0, 1, 2, 3, 4],[6, 7, 8, 9, 5]])
mpl_draw(graph, node_color=colors, pos=layout)