22 May 2025 – Martin Costa

Date: 22 May 2025
Time: 11:45 – 12:45
Location: Forschungslabor 3 (sofa room)

Speaker: Martin Costa
Title: Vizing’s Theorem in Near-Linear Time

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 Õ(mn^(1/2)) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985].

Very recently, this runtime bound was further improved to Õ(n^2) by [Assadi et al., 2024] and Õ(mn^(1/4)) by [Bhattacharya et al., 2024].

In this talk, I will 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.