{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T17:44:52Z","timestamp":1782927892409,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T00:00:00Z","timestamp":1782864000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P36280"],"award-info":[{"award-number":["P36280"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["I6915"],"award-info":[{"award-number":["I6915"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,7,6]]},"DOI":"10.1145\/3796701.3815951","type":"proceedings-article","created":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T16:40:43Z","timestamp":1782924043000},"page":"40-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Brief Announcement: Deterministic Edge Coloring with few Colors in CONGEST"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1417-6387","authenticated-orcid":false,"given":"Tijn","family":"de Vos","sequence":"first","affiliation":[{"name":"TU Graz, Graz, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4062-6991","authenticated-orcid":false,"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[{"name":"TU Graz, Graz, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-0874-2356","authenticated-orcid":false,"given":"Joakim","family":"Blikstad","sequence":"additional","affiliation":[{"name":"Radix Trading, Amsterdam, Netherlands"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,7]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"30th Annual European Symposium on Algorithms (ESA","author":"Ansari Mohammad","year":"2022","unstructured":"Mohammad Ansari, Mohammad Saneian, and Hamid Zarrabi-Zadeh. 2022. Simple streaming algorithms for edge coloring. In 30th Annual European Symposium on Algorithms (ESA 2022). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 8\u20131."},{"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.1016\/0020-0190(92)90209-E"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC).","author":"Barenboim Leonid","unstructured":"Leonid Barenboim, Michael Elkin, and U. Goldenberg. 2018. Locally-Iterative Distributed(Delta +1)-Coloring below Szegedy-Vishwanathan Barrier, and Applications to Self-Stabilization and to Restricted-Bandwidth Models. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC)."},{"key":"e_1_3_2_1_6_1","volume-title":"27th Annual European Symposium on Algorithms (ESA","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Marina Knittel, and Hamed Saleh. 2019. Streaming and massively parallel algorithms for edge coloring. In 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 15\u20131."},{"key":"e_1_3_2_1_7_1","volume-title":"2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2186\u20132201","author":"Bhattacharya Sayan","year":"2024","unstructured":"Sayan Bhattacharya, Din Carmon, Mart\u00edn Costa, Shay Solomon, and Tianyi Zhang. 2024. Faster (\u0394 + 1) -Edge Coloring: Breaking the mn Time Barrier. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2186\u20132201."},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2830\u20132842","author":"Bhattacharya Sayan","year":"2021","unstructured":"Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. 2021. Online edge coloring algorithms via the nibble method. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 2830\u20132842."},{"key":"e_1_3_2_1_9_1","unstructured":"Joakim Blikstad Yannic Maus and Tijn de Vos. 2026. Deterministic Edge Coloring with few Colors in CONGEST. Technical Report 2603.02689. arXiv. doi:10.48550\/ARXIV.2603.02689 Full version of this paper."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS63196.2025.00094"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.143"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365004"},{"key":"e_1_3_2_1_13_1","volume-title":"52nd International Colloquium on Automata, Languages, and Programming (ICALP","author":"Chechik Shiri","year":"2025","unstructured":"Shiri Chechik, Hongyi Chen, and Tianyi Zhang. 2025. Improved Streaming Edge Coloring. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 48\u20131."},{"key":"e_1_3_2_1_14_1","volume-title":"Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 1013\u20131026","author":"Grodt Christiansen Aleksander Bj\u00f8rn","year":"2023","unstructured":"Aleksander Bj\u00f8rn Grodt Christiansen. 2023. The power of multi-step Vizing chains. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing. 1013\u20131026."},{"key":"e_1_3_2_1_15_1","volume-title":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 4273\u20134295","author":"Davies Peter","year":"2023","unstructured":"Peter Davies. 2023. Improved Distributed Algorithms for the Lov\u00e1sz Local Lemma and Edge Coloring. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 4273\u20134295. arXiv:2208.08701"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310552"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00022-X"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.26"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.25"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00007"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212764"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2022.26"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79527-6_5"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210386"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2025.37"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_32_1","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC). 350\u2013363","author":"Rozho\u0148 V\u00e1clav","year":"2020","unstructured":"V\u00e1clav Rozho\u0148 and Mohsen Ghaffari. 2020. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the ACM Symposium on Theory of Computing (STOC). 350\u2013363."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316393"},{"key":"e_1_3_2_1_34_1","volume-title":"On an estimate of the chromatic class of a p-graph. Diskret analiz 3","author":"Vizing Vadim G","year":"1964","unstructured":"Vadim G Vizing. 1964. On an estimate of the chromatic class of a p-graph. Diskret analiz 3 (1964), 25\u201330."}],"event":{"name":"PODC '26: ACM Symposium on Principles of Distributed Computing","location":"Egham United Kingdom","acronym":"PODC '26","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3796701.3815951","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,1]],"date-time":"2026-07-01T16:50:26Z","timestamp":1782924626000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3796701.3815951"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7]]},"references-count":34,"alternative-id":["10.1145\/3796701.3815951","10.1145\/3796701"],"URL":"https:\/\/doi.org\/10.1145\/3796701.3815951","relation":{},"subject":[],"published":{"date-parts":[[2026,7]]},"assertion":[{"value":"2026-07-01","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}