Weighted bipartite edge colouring

Definitions and mathematical statement

Let $G=(U\sqcup W,E)$ be a finite bipartite graph with at least one edge, and give each edge a weight $w(e)\in[0,1]$. A weighted edge colouring assigns one colour $f(e)$ to every edge and is feasible when \[ \sum_{\substack{e\ni v\\f(e)=a}}w(e)\le1 \quad\text{for every vertex }v \text{ and colour }a. \] Adjacent edges may share a colour if their total load remains within this unit capacity.

For a vertex $v$, let $b_v$ be the minimum number of bins of capacity one needed to pack all its incident edge weights; each edge is one indivisible item. Put $b=\max_v b_v$. An isolated vertex has $b_v=0$, while a nonempty incident list needs at least one bin even if all its weights are zero.

Is there always a feasible weighted edge colouring using at most $2b-1$ colours? The empty-edge graph can be handled separately with zero colours.

The same colour on an edge must be used at both endpoints, so independent optimal bin packings at the vertices may be incompatible. Edges may not split their weights among colours. The lower bound $b$ is a local bin-packing bound, which can exceed the ceiling of the largest total incident weight; replacing it by that different quantity would change the conjecture.

Short English statement

Can every weighted bipartite graph be edge-coloured within unit load per colour at each vertex using at most twice the local bin-packing bound minus one?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000088 (AMR-029-0088), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Weighted bipartite edge colouring. Original source indexed by AMR-029-0088. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Weighted bipartite edge colouring. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Weighted_bipartite_edge_colouring.