Weighted edge-coloring conjectures of Chung–Ross and Feige–Singh
For every bipartite multigraph with edge weights , let be the minimum number of colors in an edge-coloring such that, for every vertex and every color , . For each vertex , let be the minimum number of unit-capacity bins needed to pack the weights of the edges incident with , and set . The Chung–Ross conjecture asserts that for every such weighted bipartite multigraph.
References
- Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing — arXiv — Rishikesh Gajjala, Arindam Khan
Source: arXiv
Progress summary
A new unrefereed preprint claims major weighted edge-coloring bounds and a counterexample to one conjecture, but these advances have not been independently verified.
The Chung–Ross and Feige–Singh conjectures concern coloring weighted bipartite graphs using bounds based on local bin-packing or weighted degree. Earlier work established only approximation bounds and showed that analogous statements fail for general non-bipartite multigraphs.
Known results
- Feige and Singh (2008): a polynomial-time coloring using at most colors for bipartite graphs.
- Feige and Singh (2008): non-bipartite examples require at least colors, with examples approaching .
- Khan and Singh (2015): improved the bipartite bound to at most colors.
November 2026 preprint
Gajjala and Khan claim an asymptotically optimal bin-packing bound for simple graphs, a bound for bipartite multigraphs, an exact factor-three bound for loopless multigraphs, and a counterexample to Feige–Singh’s exact weighted-degree conjecture. The claims are supported here only by an unrefereed preprint.
Current status (as of November 2026): Earlier partial bounds are established, while the new bounds and the claimed counterexample remain unverified; the conjectural picture is not independently settled.
Solutions 0
No solutions have been posted yet.