{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T07:52:13Z","timestamp":1781596333667,"version":"3.54.5"},"reference-count":39,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2045412"],"award-info":[{"award-number":["DMS-2045412"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2528522"],"award-info":[{"award-number":["DMS-2528522"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2053333"],"award-info":[{"award-number":["DMS-2053333"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-2239187"],"award-info":[{"award-number":["DMS-2239187"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DMS-1937241"],"award-info":[{"award-number":["DMS-1937241"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006778","name":"Georgia Institute of Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006778","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2026,6,30]]},"DOI":"10.1137\/25m1785241","type":"journal-article","created":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T07:00:36Z","timestamp":1781593236000},"page":"919-958","source":"Crossref","is-referenced-by-count":0,"title":["A Linear-Time Algorithm for \\({(1+\\varepsilon )\\Delta }\\)-Edge-Coloring"],"prefix":"10.1137","volume":"40","author":[{"given":"Anton","family":"Bernshteyn","sequence":"first","affiliation":[{"name":"Department of Mathematics, University of California, Los Angeles, Los Angeles, CA 90095 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhishek","family":"Dhawan","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Illinois Urbana-Champaign, Urbana, IL 61820 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,6,16]]},"reference":[{"key":"ref1","doi-asserted-by":"crossref","unstructured":"D. Achlioptas, F. Iliopoulos, and A. Sinclair, Beyond the Lov\u00e1sz local lemma: Point to set correlations and their algorithmic applications, in Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS), 2019, pp. 725\u2013744, https:\/\/doi.org\/10.1109\/FOCS.2019.00049.","DOI":"10.1109\/FOCS.2019.00049"},{"key":"ref2","first-page":"82","volume":"20","author":"Arjomandi E.","year":"1982","journal-title":"INFOR Inf. Syst. Oper. Res."},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"S. Assadi, Faster Vizing and near-Vizing edge coloring algorithms, in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2025, pp. 4861\u20134898, https:\/\/doi.org\/10.1137\/1.9781611978322.165.","DOI":"10.1137\/1.9781611978322.165"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"S. Assadi, S. Behnezhad, S. Bhattacharya, M. Costa, S. Solomon, and T. Zhang, Vizing\u2019s theorem in near-linear time, in Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025, pp. 24\u201335.","DOI":"10.1145\/3717823.3718265"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.004"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1090\/proc\/17048"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2025.07.002"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya, D. Carmon, M. Costa, S. Solomon, and T. Zhang, Faster \\((\\delta +1)\\)-edge coloring: Breaking the \\(m\\sqrt {n}\\) time barrier, in Proceedings of the 65th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2024, pp. 2186\u20132201.","DOI":"10.1109\/FOCS61266.2024.00128"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya, D. Chakrabarty, M. Henzinger, and D. Nanongkai, Dynamic algorithms for graph coloring, in Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2018, pp. 1\u201320, https:\/\/doi.org\/10.1137\/1.9781611975031.1.","DOI":"10.1137\/1.9781611975031.1"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"S. Bhattacharya, M. Costa, N. Panski, and S. Solomon, Nibbling at long cycles: Dynamic (and static) edge coloring in optimal time, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2024, pp. 3393\u20133440, https:\/\/doi.org\/10.1137\/1.9781611977912.122.","DOI":"10.1137\/1.9781611977912.122"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-9967-7"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"Y.J. Chang, Q. He, W. Li, S. Pettie, and J. Uitto, The complexity of distributed edge coloring with small palettes, in Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2018, pp. 2633\u20132652, https:\/\/doi.org\/10.1137\/1.9781611975031.168.","DOI":"10.1137\/1.9781611975031.168"},{"key":"ref14","first-page":"1013","author":"Christiansen A.","year":"2023","journal-title":"ACM Symposium on Theory of Computing (STOC)"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"A. Dhawan, Edge-coloring algorithms for bounded degree multigraphs, in Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2024, pp. 2120\u20132157, https:\/\/doi.org\/10.1137\/1.9781611977912.77.","DOI":"10.1137\/1.9781611977912.77"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2025.115126"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"R. Duan, H. He, and T. Zhang, Dynamic edge coloring with improved approximation, in Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2019, pp. 1937\u20131945, https:\/\/doi.org\/10.1137\/1.9781611975482.117.","DOI":"10.1137\/1.9781611975482.117"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3070-6"},{"key":"ref20","unstructured":"M. Elkin and A. Khuzman, Deterministic Simple \\((\\delta +\\varepsilon \\alpha )\\)-Edge-Coloring in Near-Linear Time, preprint, https:\/\/arxiv.org\/abs\/2401.10538, 2024."},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2013.02.007"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.4171\/aihpd\/122"},{"key":"ref23","unstructured":"H. Gabow, T. Nishizeki, O. Kariv, D. Leven, and O. Terada, Algorithms for Edge-Coloring Graphs, Technical report 41\/85, 1985, https:\/\/web.eecs.umich.edu\/."},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.111772"},{"key":"ref25","first-page":"e32","volume-title":"Forum of Mathematics, Sigma","volume":"13","author":"Greb\u00edk J.","year":"2025"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107378"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20411"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"D. G. Harris and A. Srinivasan, A constructive algorithm for the Lov\u00e1sz local lemma on permutations, in Proceedings of the 2014 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM,\u00a02014, pp. 907\u2013925, https:\/\/doi.org\/10.1137\/1.9781611973402.68.","DOI":"10.1137\/1.9781611973402.68"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/18M1167176"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"ref31","unstructured":"W. Kuszmaul and Q. Qi, The Multiplicative Version of Azuma\u2019s Inequality, with an Application to Contention Analysis, preprint, https:\/\/arxiv.org\/abs\/2102.05077, 2021."},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90041-S"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667060"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-77572-7_3"},{"key":"ref35","unstructured":"C. Sinnamon, Fast and Simple Edge-Coloring Algorithms, preprint, https:\/\/arxiv.org\/abs\/1907.03201, 2021."},{"key":"ref36","volume-title":"Graph Edge Coloring","author":"Stiebitz M.","year":"2012"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"H.H. Su and H. Vu, Towards the locality of Vizing\u2019s theorem, in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019, pp. 355\u2013364.","DOI":"10.1145\/3313276.3316393"},{"key":"ref38","author":"Tao T.","year":"2009","journal-title":"What\u2019s new (blog post)"},{"key":"ref39","first-page":"25","volume":"3","author":"Vizing V.","year":"1964","journal-title":"Diskret. Analiz."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T07:00:51Z","timestamp":1781593251000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/25M1785241"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,16]]},"references-count":39,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1137\/25M1785241"],"URL":"https:\/\/doi.org\/10.1137\/25m1785241","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,16]]}}}