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). <>

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.


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


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

Return type: