# Weighted bipartite edge colouring

From Egres Open

Let *G=(S,T;E)* be a bipartite graph, with weights [math]w:E \to [0,1][/math]. A **proper weighted edge colouring** is a colouring of the edges such that at each vertex, the sum of weights of edges of the same colour is at most 1. A lower bound for the number of colours is the minimum number of unit bins needed to pack the weights incident to any vertex, denoted by *b*. Is there always a proper weighted edge colouring using [math]2b-1[/math] colours?

## Remarks

This conjecture was proposed by Chung and Ross ^{[1]}. The best currently known bound is [math]20 b / 9 + o(b) [/math] by Khan and Singh ^{[2]}.

## References

- ↑ S.-P. Chung, K.W. Ross,
*On nonblocking multirate interconnection networks*, SIAM Journal on Computing, 20(4):726–736, 1991, DOI link - ↑ A. Khan, M. Singh,
*On Weighted Bipartite Edge Coloring*, Dagstuhl link