Fast and Simple (1+ε)Δ-Edge-Coloring of Dense Graphs

Let ε ∈ (0, 1) and n, Δ ∈ N be such that Δ = Ω(maxlog n/ε,\, (1/εlog 1/ε)²\). Given an n-vertex m-edge simple graph G of maximum degree Δ, we present a randomized O(m\,log³ Δ\,/\,ε²)-time algorithm that computes a proper (1+ε)Δ-edge-coloring of G with high probability. This improves upon the best known results for a wide range of the parameters ε, n, and Δ. 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.