rustworkx.graph_misra_gries_edge_color

graph_misra_gries_edge_color(graph, /)

Color edges of a PyGraph object using the Misra-Gries edge coloring algorithm..

Based on the paper: “A constructive proof of Vizing’s theorem” by Misra and Gries, 1992. <https://www.cs.utexas.edu/users/misra/psp.dir/vizing.pdf>

The coloring produces at most d + 1 colors where d is the maximum degree of the graph.

Parameters:

PyGraph – The input PyGraph object to edge-color

Returns:

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

Return type:

dict

import rustworkx as rx

graph = rx.generators.cycle_graph(7)
edge_colors = rx.graph_misra_gries_edge_color(graph)
assert edge_colors == {0: 0, 1: 1, 2: 2, 3: 0, 4: 1, 5: 0, 6: 2}