{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T08:00:53Z","timestamp":1784793653999,"version":"3.55.0"},"reference-count":60,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2026,8,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We provide new deterministic algorithms for the edge coloring problem, which is one of the classic and highly studied distributed local symmetry breaking problems. As our main result, we show that a [Formula: see text]-edge coloring can be computed in time [Formula: see text] in the [Formula: see text] model. This improves a result of Balliu, Kuhn, and Olivetti [ Distributed edge coloring in time quasi-polylogarithmic in [Formula: see text], in Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020, pp. 289\u2013298], who gave an algorithm with a quasi-polylogarithmic dependency on [Formula: see text]. We further show that in the [Formula: see text] model, an [Formula: see text]-edge coloring can be computed in [Formula: see text] rounds. The best previous [Formula: see text]-edge coloring algorithm that can be implemented in the [Formula: see text] model is by Barenboim and Elkin [ J. ACM, 58 (2011), 23] and it computes a [Formula: see text]-edge coloring in time [Formula: see text] for any [Formula: see text].<\/jats:p>","DOI":"10.1137\/24m1715866","type":"journal-article","created":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T07:01:10Z","timestamp":1784790070000},"page":"592-621","source":"Crossref","is-referenced-by-count":0,"title":["Distributed Edge Coloring in Time Polylogarithmic in \\({\\Delta }\\)"],"prefix":"10.1137","volume":"55","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5293-8365","authenticated-orcid":true,"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"Gran Sasso Science Institute, 67100 L\u2019Aquila AQ, Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, 66123 Saarbr\u00fccken, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, 79098 Freiburg, Germany."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, 67100 L\u2019Aquila AQ, Italy."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,7,23]]},"reference":[{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, A. V. Goldberg, M. Luby, and S. A. Plotkin, Network decomposition and locality in distributed computation, in Proceedings of the 30th Symposium on Foundations of Computer Science (FOCS), 1989, pp. 364\u2013369, https:\/\/doi.org\/10.1109\/SFCS.1989.63504.","DOI":"10.1109\/SFCS.1989.63504"},{"key":"ref3","doi-asserted-by":"crossref","unstructured":"A. Balliu, S. Brandt, J. Hirvonen, D. Olivetti, M. Rabie, and J. Suomela, Lower bounds for maximal matchings and maximal independent sets, in Proceedings of the 60th IEEE Symposium on Foundations of Computer Science (FOCS), 2019, pp. 481\u2013497.","DOI":"10.1109\/FOCS.2019.00037"},{"key":"ref4","doi-asserted-by":"crossref","unstructured":"A. Balliu, S. Brandt, F. Kuhn, and D. Olivetti, Distributed \\(\\Delta\\)-coloring plays hide-and-seek, J. ACM, (2026), https:\/\/dl.acm.org\/doi\/10.1145\/3819817.","DOI":"10.1145\/3819817"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"A. Balliu, F. Kuhn, and D. Olivetti, Distributed edge coloring in time quasi-polylogarithmic in \\(\\Delta\\), in Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020, pp. 289\u2013298, https:\/\/doi.org\/10.1145\/3382734.3405710.","DOI":"10.1145\/3382734.3405710"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2979675"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-012-0167-7"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02009-4"},{"key":"ref10","doi-asserted-by":"crossref","unstructured":"L. Barenboim, M. Elkin, and U. Goldenberg, Locally-iterative distributed \\((\\Delta +\\)1)-coloring below Szegedy-Vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models, in Proceedings of the 37th ACM Symposium on Principles of Distributed Computing (PODC), 2018, pp. 437\u2013446.","DOI":"10.1145\/3212734.3212769"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.004"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2025.07.002"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"S. Brandt, O. Fischer, J. Hirvonen, B. Keller, T. Lempi\u00e4inen, J. Rybicki, J. Suomela, and J. Uitto, A lower bound for the distributed Lov\u00e1sz local lemma, in Proceedings of the 48th ACM Symposium on Theory of Computing (STOC), 2016, pp. 479\u2013488, https:\/\/doi.org\/10.1145\/2897518.","DOI":"10.1145\/2897518.2897570"},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"S. Brandt, B. Keller, J. Rybicki, J. Suomela, and J. Uitto, Efficient load-balancing through distributed token dropping, in Proceedings of the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2021, pp. 129\u2013139.","DOI":"10.1145\/3409964.3461785"},{"key":"ref17","doi-asserted-by":"crossref","unstructured":"S. Brandt and D. Olivetti, Truly tight-in-\\(\\Delta\\) bounds for bipartite maximal matching and variants, in Proceedings of the 39th ACM Symposium on Principles of Distributed Computing (PODC), 2020, pp. 69\u201378.","DOI":"10.1145\/3382734.3405745"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"Y. Chang, W. Li, and S. Pettie, An optimal distributed (\\(\\Delta\\)+1)-coloring algorithm? in Proceedings of the 50th ACM Symposium on Theory of Computing, (STOC), 2018, pp. 445\u2013456, https:\/\/doi.org\/10.1145\/3188745.","DOI":"10.1145\/3188745.3188964"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"A. B. G. Christiansen, The power of multi-step vizing chains, in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, 2023, B. Sahaand and R. A. Servedio, eds. ACM, 2023, pp. 1013\u20131026, https:\/\/doi.org\/10.1145\/3564246.3585105.","DOI":"10.1145\/3564246.3585105"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.05.001"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00022-X"},{"key":"ref24","doi-asserted-by":"crossref","unstructured":"M. Elkin, S. Pettie, and H. Su, (2 \\(\\Delta\\) - l)-edge-coloring is much easier than maximal matching in the distributed setting, in Proceedings of the 26th ACM-SIAM Symposium\u00a0on Discrete Algorithms (SODA), 2015, pp. 355\u2013370, https:\/\/doi.org\/10.1137\/1.9781611973730.26.","DOI":"10.1137\/1.9781611973730.26"},{"key":"ref25","doi-asserted-by":"crossref","unstructured":"S. Faour, M. Ghaffari, C. Grunau, F. Kuhn, and V. Rozhon, Local distributed rounding: Generalized to mis, matching, set cover, and beyond, in Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, 2023, SIAM, Philadelphia, 2023, pp. 4409\u20134447, https:\/\/doi.org\/10.1137\/1.9781611977554.ch168.","DOI":"10.1137\/1.9781611977554.ch168"},{"key":"ref26","unstructured":"M. Fischer, Improved deterministic distributed matching via rounding, in Proceedings of the 31st Symposium on Distributed Computing (DISC), 2017, 17."},{"key":"ref27","doi-asserted-by":"crossref","unstructured":"M. Fischer, M. Ghaffari, and F. Kuhn, Deterministic distributed edge-coloring via hypergraph maximal matching, in Proceedings of the 58th IEEE Symposium on Foundations of Computer Science (FOCS), 2017, pp. 180\u2013191, https:\/\/doi.org\/10.1109\/FOCS.2017.25.","DOI":"10.1109\/FOCS.2017.25"},{"key":"ref28","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud, M. Heinrich, and A. Kosowski, Local conflict coloring, in Proceedings of the 57th IEEE Symposium on Foundations of Computer Science (FOCS), 2016, pp. 625\u2013634.","DOI":"10.1109\/FOCS.2016.73"},{"key":"ref29","doi-asserted-by":"crossref","unstructured":"M. Ghaffari, An improved distributed algorithm for maximal independent set, in Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2016, pp. 270\u2013277, https:\/\/doi.org\/10.1137\/1.9781611974331.","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"M. Ghaffari and C. Grunau,\n                      Faster deterministic distributed MIS and approximate matching\n                      , in Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Association for Computing Machinery, New York, 2023, pp. 1777\u20131790, https:\/\/doi.org\/10.1145\/3564246.3585243.","DOI":"10.1145\/3564246.3585243"},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"M. Ghaffari and C. Grunau, Near-optimal deterministic network decomposition and ruling set, and improved MIS, in Proceedings of the 65th IEEE Symposium on Foundations of Computer Science (FOCS), 2024, pp. 2148\u20132179.","DOI":"10.1109\/FOCS61266.2024.00007"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"M. Ghaffari, C. Grunau, B. Haeupler, S. Ilchi, and V. Rozhon, Improved distributed network decomposition, hitting sets, and spanners, via derandomization, in Proceedings of the 34th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023, pp. 2532\u20132566 https:\/\/doi.org\/10.1137\/1.9781611977554.ch97.","DOI":"10.1137\/1.9781611977554.ch97"},{"key":"ref33","doi-asserted-by":"crossref","unstructured":"M. Ghaffari, C. Grunau, and V. Rozhon, Improved deterministic network decomposition, in Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA), 2021, pp. 2904\u20132923, https:\/\/doi.org\/10.1137\/1.9781611976465.","DOI":"10.1137\/1.9781611976465.173"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"M. Ghaffari, D. G. Harris, and F. Kuhn, On derandomizing local distributed algorithms, in Proceedings of the 59th Symposium on Foundations of Computer Science (FOCS), 2018, pp. 662\u2013673.","DOI":"10.1109\/FOCS.2018.00069"},{"key":"ref35","doi-asserted-by":"crossref","unstructured":"M. Ghaffari and F. Kuhn, Deterministic distributed vertex coloring: Simpler, faster, and without network decomposition, in Proceedings of the 62nd IEEE Symposium on Foundations of Computing (FOCS), 2021, pp. 1009\u20131020.","DOI":"10.1109\/FOCS52979.2021.00101"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"M. Ghaffari, F. Kuhn, and Y. Maus, On the complexity of local distributed graph problems, in Proceedings of the 49th ACM Symposium on Theory of Computing (STOC), 2017, pp. 784\u2013797.","DOI":"10.1145\/3055399.3055471"},{"key":"ref37","doi-asserted-by":"crossref","unstructured":"M. Ghaffari, F. Kuhn, Y. Maus, and J. Uitto, Deterministic distributed edge-coloring with fewer colors, in Proceedings of the 50th ACM Symposium on Theory of Computing (STOC), 2018, pp. 418\u2013430.","DOI":"10.1145\/3188745.3188906"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520023"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"M. Hanckowiak, M. Karonski, and A. Panconesi, On the distributed complexity of computing maximal matchings, SIAM J. Discrete Math., 15 (2001), pp. 41\u201357.","DOI":"10.1137\/S0895480100373121"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"M. Hanckowiak, M. Karonski, and A. Panconesi, A faster distributed algorithm for computing maximal matchings deterministically, in Proceedings of the 18th ACM Symposium on Principles of Distributed Computing (PODC), 1999, pp. 219\u2013228.","DOI":"10.1145\/301308.301360"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1137\/19M1279241"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"ref45","doi-asserted-by":"crossref","unstructured":"F. Kuhn, Weak graph colorings: distributed algorithms and applications, in Proceedings of the 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2009, pp. 138\u2013144.","DOI":"10.1145\/1583991.1584032"},{"key":"ref46","doi-asserted-by":"crossref","unstructured":"F. Kuhn, Faster deterministic distributed coloring through recursive list coloring, in Proceedings of the 32st ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020, pp. 1244\u20131259, https:\/\/doi.org\/10.1137\/1.9781611975994.76.","DOI":"10.1137\/1.9781611975994.76"},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"F. Kuhn and R. Wattenhofer, On the complexity of distributed graph coloring, in Proceedings of the 25th ACM Symposium on Principles of Distributed Computing (PODC), 2006, pp. 7\u201315.","DOI":"10.1145\/1146381.1146387"},{"key":"ref48","doi-asserted-by":"crossref","unstructured":"N. Linial, Distributive graph algorithms \u2013 Global solutions from local data, in Proceedings of the 28th Symposium on Foundations of Computer Science (FOCS 1987), IEEE, 1987, pp. 331\u2013335, https:\/\/doi.org\/10.1109\/SFCS.1987.20.","DOI":"10.1109\/SFCS.1987.20"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"ref50","first-page":"16:1","volume-title":"34th International Symposium on Distributed Computing (DISC)","author":"Maus Y.","year":"2020"},{"key":"ref51","doi-asserted-by":"crossref","unstructured":"G. L. Miller, R. Peng, and S. C. Xu, Parallel graph decompositions using random shifts, in Proceedings of the 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2013, pp. 196\u2013203.","DOI":"10.1145\/2486159.2486180"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"ref55","author":"Peleg D.","year":"2000","journal-title":"Society for Industrial and Applied Mathematics"},{"key":"ref56","doi-asserted-by":"crossref","unstructured":"V. Rozhon, B. Haeupler, and C. Grunau, A simple deterministic distributed low-diameter clustering, in Proceedings of the 6th Symposium on Simplicity in Algorithms (SOSA), 2023, pp. 166\u2013174.","DOI":"10.1137\/1.9781611977585.ch16"},{"key":"ref57","doi-asserted-by":"crossref","unstructured":"V. Rozho\u0148 and M. Ghaffari, Polylogarithmic-time deterministic network decomposition and distributed derandomization, in Proceedings of the 52nd ACM Symposium on Theory of Computing (STOC), 2020, pp. 350\u2013363.","DOI":"10.1145\/3357713.3384298"},{"key":"ref58","doi-asserted-by":"crossref","unstructured":"J. Schneider and R. Wattenhofer, A new technique for distributed symmetry breaking, in Proceedings of the 29th ACM Symposium on Principles of Distributed Computing (PODC), 2010, pp. 257\u2013266, https:\/\/doi.org\/10.1145\/1835698.","DOI":"10.1145\/1835698.1835760"},{"key":"ref59","doi-asserted-by":"crossref","unstructured":"H. Su and H. T. Vu, Towards the locality of Vizing\u2019s theorem, in Proceedings of the 51st ACM Symposium on Theory of Computing (STOC), 2019, pp. 355\u2013364, https:\/\/doi.org\/10.1145\/3313276.","DOI":"10.1145\/3313276.3316393"},{"key":"ref60","doi-asserted-by":"crossref","unstructured":"M. Szegedy and S. Vishwanathan, Locality based graph coloring, in Proceedings of the 25th ACM Symposium on Theory of Computing (STOC), 1993, pp. 201\u2013207.","DOI":"10.1145\/167088.167156"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","deposited":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T07:01:14Z","timestamp":1784790074000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1715866"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,23]]},"references-count":60,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,8,31]]}},"alternative-id":["10.1137\/24M1715866"],"URL":"https:\/\/doi.org\/10.1137\/24m1715866","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,23]]}}}