Vizing's Theorem in Near-Linear Time

2024/10/07 by Sepehr Assadi, Assadi, Sepehr, Soheil Behnezhad +9 · 1 voice · 3 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.DS

paper · pdf · doi:10.48550/arxiv.2410.05240

arxiv published 2024/10/07 · arxiv updated 2025/10/14

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 O(m√(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 O(n²) by [Assadi, 2024] and O(mn^1/3) by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to O(mn^1/4) time 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.

Cited by

• Vizing's Theorem in Deterministic Almost-Linear Time
• Flipping odd matchings in geometric and combinatorial settings
• Online Edge Coloring: Sharp Thresholds

Discussions

• Vizing's Theorem in Near-Linear Time. Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martin Costa, Shay Solomon, Tianyi Zhang. (Δ+1)-edge colorings in degree-Δ graphs in time O(m log Δ): enough [bsky, 4 points, 1 comments]

Related

• Faster Vizing and Near-Vizing Edge Coloring Algorithms
• Vizing's Theorem in Deterministic Almost-Linear Time
• Faster (Δ+ 1)-Edge Coloring: Breaking the m √(n) Time Barrier
• Even Faster (Δ+ 1)-Edge Coloring via Shorter Multi-Step Vizing Chains
• Fast algorithms for Vizing's theorem on bounded degree graphs