rustworkx.graph_bipartite_edge_color

graph_bipartite_edge_color(graph, /)

Color edges of a graph by checking whether the graph is bipartite, and if so, calling the algorithm for edge-coloring bipartite graphs.

If the input graph is not bipartite, None is returned.

The implementation is based on the following paper:

Noga Alon. “A simple algorithm for edge-coloring bipartite multigraphs”. Inf. Process. Lett. 85(6), (2003). <https://www.tau.ac.il/~nogaa/PDFS/lex2.pdf>

The algorithm runs in time O (n + m log m), where n is the number of vertices and m is the number of edges of the graph.

Parameters:

graph (PyGraph) – The graph to find the coloring for

Returns:

A dictionary where keys are edge indices and the value is the color (provided that the graph is bipartite)

Return type:

dict