Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
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)⌉≤bp(G)≤χ'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)≤(2+o(1))Δw(G), establishing the Chung--Ross conjecture [SICOMP'91] asymptotically. For loopless multigraphs, we obtain the exact bound χ'w(G)≤3⌈Δ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.
Related
- Density regions, integer certificates and packing colorings of distance graphs
- On S-packing total colorings
- Weighted odd-cycle transversals and fractional colorings of planar graphs
- On the geometry of asymptotically conical Ricci shrinkers (I): weighted analysis
- Optimal Kt-free list colorings and the Pollyanna property of graphs with no triangular wheel
BibTeX
@misc{gajjala2026asymptotically,
title = {{Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing}},
author = {Rishikesh Gajjala and Arindam Khan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.03190},
eprint = {2611.03190},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.03190},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing
AU - Rishikesh Gajjala
AU - Arindam Khan
PY - 2026
DA - 2026/11/02
PB - arXiv
DO - 10.48550/arxiv.2611.03190
UR - https://arxiv.org/abs/2611.03190
AB - 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)⌉≤bp(G)≤χ'_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)≤(2+o(1))Δ_w(G), establishing the Chung--Ross conjecture [SICOMP'91] asymptotically. For loopless multigraphs, we obtain the exact bound χ'_w(G)≤3⌈Δ_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.
ER -