9.25

Minimum edge–coloring of a bipartite graph

Theorem (Kőnig’s line-coloring): In every bipartite graph G=(U∪V,E) the minimum number of colors needed to color edges so that no two incident edges share a color (the chromatic index χ′(G)) equals the maximum vertex degree Δ(G).

Idea: We iteratively remove a maximum matching. A matching puts at most one edge on every vertex, so each chosen matching can safely receive a single new color. After at most Δ(G) iterations all edges are colored.

Pseudocode (Hopcroft–Karp is used for maximum matching and runs in O(E√V)):

EdgeColor(G): Δ ← max degree of G color ← 1 while E(G) ≠ ∅: M ← MaximumMatching(G) # Hopcroft–Karp for each edge e in M: assign color(e) ← color delete e from G color ← color + 1

Because every round removes at least one edge from every still-saturated vertex, the loop executes ≤ Δ times, giving time complexity O(Δ·E√V) and exactly Δ colors—provably optimal.

Reference implementation (Python 3):

from collections import deque,defaultdict def hopcroft_karp(adj,U,V): """adj[u] = {v,…} for bipartite sets U,V""" pair_u={u:None for u in U}; pair_v={v:None for v in V} INF=len(U)+len(V)+1 def bfs(): dist={} Q=deque() for u in U: if pair_u[u] is None: dist[u]=0; Q.append(u) d=INF while Q: u=Q.popleft() if dist[u] The function edge_coloring_bipartite returns an optimal Δ-edge coloring for any bipartite input graph, concretely realizing the algorithm described above.

Back to Chapter 9