A Linear-Time Algorithm for \({(1+\varepsilon )\Delta }\)-Edge-Coloring
SIAM Journal on Discrete Mathematics · 30.06.2026 · 40 (2) · 919-958
DOI: 10.1137/25m1785241 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Discrete Mathematics, online erschienen am 16.06.2026. Verfasst von Anton Bernshteyn und 1 weiteren Autor:innen. Die Arbeit nennt 39 Literaturangaben. Gefördert von: National Science Foundation, Alfred P. Sloan Foundation, Georgia Institute of Technology.
Abstract (Originalsprache)
We present a randomized algorithm that, given a constant [Formula: see text], outputs a proper [Formula: see text]-edge-coloring of an [Formula: see text]-edge simple graph [Formula: see text] of maximum degree [Formula: see text] in [Formula: see text] time with high probability. This is the first linear-time algorithm for this problem covering the full range of possible values of [Formula: see text]. Indeed, even for edge-coloring with [Formula: see text] colors (i.e., meeting the “greedy” bound), no such linear-time algorithm has been previously known.
Förderung
- National Science Foundation
- Alfred P. Sloan Foundation
- Georgia Institute of Technology
Zitieren
APA
Bernshteyn, A., & Dhawan, A. (2026). A Linear-Time Algorithm for \({(1+\varepsilon )\Delta }\)-Edge-Coloring. SIAM Journal on Discrete Mathematics, 40(2), 919-958. https://doi.org/10.1137/25m1785241
Vancouver
Bernshteyn A, Dhawan A. A Linear-Time Algorithm for \({(1+\varepsilon )\Delta }\)-Edge-Coloring. SIAM Journal on Discrete Mathematics. 2026;40(2):919-958. doi:10.1137/25m1785241
BibTeX
@article{Bernshteyn2026,
author = {Bernshteyn, Anton and Dhawan, Abhishek},
title = {A Linear-Time Algorithm for \((1+\varepsilon )\Delta \)-Edge-Coloring},
journal = {SIAM Journal on Discrete Mathematics},
year = {2026},
volume = {40},
number = {2},
pages = {919--958},
doi = {10.1137/25m1785241}
}
EUVIMED