Vizing’s Theorem in Deterministic Almost-Linear Time

Society for Industrial and Applied Mathematics eBooks 2026

View at publisher
Authors: Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang
DOI: 10.1137/1.9781611978971.198
Cited by: 0

Abstract

Vizing’s theorem states that any \(n\)-vertex \(m\)-edge graph of maximum degree \(\Delta\) can be edge colored using at most \(\Delta + 1\) different colors. Vizing’s original proof is easily translated into a deterministic \(O(mn)\) time algorithm. This deterministic time bound was subsequently improved to \(\tilde{O}(m\sqrt{n})\) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Fields of Study & Subjects

Advanced Graph Theory Research Complexity and Algorithms in Graphs Limits and Structures in Graph Theory

Publication details

Journal / source
Society for Industrial and Applied Mathematics eBooks
Pages
5558–5585
Publication date
1 January 2026
Language
EN