Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains

Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang

Abstract

Vizing's Theorem from 1964 states that any $n$-vertex $m$-edge graph with maximum degree $\Delta$ can be edge colored using at most $\Delta + 1$ colors. For over 40 years, the state-of-the-art running time for computing such a coloring was $\tilde O(m\sqrt{n})$. Very recently, this time bound was improved in two independent works to $\tilde O(mn^{1/3})$ and $\tilde O(n^2)$. In this paper, we present an algorithm that computes such a coloring in $\tilde O(mn^{1/4})$ time. Our key technical contribution is a subroutine for extending the coloring to one more edge within time $\tilde O(\Delta^2 + \sqrt{\Delta n})$. Our color extension subroutine produces significantly shorter multi-step Vizing chains than in previous works, for sufficiently large $\Delta$.

Introduction

Edge coloring is a fundamental problem in graph theory and combinatorial optimization. The goal is to assign colors to the edges of a graph such that no two edges incident to the same vertex share a color. According to Vizing's Theorem, every graph with maximum degree $\Delta$ can be colored using either $\Delta$ or $\Delta + 1$ colors. While determining if $\Delta$ colors suffice is NP-hard, finding a $(\Delta + 1)$-coloring is known to be in P.

Despite its long history, the algorithmic complexity of $(\Delta + 1)$-edge coloring remained stagnant for decades, with the $O(m\sqrt{n})$ bound established in the early 1980s serving as the benchmark. Recent breakthroughs have finally broken this barrier, and this paper continues that momentum by introducing a randomized algorithm that achieves a complexity of $\tilde{O}(mn^{1/4})$.

The Color Extension Challenge

The standard approach to edge coloring involves starting with an empty set and iteratively adding edges to the partial coloring. The difficulty lies in "color extension": when an edge $(u, v)$ needs to be colored, there might not be a color available at both $u$ and $v$. To resolve this, algorithms use Vizing chains—sequences of color swaps along paths of alternating colors—to shift the available colors until the target edge can be accommodated.

In recent years, researchers have moved toward "multi-step" Vizing chains, which are concatenations of several carefully chosen chains. However, previous constructions of these multi-step chains were extremely long, leading to a color extension time of $\tilde{O}(\Delta^6)$. This paper’s primary innovation is a method to generate significantly shorter multi-step chains, reducing the extension time to $\tilde{O}(\Delta^2 + \sqrt{\Delta n})$.

Algorithmic Framework

The proposed algorithm utilizes a "win-win" framework that integrates several advanced techniques:

1. Eulerian Partitioning

The algorithm uses Eulerian partitioning to recursively decompose the graph into smaller subgraphs with lower maximum degrees. This standard technique allows the problem to be solved on more manageable components before being recombined.

2. Star Coloring and Vertex Covers

To handle the initial stages of coloring, the authors use a randomized vertex cover approach to identify a small set of "problematic" vertices. They apply a specialized subroutine to efficiently color "stars" (sets of edges incident to specific vertices) when those vertices have a high density of available colors.

3. Truncated Multi-Step Vizing Chains

This is the core technical contribution. The algorithm attempts to find a short path to color an edge. If a path becomes too long, the algorithm "truncates" the search and tries a different random path. This ensures that the computational work performed per edge remains bounded. By forcing the algorithm to avoid long, inefficient chains, the authors prove that the total time spent on color extension is drastically reduced.

4. Meta-Tree Analysis

To prove that this randomized approach terminates quickly, the authors model the algorithm's execution as a random walk on a "meta-tree." In this theoretical structure, each node represents a state of the partial coloring. The authors demonstrate that this random walk is highly likely to reach a "terminal" state—representing a complete and valid coloring—in a small number of steps.

Key Results and Complexity

The primary result is a randomized algorithm that computes a $(\Delta + 1)$-edge coloring in $\tilde{O}(mn^{1/4})$ time with high probability. This represents a significant polynomial improvement over the previous state-of-the-art $\tilde{O}(mn^{1/3})$ for general graph parameters.

The speedup is driven by the new color extension subroutine, which runs in $\tilde{O}(\Delta^2 + \sqrt{\Delta n})$. This is a massive improvement over the $\tilde{O}(\Delta^6)$ bound found in earlier multi-step Vizing chain implementations.

Discussion and Future Work

While the $\tilde{O}(mn^{1/4})$ bound is a major step forward, several questions remain. The algorithm is randomized; developing a deterministic version with comparable performance is a significant open challenge. Furthermore, while this algorithm is faster for many regimes, a concurrent work (ABB+24) has proposed an $O(m \log \Delta)$ approach using different techniques, suggesting that the ultimate limit for this problem may be near-linear time.

Finally, the benefits of the shorter multi-step Vizing chains are most pronounced when $\Delta$ is large. For very sparse graphs, the improvements are less dramatic, though the overall complexity remains a new theoretical benchmark for the field.

Summary updated

Abstract

Vizing's Theorem from 1964 states that any $n$-vertex $m$-edge graph with maximum degree $\Delta$ can be {\em edge colored} using at most $\Delta + 1$ colors. For over 40 years, the state-of-the-art running time for computing such a coloring, obtained independently by Arjomandi [1982] and by Gabow, Nishizeki, Kariv, Leven and Terada~[1985], was $\tilde O(m\sqrt{n})$. Very recently, this time bound was improved in two independent works, by Bhattacharya, Carmon, Costa, Solomon and Zhang to $\tilde O(mn^{1/3})$, and by Assadi to $\tilde O(n^2)$. In this paper we present an algorithm that computes such a coloring in $\tilde O(mn^{1/4})$ time. Our key technical contribution is a subroutine for extending the coloring to one more edge within time $\tilde O(\Delta^2 + \sqrt{\Delta n})$. The best previous time bound of any color extension subroutine is either the trivial $O(n)$, dominated by the length of a Vizing chain, or the bound $\tilde{O}(\Delta^6)$ by Bernshteyn [2022], dominated by the length of {\em multi-step Vizing chains}, which is basically a concatenation of multiple (carefully chosen) Vizing chains. Our color extension subroutine produces significantly shorter multi-step Vizing chains than in previous works, for sufficiently large $\Delta$.
BibTeX
@inproceedings{bhattacharya2025even,
  author = {Sayan Bhattacharya and Martín Costa and Shay Solomon and Tianyi Zhang},
  title = {{Even Faster (Δ + 1)-Edge Coloring via Shorter Multi-Step Vizing Chains}},
  booktitle = {SODA},
  year = {2025},
  url = {https://openreview.net/forum?id=EuTrw6jEiG},
}
Figure