Fast and Simple $(1+\epsilon )\Delta$-Edge-Coloring of Dense Graphs

Abstract

Let $\epsilon \in (0,1)$ and $n,\Delta \in \mathbb{N}$ be such that $\Delta =\Omega \left(\max \left\{\frac{\log n}{\epsilon },{\left(\frac{1}{\epsilon }\log \frac{1}{\epsilon }\right)}^2\right\}\right)$. Given an $n$-vertex $m$-edge simple graph $G$ of maximum degree $\Delta$, we present a randomized $O\left(m{\log }^3\Delta /{\epsilon }^2\right)$-time algorithm that computes a proper $(1+\epsilon )\Delta$-edge-coloring of $G$ with high probability. This improves upon the best known results for a wide range of the parameters $\epsilon$, $n$, and $\Delta$. Our approach combines a flagging strategy from earlier work of the author with a shifting procedure employed by Duan, He, and Zhang for dynamic edge-coloring. The resulting algorithm is simple to implement and may be of practical interest.

arXiv comment26 pages, 9 figures. arXiv admin note: substantial text overlap with arXiv:2407.16585