A linear-time algorithm for $(1+\hat{I}\mu )\hat{I}”$-edge-coloring

Abstract

We present a randomized algorithm that, given a constant $\hat{I}\mu >0$, outputs a proper $(1+\hat{I}\mu )\hat{I}”$-edge-coloring of an $m$-edge simple graph $G$ of maximum degree $\hat{I}”\ge 1/\hat{I}\mu$ in $O(m)$ time with high probability. This is the first linear-time algorithm for this problem covering the full range of possible values of $\hat{I}”$. Indeed, even for edge-coloring with $2\hat{I}”-1$ colors (i.e., meeting the "greedy" bound), no such linear-time algorithm has been previously known.

36 pages, 11 figures. arXiv admin note: text overlap with arXiv:2303.05408