2025/10/14 by Sepehr Assadi, Assadi, Sepehr, Soheil Behnezhad +9
Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Matrix Theory and Algorithms #advanced mathematical theories
paper · pdf · doi:10.48550/arxiv.2510.12619
openalex publication_date 2025/10/14 · openalex created_date 2025/10/17 · openalex updated_date 2026/07/28
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's original proof is easily translated into a deterministic O(mn) time algorithm. This deterministic time bound was subsequently improved to O(m √ n) time, independently by [Arjomandi, 1982] and by [Gabow et al., 1985]. A series of recent papers improved the time bound of O(m√(n)) using randomization, culminating in the randomized near-linear time (Δ+1)-coloring algorithm by [Assadi, Behnezhad, Bhattacharya, Costa, Solomon, and Zhang, 2025]. At the heart of all of these recent improvements, there is some form of a sublinear time algorithm. Unfortunately, sublinear time algorithms as a whole almost always require randomization. This raises a natural question: can the deterministic time complexity of the problem be reduced below the O(m√(n)) barrier? In this paper, we answer this question in the affirmative. We present a deterministic almost-linear time (Δ+1)-coloring algorithm, namely, an algorithm running in m ⋅ 2O(√(log Δ)) ⋅ log n = m1+o(1) time. Our main technical contribution is to entirely forego sublinear time algorithms. We do so by presenting a new deterministic color-type sparsification approach that runs in almost-linear (instead of sublinear) time, but can be used to color a much larger set of edges.