{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:03Z","timestamp":1781077683714,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":55,"publisher":"ACM","funder":[{"name":"Sloan Research Fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"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","award":[""],"award-info":[{"award-number":[""]}]},{"name":"NSF CAREER award","award":["CCF-2442812"],"award-info":[{"award-number":["CCF-2442812"]}]},{"name":"Google Faculty Research Award","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Google PhD Fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"name":"European Research Council","award":["DynOpt 101043159"],"award-info":[{"award-number":["DynOpt 101043159"]}]},{"name":"The United States-Israel Binational Science Foundation (BSF)","award":[""],"award-info":[{"award-number":[""]}]},{"name":"The United States National Science Foundation (NSF)","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Swiss National Science Foundation","award":["TMSGI2_218022"],"award-info":[{"award-number":["TMSGI2_218022"]}]},{"name":"Simons Institute for the Theory of Computing, University of California Berkeley Sublinear Algorithms program","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718265","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"24-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Vizing\u2019s Theorem in Near-Linear Time"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0006-8914-5995","authenticated-orcid":false,"given":"Sepehr","family":"Assadi","sequence":"first","affiliation":[{"name":"University of Waterloo, 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, Boston, USA"}],"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, Coventry, United Kingdom"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0726-9083","authenticated-orcid":false,"given":"Mart\u00edn","family":"Costa","sequence":"additional","affiliation":[{"name":"University of Warwick, Coventry, United Kingdom"}],"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, 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":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00446-5"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1080\/03155986.1982.11731850"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.165"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2410.05240"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538440"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2017.05.098"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2019.15"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.004"},{"key":"e_1_3_2_1_9_1","volume-title":"Fast algorithms for Vizing\u2019s theorem on bounded degree graphs. CoRR, abs\/2303.05408","author":"Bernshteyn Anton","year":"2023","unstructured":"Anton Bernshteyn and Abhishek Dhawan. 2023. Fast algorithms for Vizing\u2019s theorem on bounded degree graphs. CoRR, abs\/2303.05408 (2023)."},{"key":"e_1_3_2_1_10_1","unstructured":"Anton Bernshteyn and Abhishek Dhawan. 2024. A linear-time algorithm for (1+\u220a )\u0394 -edge-coloring. arXiv preprint arXiv:2407.04887."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00128"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.1"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2024.12"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2024.23"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.122"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.167"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.168"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649741"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.49"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.40"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585105"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2402.13139"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SWAT.2024.20"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(90)90032-A"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90022-9"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00010"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211043"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9044-3"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch163"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.77"},{"key":"e_1_3_2_1_33_1","unstructured":"Abhishek Dhawan. 2024. A Simple Algorithm for Near-Vizing Edge-Coloring in Near-Linear Time. arXiv preprint arXiv:2407.16585."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.117"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.168"},{"key":"e_1_3_2_1_36_1","unstructured":"Michael Elkin and Ariel Khuzman. 2024. Deterministic Simple (1+\u220a )-Edge-Coloring in Near-Linear Time. arXiv preprint arXiv:2401.10538."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.25"},{"key":"e_1_3_2_1_39_1","unstructured":"Harold N Gabow Takao Nishizeki Oded Kariv Daneil Leven and Osamu Terada. 1985. Algorithms for edge coloring. Technical Rport."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.71"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806697"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2020.107378"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210055"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(87)90026-5"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2024.81"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519986"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2021.109"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.121"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1002\/sapm1949281148"},{"key":"e_1_3_2_1_52_1","unstructured":"Corwin Sinnamon. 2019. Fast and simple edge-coloring algorithms. arXiv preprint arXiv:1907.03201."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316393"},{"key":"e_1_3_2_1_54_1","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_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01885700"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718265","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:47:10Z","timestamp":1750693630000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718265"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":55,"alternative-id":["10.1145\/3717823.3718265","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718265","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}