# Vizing's Theorem in Deterministic Almost-Linear Time

Preprint · Sepehr Assadi, Soheil Behnezhad, Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang

- Archive id: arxiv:2510.12619
- Published: 2025-10-14
- arXiv: https://arxiv.org/abs/2510.12619
- Source URL: https://arxiv.org/abs/2510.12619
- PDF: https://arxiv.org/pdf/2510.12619
- Provenance: arxiv

## 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's original proof is easily translated into a deterministic $O(mn)$ time algorithm. This deterministic time bound was subsequently improved to $\\tilde O(m \\sqrt n)$ time, independently by \[Arjomandi, 1982\] and by \[Gabow et al., 1985\]. A series of recent papers improved the time bound of $\\tilde O(m\\sqrt{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 $\\tilde O(m\\sqrt{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 \\cdot 2^{O(\\sqrt{\\log Δ})} \\cdot \\log n = m^{1+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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.