Edge Coloring of Multigraphs With Very High Multiplicities
Networks · 2026-09 · 88 (2) · 275-290
DOI: 10.1002/net.70054 ↗At a glance
Journal article in Networks, published online on 2026-06-15. Written by Jan De Neve and 3 co-authors. 24 references. Funded by: Bijzonder Onderzoeksfonds UGent.
Abstract (original language)
Vizing's generalized theorem states that any multigraph with maximum degree and maximum multiplicity has an edge coloring with at most colors. The runtime of Vizing's algorithm, which can find such a coloring, scales quadratically with . This is an important drawback for multigraphs arising from applications like photonic networks, where edge degrees and multiplicities can be very high. In this work, we propose a new edge coloring algorithm for multigraphs, which scales linearly with . To the best of our knowledge, no existing edge coloring algorithm, using so few colors, scales less than quadratically with . We describe one algorithm that finds a near‐optimal coloring and another algorithm that finds an optimal coloring with and worst‐case time complexity, respectively. We verify the working mechanisms as well as the performance of these algorithms, both for purely random test inputs and for synthetic test inputs whose structure is based on real applications.
Funding
- Bijzonder Onderzoeksfonds UGent
Cite
APA
Neve, J. D., Colle, D., Tavernier, W., & Pickavet, M. (2026). Edge Coloring of Multigraphs With Very High Multiplicities. Networks, 88(2), 275-290. https://doi.org/10.1002/net.70054
Vancouver
Neve JD, Colle D, Tavernier W, Pickavet M. Edge Coloring of Multigraphs With Very High Multiplicities. Networks. 2026;88(2):275-290. doi:10.1002/net.70054
BibTeX
@article{Neve2026,
author = {Neve, Jan De and Colle, Didier and Tavernier, Wouter and Pickavet, Mario},
title = {Edge Coloring of Multigraphs With Very High Multiplicities},
journal = {Networks},
year = {2026},
volume = {88},
number = {2},
pages = {275--290},
doi = {10.1002/net.70054}
}
EUVIMED