{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,9]],"date-time":"2026-07-09T06:00:23Z","timestamp":1783576823732,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":51,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538440","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"15-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Distributed Edge Coloring in Time Polylogarithmic in \u0394"],"prefix":"10.1145","author":[{"given":"Alkida","family":"Balliu","sequence":"first","affiliation":[{"name":"Gran Sasso Science Institute, L'Aquila, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Brandt","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarbr\u00fccken, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dennis","family":"Olivetti","sequence":"additional","affiliation":[{"name":"Gran Sasso Science Institute, L'Aquila, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_3_2_2_2_1","volume-title":"Proc. 30th Symp. on Foundations of Computer Science (FOCS). 364--369","author":"Awerbuch Baruch","year":"1989","unstructured":"Baruch Awerbuch , Andrew V. Goldberg , Michael Luby , and Serge A. Plotkin . 1989. Network Decomposition and Locality in Distributed Computation . In Proc. 30th Symp. on Foundations of Computer Science (FOCS). 364--369 . https: \/\/doi.org\/10.1109\/SFCS. 1989 .63504 10.1109\/SFCS.1989.63504 Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. 1989. Network Decomposition and Locality in Distributed Computation. In Proc. 30th Symp. on Foundations of Computer Science (FOCS). 364--369. https: \/\/doi.org\/10.1109\/SFCS.1989.63504"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_2_4_1","volume-title":"Distributed -Coloring Plays Hide-and-Seek. arXiv preprint arXiv:2110.00643","author":"Balliu Alkida","year":"2021","unstructured":"Alkida Balliu , Sebastian Brandt , Fabian Kuhn , and Dennis Olivetti . 2021. Distributed -Coloring Plays Hide-and-Seek. arXiv preprint arXiv:2110.00643 ( 2021 ). Alkida Balliu, Sebastian Brandt, Fabian Kuhn, and Dennis Olivetti. 2021. Distributed -Coloring Plays Hide-and-Seek. arXiv preprint arXiv:2110.00643 (2021)."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405710"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2979675"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-02009-4"},{"key":"e_1_3_2_2_10_1","volume-title":"Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC). 437--446","author":"Barenboim Leonid","year":"2018","unstructured":"Leonid Barenboim , Michael Elkin , and Uri Goldenberg . 2018 . Locally-Iterative Distributed ( + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models . In Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC). 437--446 . Leonid Barenboim, Michael Elkin, and Uri Goldenberg. 2018. Locally-Iterative Distributed ( + 1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. In Proc. 37th ACM Symp. on Principles of Distributed Computing (PODC). 437--446."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3409964.3461785"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405745"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2016.05.001"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00022-X"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_3_2_2_22_1","volume-title":"Proc. 31st Symp. on Distributed Computing (DISC). 17:1--17:15","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer . 2017 . Improved Deterministic Distributed Matching via Rounding . In Proc. 31st Symp. on Distributed Computing (DISC). 17:1--17:15 . Manuela Fischer. 2017. Improved Deterministic Distributed Matching via Rounding. In Proc. 31st Symp. on Distributed Computing (DISC). 17:1--17:15."},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.25"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.73"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_2_28_1","volume-title":"Proc. 62nd IEEE Symp. on Foundations of Computing (FOCS).","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2021 . Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition . In Proc. 62nd IEEE Symp. on Foundations of Computing (FOCS). Mohsen Ghaffari and Fabian Kuhn. 2021. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. In Proc. 62nd IEEE Symp. on Foundations of Computing (FOCS)."},{"key":"e_1_3_2_2_29_1","volume-title":"Proc. 49th ACM Symp. on Theory of Computing (STOC). 784-- 797","author":"Ghaffari M.","unstructured":"M. Ghaffari , F. Kuhn , and Y. Maus . 2017. On the Complexity of Local Distributed Graph Problems . In Proc. 49th ACM Symp. on Theory of Computing (STOC). 784-- 797 . M. Ghaffari, F. Kuhn, and Y. Maus. 2017. On the Complexity of Local Distributed Graph Problems. In Proc. 49th ACM Symp. on Theory of Computing (STOC). 784-- 797."},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_3_2_2_32_1","volume-title":"Near-Optimal Distributed Degree+1 Coloring. CoRR abs\/2112.00604","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2021","unstructured":"Magn\u00fas M. Halld\u00f3rsson , Fabian Kuhn , Alexandre Nolin , and Tigran Tonoyan . 2021. Near-Optimal Distributed Degree+1 Coloring. CoRR abs\/2112.00604 ( 2021 ). Magn\u00fas M. Halld\u00f3rsson, Fabian Kuhn, Alexandre Nolin, and Tigran Tonoyan. 2021. Near-Optimal Distributed Degree+1 Coloring. CoRR abs\/2112.00604 (2021)."},{"key":"e_1_3_2_2_33_1","volume-title":"Proc. 9th ACMSIAM Symp. on Discrete Algorithms (SODA). 219--225","author":"Hanckowiak Michal","year":"1998","unstructured":"Michal Hanckowiak , Michal Karonski , and Alessandro Panconesi . 1998 . On the Distributed Complexity of Computing Maximal Matchings . In Proc. 9th ACMSIAM Symp. on Discrete Algorithms (SODA). 219--225 . Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. 1998. On the Distributed Complexity of Computing Maximal Matchings. In Proc. 9th ACMSIAM Symp. on Discrete Algorithms (SODA). 219--225."},{"key":"e_1_3_2_2_34_1","volume-title":"Proc. 18th ACM Symp. on Principles of Distributed Computing (PODC). 219--228","author":"Hanckowiak Michal","year":"1999","unstructured":"Michal Hanckowiak , Michal Karonski , and Alessandro Panconesi . 1999 . A Faster Distributed Algorithm for Computing Maximal Matchings Deterministically . In Proc. 18th ACM Symp. on Principles of Distributed Computing (PODC). 219--228 . Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. 1999. A Faster Distributed Algorithm for Computing Maximal Matchings Deterministically. In Proc. 18th ACM Symp. on Principles of Distributed Computing (PODC). 219--228."},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1279241"},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(86)90144-4"},{"key":"e_1_3_2_2_38_1","volume-title":"Proc. 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA).","author":"Kuhn Fabian","year":"2009","unstructured":"Fabian Kuhn . 2009 . Local Weak Coloring Algorithms and Implications on Deterministic Symmetry Breaking . In Proc. 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA). Fabian Kuhn. 2009. Local Weak Coloring Algorithms and Implications on Deterministic Symmetry Breaking. In Proc. 21st ACM Symp. on Parallelism in Algorithms and Architectures (SPAA)."},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.76"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_2_43_1","volume-title":"Local Conflict Coloring Revisited: Linial for Lists. CoRR abs\/2007.15251","author":"Maus Yannic","year":"2020","unstructured":"Yannic Maus and Tigran Tonoyan . 2020. Local Conflict Coloring Revisited: Linial for Lists. CoRR abs\/2007.15251 ( 2020 ). Yannic Maus and Tigran Tonoyan. 2020. Local Conflict Coloring Revisited: Linial for Lists. CoRR abs\/2007.15251 (2020)."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_2_48_1","volume-title":"Proc. 52nd ACM Symp. on Theory of Computing (STOC). 350--363","author":"Mohsen Ghaffari V\u00e1clav","year":"2020","unstructured":"V\u00e1clav Rozho? and Mohsen Ghaffari . 2020 . Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization . In Proc. 52nd ACM Symp. on Theory of Computing (STOC). 350--363 . V\u00e1clav Rozho? and Mohsen Ghaffari. 2020. Polylogarithmic-Time Deterministic Network Decomposition and Distributed Derandomization. In Proc. 52nd ACM Symp. on Theory of Computing (STOC). 350--363."},{"key":"e_1_3_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"},{"key":"e_1_3_2_2_50_1","volume-title":"Proc. 51st ACM Symp. on Theory of Computing (STOC). 355--364","author":"Su Hsin-Hao","unstructured":"Hsin-Hao Su and Hoa T. Vu . 2019. Towards the locality of Vizing's theorem . In Proc. 51st ACM Symp. on Theory of Computing (STOC). 355--364 . https:\/\/doi.org\/ 10.1145\/3313276.3316393 10.1145\/3313276.3316393 Hsin-Hao Su and Hoa T. Vu. 2019. Towards the locality of Vizing's theorem. In Proc. 51st ACM Symp. on Theory of Computing (STOC). 355--364. https:\/\/doi.org\/ 10.1145\/3313276.3316393"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167156"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","location":"Salerno Italy","acronym":"PODC '22","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538440","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538440","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:21Z","timestamp":1750191141000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538440"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":51,"alternative-id":["10.1145\/3519270.3538440","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538440","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}