A simple algorithm for near-Vizing edge-coloring in near-linear time
Abstract
• Simple near-linear time algorithm for ( 1 + ε ) Δ -edge-coloring that may be of practical interest. • Two-stage edge-coloring procedure reminiscent of palette sparsification for vertex coloring. • New flagging procedure for truncation of Vizing chains. We present a simple ( 1 + ε ) Δ -edge-coloring algorithm for graphs of maximum degree Δ = Ω ( log n / ε ) with running time O ( m log 3 n /ε 3 ). Our algorithm improves upon that of [Duan, He, and Zhang; SODA19], which was the first near-linear time algorithm for this problem. While our results are weaker than the current state-of-the-art, our approach is significantly simpler, both in terms of analysis as well as implementation, and may be of practical interest.
Fields of Study & Subjects
Color Science and Applications
Publication details
- Journal / source
- Information Processing Letters
- Publisher
- Elsevier BV
- Volume
- 194
- Pages
- 106643–106643
- Publication date
- 7 May 2026
- Language
- EN