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
