Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
math.CO, cs.DM, cs.DS
Submitted: 2026-11-02
Updated: 2026-11-02
Comments: 94 pages
Code: https://github.com/rishigajjala/weighted-edge-coloring-challenges
License: http://creativecommons.org/licenses/by/4.0/
The gist: We study weighted edge coloring, where each edge of a graph G has a weight in (0,1], and colors are assigned so that the incident weight of each color at every vertex is at most one.
Abstract
We study weighted edge coloring, where each edge of a graph G has a weight in (0,1], and colors are assigned so that the incident weight of each color at every vertex is at most one. The objective is to minimize the number of colors, denoted by χ'w(G). This generalizes classical edge coloring (all weights are one) and bin packing (G is a star). Two natural lower bounds are the maximum weighted degree Δ w(G) and the maximum local bin-packing number bp(G): the maximum, over vertices, of the minimum number of unit bins needed to pack the incident weights. We have Δ w(G) at most bp(G) at mostχ'w(G). How closely these local lower bounds approximate the global optimum is a longstanding open problem. Our main result establishes an asymptotic weighted analogue of Vizing's theorem: every simple graph admits a coloring using at most (1+o(1)) bp(G) colors. Thus local bin packings can be made globally consistent with asymptotically vanishing relative loss, even in nonbipartite graphs. Our local-to-global rounding framework coordinates feasible local packing distributions into a partial coloring, leaving only o(bp(G)) uncolored weight at every vertex. For bipartite multigraphs, we prove χ'w(G) at most(2+o(1))Δ w(G), establishing the Chung--Ross conjecture [SICOMP'91] asymptotically. For loopless multigraphs, we obtain the exact bound χ'w(G) at most3 Δ w(G). Both leading coefficients are optimal, giving weighted analogues of the classical Kőnig--Shannon bounds. Further upper and lower bounds show that the classical factor- 3/2 separation does not persist with the local bin-packing benchmark. We also disprove the exact weighted-degree conjecture of Feige and Singh [ESA'08]. Our upper bounds have polynomial-time algorithms, and their existence statements are formalized in Lean 4.
Sources
- Finding an almost perfect matching in a hypergraph avoiding forbidden submatchings
- The Moser-Tardos Framework with Partial Resampling
- Improved Approximation Algorithms for Weighted Edge Coloring of Graphs
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality