Density-Sensitive Algorithms for $(\Delta +1)$-Edge Coloring

Abstract

Vizing's theorem asserts the existence of a $(\Delta +1)$-edge coloring for any graph $G$, where $\Delta =\Delta (G)$ denotes the maximum degree of $G$. Several polynomial time $(\Delta +1)$-edge coloring algorithms are known, and the state-of-the-art running time (up to polylogarithmic factors) is $\tilde{O}(\min \{m\cdot \sqrt{n},m\cdot \Delta \})$, by Gabow et al.\ from 1985, where $n$ and $m$ denote the number of vertices and edges in the graph, respectively. (The $\tilde{O}$ notation suppresses polylogarithmic factors.) Recently, Sinnamon shaved off a polylogarithmic factor from the time bound of Gabow et al. The {arboricity} $\alpha =\alpha (G)$ of a graph $G$ is the minimum number of edge-disjoint forests into which its edge set can be partitioned, and it is a measure of the graph's "uniform density". While $\alpha \le \Delta$ in any graph, many natural and real-world graphs exhibit a significant separation between $\alpha$ and $\Delta$. In this work we design a $(\Delta +1)$-edge coloring algorithm with a running time of $\tilde{O}(\min \{m\cdot \sqrt{n},m\cdot \Delta \})\cdot \frac{\alpha }{\Delta }$, thus improving the longstanding time barrier by a factor of $\frac{\alpha }{\Delta }$. In particular, we achieve a near-linear runtime for bounded arboricity graphs (i.e., $\alpha =\tilde{O}(1)$) as well as when $\alpha =\tilde{O}(\frac{\Delta }{\sqrt{n}})$. Our algorithm builds on Sinnamon's algorithm, and can be viewed as a density-sensitive refinement of it.

To appear at ESA'24