A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time
<|reference_start|>A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time: We present a simple $(1+\varepsilon)\Delta$-edge-coloring algorithm for graphs of maximum degree $\Delta = \Omega(\log n / \varepsilon)$ with running time $O\left(m\,\log^3 n/\varepsilon^3\right)$. 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.<|reference_end|>
@article{dhawan2024a,
    title={A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time},
    author={Abhishek Dhawan},
    journal={arXiv preprint arXiv:2407.16585},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.16585},
    primaryClass={cs.DS math.CO}
}