{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T06:46:20Z","timestamp":1782542780244,"version":"3.54.5"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T00:00:00Z","timestamp":1781568000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Sloan Research Fellowship"},{"name":"NSERC Discovery Grant","award":["RGPIN-2024-04290"],"award-info":[{"award-number":["RGPIN-2024-04290"]}]},{"name":"Faculty of Math Research Chair grant from University of Waterloo"},{"name":"NSF CAREER","award":["CCF-2442812"],"award-info":[{"award-number":["CCF-2442812"]}]},{"name":"Google Faculty Research Award"},{"name":"Google PhD Fellowship"},{"DOI":"10.13039\/501100000780","name":"European Union","doi-asserted-by":"crossref","award":["101043159"],"award-info":[{"award-number":["101043159"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001742","name":"United States-Israel Binational Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001742","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100000001","name":"United States National Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"crossref"}]},{"name":"\u201cA New Paradigm for Flow and Cut Algorithms\u201d","award":["TMSGI2_218022"],"award-info":[{"award-number":["TMSGI2_218022"]}]},{"DOI":"10.13039\/501100001711","name":"Swiss National Science Foundation","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China","award":["JYB2025XDXM118"],"award-info":[{"award-number":["JYB2025XDXM118"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2026,6,30]]},"abstract":"<jats:p>\n                    Vizing\u2019s theorem states that any\n                    <jats:italic toggle=\"yes\">n<\/jats:italic>\n                    -vertex\n                    <jats:italic toggle=\"yes\">m<\/jats:italic>\n                    -edge graph of maximum degree \u0394 can be\n                    <jats:italic toggle=\"yes\">edge colored<\/jats:italic>\n                    using at most \u0394 + 1 different colors [Vizing, 1964]. Vizing\u2019s original proof is algorithmic and shows that such an edge coloring can be found in\n                    <jats:italic toggle=\"yes\">O(mn)<\/jats:italic>\n                    time. This was subsequently improved to\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(m\\sqrt {n})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    time, independently by [Arjomandi, 1982] and by [Gabow et\u00a0al., 1985].\n                    <jats:xref ref-type=\"fn\">\n                      <jats:sup>1<\/jats:sup>\n                    <\/jats:xref>\n                  <\/jats:p>\n                  <jats:p>\n                    Very recently, independently and concurrently, using randomization, this runtime bound was further improved to\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(n^2)\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    by [Assadi, 2024] and\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(mn^{1\/3})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    by [Bhattacharya, Carmon, Costa, Solomon and Zhang, 2024] (and subsequently to\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\tilde{O}(mn^{1\/4})\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    by [Bhattacharya, Costa, Solomon and Zhang, 2024]).\n                  <\/jats:p>\n                  <jats:p>\n                    In this article, we present a randomized algorithm that computes a \u0394 + 1-edge coloring in near-linear time\u2014in fact, only\n                    <jats:italic toggle=\"yes\">O(m<\/jats:italic>\n                    log \u0394) time\u2014with high probability,\n                    <jats:italic toggle=\"yes\">giving a near-optimal algorithm for this fundamental problem<\/jats:italic>\n                    .\n                  <\/jats:p>","DOI":"10.1145\/3806392","type":"journal-article","created":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T11:26:43Z","timestamp":1775042803000},"page":"1-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Vizing\u2019s Theorem in Near-Linear Time"],"prefix":"10.1145","volume":"73","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8914-5995","authenticated-orcid":false,"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"University of Waterloo","place":["Waterloo, Canada"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0104-633X","authenticated-orcid":false,"given":"Soheil","family":"Behnezhad","sequence":"additional","affiliation":[{"name":"Northeastern University","place":["Boston, United States"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1612-0296","authenticated-orcid":false,"given":"Sayan","family":"Bhattacharya","sequence":"additional","affiliation":[{"name":"University of Warwick","place":["Coventry, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0726-9083","authenticated-orcid":false,"given":"Martin","family":"Costa","sequence":"additional","affiliation":[{"name":"University of Warwick","place":["Coventry, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2254-5100","authenticated-orcid":false,"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Tel Aviv University","place":["Tel Aviv, Israel"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3407-3307","authenticated-orcid":false,"given":"Tianyi","family":"Zhang","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, Nanjing University","place":["Nanjing, China"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00446-5"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1080\/03155986.1982.11731850"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.165"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538440"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.05.098"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.15"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.004"},{"key":"e_1_3_3_9_2","unstructured":"Anton Bernshteyn and Abhishek Dhawan. 2023. Fast algorithms for Vizing\u2019s theorem on bounded degree graphs. arXiv:2303.05408. Retrieved from https:\/\/arxiv.org\/abs\/2303.05408"},{"key":"e_1_3_3_10_2","article-title":"A linear-time algorithm for  \\((1+\\epsilon)\\Delta\\) -edge-coloring","author":"Bernshteyn Anton","year":"2024","unstructured":"Anton Bernshteyn and Abhishek Dhawan. 2024. A linear-time algorithm for \\((1+\\epsilon)\\Delta\\) -edge-coloring. arXiv:2407.04887. Retrieved from https:\/\/arxiv.org\/abs\/2407.04887","journal-title":"arXiv:2407.04887"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00128"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.1"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2024.12"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2024.23"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.122"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.167"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.168"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649741"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.49"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.40"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585105"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","unstructured":"Aleksander B. G. Christiansen. 2026. Deterministic Dynamic Edge Colouring. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201926) Vancouver BC Canada January 11-14 2026. SIAM 1047\u20131096. DOI:10.1137\/1.9781611978971.43","DOI":"10.1137\/1.9781611978971.43"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2024.20"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90032-A"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90022-9"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00010"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/0211043"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9044-3"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch163"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.77"},{"key":"e_1_3_3_33_2","article-title":"A simple algorithm for near-vizing edge-coloring in near-linear time","author":"Dhawan Abhishek","year":"2024","unstructured":"Abhishek Dhawan. 2024. A simple algorithm for near-vizing edge-coloring in near-linear time. arXiv:2407.16585. Retrieved from https:\/\/arxiv.org\/abs\/2407.16585","journal-title":"arXiv:2407.16585"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032018"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.117"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.168"},{"key":"e_1_3_3_37_2","article-title":"Deterministic simple  \\((1+\\epsilon)\\) -edge-coloring in near-linear time","author":"Elkin Michael","year":"2024","unstructured":"Michael Elkin and Ariel Khuzman. 2024. Deterministic simple \\((1+\\epsilon)\\) -edge-coloring in near-linear time. arXiv:2401.10538. Retrieved from https:\/\/arxiv.org\/abs\/2401.10538","journal-title":"arXiv:2401.10538"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.25"},{"key":"e_1_3_3_40_2","article-title":"Algorithms for Edge Coloring","author":"Gabow Harold N.","year":"1985","unstructured":"Harold N. Gabow, Takao Nishizeki, Oded Kariv, Daneil Leven, and Osamu Terada. 1985. Algorithms for Edge Coloring. Technical Report (1985).","journal-title":"Technical Report"},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.71"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806697"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107378"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90026-5"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2024.81"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519986"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00097"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_3_51_2","article-title":"Graph Theory 3-4: Edge Coloring Multigraphs","author":"Postle Luke","year":"2021","unstructured":"Luke Postle. 2021. Graph Theory 3-4: Edge Coloring Multigraphs. YouTube video. Retrieved January 12, 2026 from http:\/\/www.youtube.com\/watch?v=y9Tnf18Fwuc","journal-title":"YouTube video"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.109"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.121"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1949281148"},{"key":"e_1_3_3_55_2","article-title":"Fast and simple edge-coloring algorithms","author":"Sinnamon Corwin","year":"2019","unstructured":"Corwin Sinnamon. 2019. Fast and simple edge-coloring algorithms. arXiv:1907.03201. Retrieved from https:\/\/arxiv.org\/abs\/1907.03201","journal-title":"arXiv:1907.03201"},{"key":"e_1_3_3_56_2","first-page":"25","article-title":"On an estimate of the chromatic class of a p-graph","volume":"3","author":"Vizing V. G.","year":"1964","unstructured":"V. G. Vizing. 1964. On an estimate of the chromatic class of a p-graph. Discret Analiz 3 (1964), 25\u201330.","journal-title":"Discret Analiz"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01885700"},{"key":"e_1_3_3_58_2","unstructured":"David Wajc. Nov. 2024. Personal Communication."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3806392","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T05:57:50Z","timestamp":1782539870000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3806392"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,16]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6,30]]}},"alternative-id":["10.1145\/3806392"],"URL":"https:\/\/doi.org\/10.1145\/3806392","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,16]]},"assertion":[{"value":"2025-07-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-16","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-06-16","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}