Metraipolis › archive › dc_c71f3ef5694b

Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing — arXiv:2611.03190

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03190
License (as archived)
CC0-1.0
Archived
2026-11-03T11:37:39.997Z
SHA-256 of the archived text
70e99978b8edc6ef98fe191fbdbde4188ca4c16c7906fcf198ccd12419ab52b9
Stable URL of this page
https://metraipolis.com/documento/dc_c71f3ef5694b

How to cite

Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing — arXiv:2611.03190 — arXiv (en), https://arxiv.org/abs/2611.03190 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c71f3ef5694b (Metraipolis archive dc_c71f3ef5694b, sha256 70e99978b8edc6ef98fe191fbdbde4188ca4c16c7906fcf198ccd12419ab52b9)
BibTeX
@misc{dcc71f3ef5694b,
  title = {Asymptotically Optimal Weighted Edge Colorings via Local Bin Packing — arXiv:2611.03190},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03190},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c71f3ef5694b; sha256 70e99978b8edc6ef98fe191fbdbde4188ca4c16c7906fcf198ccd12419ab52b9},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03190. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\chi'_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 $\Delta_w(G)$ and the maximum local bin-packing number $\mathrm{bp}(G)$: the maximum, over vertices, of the minimum number of unit bins needed to pack the incident weights. We have $\lceil\Delta_w(G)\rceil\le\mathrm{bp}(G)\le\chi'_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))\mathrm{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(\mathrm{bp}(G))$ uncolored weight at every vertex. For bipartite multigraphs, we prove $\chi'_w(G)\le(2+o(1))\Delta_w(G)$, establishing the Chung--Ross conjecture [SICOMP'91] asymptotically. For loopless multigraphs, we obtain the exact bound $\chi'_w(G)\le3\lceil\Delta_w(G)\rceil$. 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.03190 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T11:05:22.315Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).