EUVIMEDEUVIMED entdecken
Crossref

A Linear-Time Algorithm for \({(1+\varepsilon )\Delta }\)-Edge-Coloring

Anton Bernshteyn, Abhishek Dhawan

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →