← All problems

Weighted edge-coloring conjectures of Chung–Ross and Feige–Singh

For every bipartite multigraph G=(V,E)G=(V,E) with edge weights w:E→(0,1]w:E\to(0,1], let χw′(G)\chi'_w(G) be the minimum number of colors in an edge-coloring such that, for every vertex v∈Vv\in V and every color cc, ∑e∋v, col⁡(e)=cw(e)≤1\sum_{e\ni v,\,\operatorname{col}(e)=c}w(e)\le 1. For each vertex vv, let bp⁡v(G)\operatorname{bp}_v(G) be the minimum number of unit-capacity bins needed to pack the weights of the edges incident with vv, and set bp⁡(G)=max⁡v∈Vbp⁡v(G)\operatorname{bp}(G)=\max_{v\in V}\operatorname{bp}_v(G). The Chung–Ross conjecture asserts that χw′(G)≤2bp⁡(G)\chi'_w(G)\le 2\operatorname{bp}(G) for every such weighted bipartite multigraph.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 2.25n2.25n colors for bipartite graphs.
  • Feige and Singh (2008): non-bipartite examples require at least 2n2n colors, with examples approaching 3n3n.
  • Khan and Singh (2015): improved the bipartite bound to at most ⌈2.2223m⌉\lceil 2.2223m\rceil colors.

November 2026 preprint

Gajjala and Khan claim an asymptotically optimal bin-packing bound for simple graphs, a (2+o(1))Δw(2+o(1))\Delta_w 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.

Sources

Solutions 0

No solutions have been posted yet.