EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Vizing’s Theorem in Near-Linear Time

Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, Tianyi Zhang

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →