Fast and simple (1 + ε)Δ-edge-coloring of dense graphs
Abhishek Dhawan · Theoretical Computer Science · 2025
Let ε ∈ ( 0 , 1 ) and n , Δ ∈ N be such that Δ = Ω ( max { log n ε , ( 1 ε log 1 ε ) 2 } ) . Given an n -vertex m -edge simple graph G of maximum degree Δ, we present a randomized O ( m log 3 Δ / ε 2 ) -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.