Welcome, guest | Sign In | My Account | Store | Cart

Konig's theorem tells us that every bipartite graph with maximum vertex-degree d can be edge-colored with just d colors. This recipe relies on a previous recipe by D.Eppstein (123641) : "Hopcroft-Karp bipartite matching".

Python, 30 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30``` ```from bipartite_recipe import bipartite_match def max_degree(graph): max_degree_u=max(len(v) for v in graph.values() ) count={} for vlist in graph.values(): for v in vlist: try: count[v]+=1 except KeyError: count[v]=1 max_degree_v=max(count.values()) return max(max_degree_v,max_degree_u) def best_match(graph): b_m=bipartiteMatch(graph) return dict((value,key) for (key,value) in b_m.items()) def edge_coloring(graph): g=graph.copy() number_colors=max_degree(g) for color in range(number_colors): print 'NEXT COLOR' bm=best_match(g) print bm for k in g.copy(): try: g[k].remove(bm[k]) except KeyError: pass graph={ 'p1':['c1','c3'], 'p2':['c1','c2'], 'p3':['c2','c3'], 'p4':['c2'] } edge_coloring(graph) ```

The algorithm presented here simply does the following two steps d times: 1-find the maximum cardinality matching using Hopcroft-Karp algorithm. All edges found get the same color assigned 2-delete the edges found above and goto 1

This algorithm is not optimal in terms of number of operations but it has the merit to exist in less than 20 lines (other algorithms are a real pain to implement ;-)) Created by Praveen on Thu, 30 Jul 2015 (PSF)