Vizing’s Theorem in Near-Linear Time
Vizing’s Theorem in Near-Linear Time
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 Õ(m$\sqrt{n}$) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. Very recently, independently and concurrently, using randomization, this runtime bound was further improved to Õ(n$^2$) by [Assadi, 2024] and Õ(mn$^{1/3}$) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to Õ(mn$^{1/4}$) by [Bhattacharya, Costa, Solomon and Zhang, 2024]). In this paper, we present a randomized algorithm that computes a (Δ +1)-edge coloring in near-linear time - in fact, only O(mlogΔ) time - with high probability, giving a near-optimal algorithm for this fundamental problem.
STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
ISBN:979-8-4007-1510-5
- University of Warwick United Kingdom
- ETH Zurich Switzerland
- University of Waterloo Canada
- Tel Aviv University Israel
- Northwestern University United States
FOS: Computer and information sciences, Vizing’s Theorem, Data Structures and Algorithms, Edge Coloring; Vizing’s Theorem, Edge Coloring, Data Structures and Algorithms (cs.DS)
FOS: Computer and information sciences, Vizing’s Theorem, Data Structures and Algorithms, Edge Coloring; Vizing’s Theorem, Edge Coloring, Data Structures and Algorithms (cs.DS)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!