Vizing’s Theorem in Near-Linear Time
Journal of the ACM · 30.06.2026 · 73 (3) · 1-53
DOI: 10.1145/3806392 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of the ACM, online erschienen am 16.06.2026. Verfasst von Sepehr Assadi und 5 weiteren Autor:innen. Die Arbeit nennt 57 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Sloan Research Fellowship, NSERC Discovery Grant, Faculty of Math Research Chair grant from University of Waterloo.
Abstract (Originalsprache)
Vizing’s theorem states that any n -vertex m -edge graph of maximum degree Δ can be edge colored using at most Δ + 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found in O(mn) time. This was subsequently improved to \(\tilde{O}(m\sqrt {n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. 1 Very recently, independently and concurrently, using randomization, this runtime bound was further improved to \(\tilde{O}(n^2)\) by [Assadi, 2024] and \(\tilde{O}(mn^{1/3})\) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to \(\tilde{O}(mn^{1/4})\) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this article, we present a randomized algorithm that computes a Δ + 1-edge coloring in near-linear time—in fact, only O(m log Δ) time—with high probability, giving a near-optimal algorithm for this fundamental problem .
Förderung
- Sloan Research Fellowship
- NSERC Discovery Grant
- Faculty of Math Research Chair grant from University of Waterloo
- NSF CAREER
- Google Faculty Research Award
- Google PhD Fellowship
- European Union
- United States-Israel Binational Science Foundation
Zitieren
APA
Assadi, S., Behnezhad, S., Bhattacharya, S., Costa, M., Solomon, S., & Zhang, T. (2026). Vizing’s Theorem in Near-Linear Time. Journal of the ACM, 73(3), 1-53. https://doi.org/10.1145/3806392
Vancouver
Assadi S, Behnezhad S, Bhattacharya S, Costa M, Solomon S, Zhang T. Vizing’s Theorem in Near-Linear Time. Journal of the ACM. 2026;73(3):1-53. doi:10.1145/3806392
BibTeX
@article{Assadi2026,
author = {Assadi, Sepehr and Behnezhad, Soheil and Bhattacharya, Sayan and Costa, Martin and Solomon, Shay and Zhang, Tianyi},
title = {Vizing’s Theorem in Near-Linear Time},
journal = {Journal of the ACM},
year = {2026},
volume = {73},
number = {3},
pages = {1--53},
doi = {10.1145/3806392}
}
EUVIMED