Vizing's Theorem in Near-Linear Time
OPEN ACCESS
Loading...
Author / Producer
Date
2025-06
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
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.
Permanent link
Publication status
published
External links
Book title
STOC '25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
Journal / series
Volume
Pages / Article No.
24 - 35
Publisher
Association for Computing Machinery
Event
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Edge Coloring; Vizing’s Theorem
Organisational unit
Notes
Funding
218022 - A New Paradigm for Flow and Cut Algorithms (SNF)