{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:06:25Z","timestamp":1749873985992,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","funder":[{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["24-1323-A0001"],"award-info":[{"award-number":["24-1323-A0001"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733508","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"360-371","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Round and Communication Efficient Graph Coloring"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0109-2432","authenticated-orcid":false,"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0540-0292","authenticated-orcid":false,"given":"Gopinath","family":"Mishra","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-7993-2952","authenticated-orcid":false,"given":"Hung Thuan","family":"Nguyen","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-8969-0279","authenticated-orcid":false,"given":"Farrel D","family":"Salim","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"30th Annual European Symposium on Algorithms, ESA 2022","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, September 5\u20139, 2022, Berlin\/Potsdam, Germany. Springer, 8:1\u20138:4."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588681"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.48"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976496.19"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649763"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585192"},{"key":"e_1_3_2_1_7_1","volume-title":"Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 337\u2013347","author":"Babai L\u00e1szl\u00f3","year":"1986","unstructured":"L\u00e1szl\u00f3 Babai, Peter Frankl, and Janos Simon. 1986. Complexity Classes in Communication Complexity Theory (Preliminary Version). In Proceedings of the 27th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 337\u2013347."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_1_9_1","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019","author":"Behnezhad Soheil","year":"2019","unstructured":"Soheil Behnezhad, Mahsa Derakhshan, Mohammad Taghi Hajiaghayi, Marina Knittel, and Hamed Saleh. 2019. Streaming and massively parallel algorithms for edge coloring. In 27th Annual European Symposium on Algorithms, ESA 2019, September 9\u201311, 2019, Munich\/Garching, Germany. Springer, 15:1\u201315:14."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175267"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3494539"},{"key":"e_1_3_2_1_12_1","volume-title":"2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). arXiv: 2208","author":"Blikstad Joakim","unstructured":"Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. 2022. Nearly optimal communication and query complexity of bipartite matching. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS). arXiv: 2208.02526."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1249527"},{"key":"e_1_3_2_1_15_1","volume-title":"Hung Thuan Nguyen, and Farrel D. Salim","author":"Chang Yi-Jun","year":"2024","unstructured":"Yi-Jun Chang, Gopinath Mishra, Hung Thuan Nguyen, and Farrel D. Salim. 2024. Round and Communication Efficient Graph Coloring. CoRR abs\/2412.12589 (2024). arXiv:2412.12589 [cs.DS]"},{"key":"e_1_3_2_1_16_1","volume-title":"4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11\u201312","author":"Charikar Moses","year":"2021","unstructured":"Moses Charikar and Paul Liu. 2021. Improved algorithms for edge colouring in the w-streaming model. In 4th Symposium on Simplicity in Algorithms, SOSA 2021, Virtual Conference, January 11\u201312, 2021. ACM, 181\u2013183."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.46"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS57955.2024.00098"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467937"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1366502"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.41"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2024.26"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2024.24"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-024-00475-3"},{"key":"e_1_3_2_1_25_1","first-page":"311","article-title":"Colorations des ar\u00eates d'un graphe","volume":"15","author":"Fournier Jean-Claude","year":"1973","unstructured":"Jean-Claude Fournier. 1973. Colorations des ar\u00eates d'un graphe. Cahiers du CERO (Bruxelles) 15 (1973), 311\u2013314.","journal-title":"Cahiers du CERO (Bruxelles)"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00007"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00101"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.32"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212737"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62228"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451089"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520023"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.113711"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538438"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1279241"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3501403"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a008"},{"key":"e_1_3_2_1_38_1","volume-title":"Proceedings of the 32nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"159","author":"Ivanyos G\u00e1bor","year":"2012","unstructured":"G\u00e1bor Ivanyos, Hartmut Klauck, Troy Lee, Miklos Santha, and Ronald de Wolf. 2012. New Bounds on the Classical and Quantum Communication Complexity of Some Graph Properties. In Proceedings of the 32nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 18). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 148\u2013159."},{"key":"e_1_3_2_1_39_1","volume-title":"Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication. CoRR abs\/2103.07027","author":"Konrad Christian","year":"2021","unstructured":"Christian Konrad, Peter Robinson, and Viktor Zamaraev. 2021. Robust Lower Bounds for Graph Problems in the Blackboard Model of Communication. CoRR abs\/2103.07027 (2021). arXiv:2103.07027 https:\/\/arxiv.org\/abs\/2103.07027 Available at https:\/\/arxiv.org\/abs\/2103.07027."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity.","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3007748.3007775"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3365005"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802192"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"crossref","unstructured":"Anup Rao and Amir Yehudayoff. 2020. Communication complexity and applications.","DOI":"10.1017\/9781108671644"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280895"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.121"},{"key":"e_1_3_2_1_50_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. Diskret. Analiz 3 (1964), 25\u201330. English translation in: Journal of Soviet Mathematics, 1980..","journal-title":"Diskret. Analiz"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00064-2"}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","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\/3732772.3733508","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:25:34Z","timestamp":1749824734000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733508"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":52,"alternative-id":["10.1145\/3732772.3733508","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733508","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}