Vizing’s theorem states that anyn-vertexm-edge graph of maximum degreeΔcan beedge coloredusing at mostΔ+ 1 different colors [Vizing, 1964]. Vizing’s original proof is algorithmic and shows that such an edge coloring can be found inO(mn) time. This was subsequently improved to\(\tilde{O}(m\sqrt {n}) \)time, independently by [Arjomandi, 1982] and by [Gabow etal., 1985]. 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 paper, we present a randomized algorithm that computes a (Δ+ 1)-edge coloring in near-linear time—in fact, onlyO(mlogΔ) time—with high probability,giving a near-optimal algorithm for this fundamental problem.
]]>