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

Let (0, 1) and n, N be such that = (\ n{, \, (1 1) ²\}). Given an n-vertex m-edge simple graph G of maximum degree, we present a randomized O (m\, ³ \, /\, ²) -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.