{"ID":2855810,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.12619","arxiv_id":"2510.12619","title":"Vizing's Theorem in Deterministic Almost-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'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.","short_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, ind...","url_abs":"https://arxiv.org/abs/2510.12619","url_pdf":"https://arxiv.org/pdf/2510.12619v2","authors":"[\"Sepehr Assadi\",\"Soheil Behnezhad\",\"Sayan Bhattacharya\",\"Martín Costa\",\"Shay Solomon\",\"Tianyi Zhang\"]","published":"2025-10-14T15:18:01Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}