{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T03:16:28Z","timestamp":1783048588176,"version":"3.54.6"},"reference-count":25,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T00:00:00Z","timestamp":1778112000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by-nc-nd\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000121","name":"National Science Foundation Division of Mathematical Sciences","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000121","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"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Information Processing Letters"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1016\/j.ipl.2026.106643","type":"journal-article","created":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T23:20:50Z","timestamp":1778196050000},"page":"106643","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["A simple algorithm for near-Vizing edge-coloring in near-linear time"],"prefix":"10.1016","volume":"194","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1971-7733","authenticated-orcid":false,"given":"Abhishek","family":"Dhawan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"78","reference":[{"key":"10.1016\/j.ipl.2026.106643_bib0001","series-title":"Graph Theory","author":"Bondy","year":"2008"},{"key":"10.1016\/j.ipl.2026.106643_bib0002","series-title":"Graph Theory","author":"Diestel","year":"2017"},{"key":"10.1016\/j.ipl.2026.106643_bib0003","first-page":"25","article-title":"On an estimate of the chromatic class of a P-graph","volume":"3","author":"Vizing","year":"1964","journal-title":"Diskret. Anal."},{"key":"10.1016\/j.ipl.2026.106643_bib0004","series-title":"Graph Edge Coloring: Vizing\u2019s Theorem and Goldberg\u2019s Conjecture","volume":"vol. 75","author":"Stiebitz","year":"2012"},{"issue":"4","key":"10.1016\/j.ipl.2026.106643_bib0005","doi-asserted-by":"crossref","first-page":"718","DOI":"10.1137\/0210055","article-title":"The NP-completeness of edge-coloring","volume":"10","author":"Holyer","year":"1981","journal-title":"SIAM J. Comput."},{"key":"10.1016\/j.ipl.2026.106643_bib0006","series-title":"Graph Theory: An Introductory Course","author":"Bollob\u00e1s","year":"1979"},{"key":"10.1016\/j.ipl.2026.106643_bib0007","doi-asserted-by":"crossref","unstructured":"J.R. Rao, E.W. Dijkstra, Designing the proof of Vizing\u2019s theoremIn: M. Broy (ed.). Programming and Mathematical Method, 1992, pp. 17\u201325.","DOI":"10.1007\/978-3-642-77572-7_3"},{"issue":"3","key":"10.1016\/j.ipl.2026.106643_bib0008","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/0020-0190(92)90041-S","article-title":"A constructive proof of Vizing\u2019s theorem","volume":"41","author":"Misra","year":"1992","journal-title":"Inf. Process. Lett."},{"key":"10.1016\/j.ipl.2026.106643_bib0009","series-title":"Technical Report","article-title":"Algorithms for Edge-Colouring Graphs","author":"Gabow","year":"1985"},{"key":"10.1016\/j.ipl.2026.106643_bib0010","unstructured":"C. Sinnamon, Fast and simple edge-coloring algorithms, 2019. https:\/\/arxiv.org\/abs\/1907.03201."},{"key":"10.1016\/j.ipl.2026.106643_bib0011","series-title":"2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)","first-page":"2186","article-title":"Faster (\u0394+1)-edge coloring: breaking the mn time barrier","author":"Bhattacharya","year":"2024"},{"key":"10.1016\/j.ipl.2026.106643_sbref0010","series-title":"Proc. 57th Annual ACM Symposium on Theory of Computing (STOC)","first-page":"24","article-title":"Vizing\u2019s theorem in near-linear time","author":"Assadi","year":"2025"},{"issue":"1","key":"10.1016\/j.ipl.2026.106643_bib0013","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/s004930170002","article-title":"Edge-coloring bipartite multigraphs in O (E logD) time","volume":"21","author":"Cole","year":"2001","journal-title":"Combinatorica"},{"key":"10.1016\/j.ipl.2026.106643_bib0014","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/j.jctb.2025.07.002","article-title":"Fast algorithms for Vizing\u2019s theorem on bounded degree graphs","volume":"175","author":"Bernshteyn","year":"2025","journal-title":"J. Comb. Theory Ser. B"},{"key":"10.1016\/j.ipl.2026.106643_bib0015","unstructured":"S. Bhattacharya, M. Costa, N. Panski, S. Solomon, Density-sensitive algorithms for (\u0394+1)-edge coloring, 2023. https:\/\/arxiv.org\/abs\/2307.02415."},{"issue":"1","key":"10.1016\/j.ipl.2026.106643_bib0016","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/0196-6774(87)90026-5","article-title":"Efficient parallel algorithms for edge coloring problems","volume":"8","author":"Karloff","year":"1987","journal-title":"J. Algorithms"},{"key":"10.1016\/j.ipl.2026.106643_bib0017","series-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms","first-page":"1937","article-title":"Dynamic edge coloring with improved approximation","author":"Duan","year":"2019"},{"key":"10.1016\/j.ipl.2026.106643_bib0018","unstructured":"M. Elkin, A. Khuzman, Deterministic simple (\u0394+\u03b5\u03b1)-edge-coloring in near-linear time, 2024. https:\/\/arxiv.org\/abs\/2401.10538."},{"key":"10.1016\/j.ipl.2026.106643_bib0019","series-title":"Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"3393","article-title":"Nibbling at long cycles: dynamic (and static) edge coloring in optimal time","author":"Bhattacharya","year":"2024"},{"key":"10.1016\/j.ipl.2026.106643_bib0020","series-title":"Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"4861","article-title":"Faster vizing and near-vizing edge coloring algorithms","author":"Assadi","year":"2025"},{"key":"10.1016\/j.ipl.2026.106643_bib0021","unstructured":"A. Bernshteyn, A. Dhawan, A linear-time algorithm for (1+\u03b5)\u0394-edge-coloring, 2024. https:\/\/arxiv.org\/abs\/2407.04887."},{"key":"10.1016\/j.ipl.2026.106643_bib0022","series-title":"Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","first-page":"5558","article-title":"Vizing\u2019s theorem in deterministic almost-linear time","author":"Assadi","year":"2026"},{"key":"10.1016\/j.ipl.2026.106643_bib0023","series-title":"Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing","first-page":"355","article-title":"Towards the locality of Vizing\u2019s theorem","author":"Su","year":"2019"},{"key":"10.1016\/j.ipl.2026.106643_bib0024","unstructured":"W. Kuszmaul, Q. Qi, The multiplicative version of Azuma\u2019s inequality, with an application to contention analysis, 2021. https:\/\/arxiv.org\/abs\/2102.05077."},{"key":"10.1016\/j.ipl.2026.106643_bib0025","series-title":"A Radical Approach to Real Analysis","volume":"vol. 10","author":"Bressoud","year":"2022"}],"container-title":["Information Processing Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000244?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0020019026000244?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T02:29:53Z","timestamp":1783045793000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0020019026000244"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":25,"alternative-id":["S0020019026000244"],"URL":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106643","relation":{},"ISSN":["0020-0190"],"issn-type":[{"value":"0020-0190","type":"print"}],"subject":[],"published":{"date-parts":[[2026,8]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"A simple algorithm for near-Vizing edge-coloring in near-linear time","name":"articletitle","label":"Article Title"},{"value":"Information Processing Letters","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.ipl.2026.106643","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2026 The Author(s). Published by Elsevier B.V.","name":"copyright","label":"Copyright"}],"article-number":"106643"}}