{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,8]],"date-time":"2025-09-08T06:09:38Z","timestamp":1757311778072,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T00:00:00Z","timestamp":1625788800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T00:00:00Z","timestamp":1625788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["336495"],"award-info":[{"award-number":["336495"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>We present a randomized distributed algorithm that computes a $$\\Delta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-coloring in any non-complete graph with maximum degree $$\\Delta \\ge 4$$<\/jats:tex-math>\n \n \u0394<\/mml:mi>\n \u2265<\/mml:mo>\n 4<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in $$O(\\log \\Delta ) + 2^{O(\\sqrt{\\log \\log n})}$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n (<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds, as well as a randomized algorithm that computes a $$\\Delta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-coloring in $$O((\\log \\log n)^2)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \n (<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> rounds when $$\\Delta \\in [3, O(1)]$$<\/jats:tex-math>\n \n \u0394<\/mml:mi>\n \u2208<\/mml:mo>\n [<\/mml:mo>\n 3<\/mml:mn>\n ,<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Both these algorithms improve on an $$O(\\log ^3 n \/ \\log \\Delta )$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n 3<\/mml:mn>\n <\/mml:msup>\n n<\/mml:mi>\n \/<\/mml:mo>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-round algorithm of Panconesi and Srinivasan (STOC\u201993), which has remained the state of the art for the past 25\u00a0years. Moreover, the latter algorithm gets (exponentially) closer to an $$\\Omega (\\log \\log n)$$<\/jats:tex-math>\n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> round lower bound of Brandt et al. (STOC\u201916).<\/jats:p>","DOI":"10.1007\/s00446-021-00397-4","type":"journal-article","created":{"date-parts":[[2021,7,9]],"date-time":"2021-07-09T09:02:47Z","timestamp":1625821367000},"page":"239-258","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Improved distributed $$\\Delta $$-coloring"],"prefix":"10.1007","volume":"34","author":[{"given":"Mohsen","family":"Ghaffari","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juho","family":"Hirvonen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1025-5037","authenticated-orcid":false,"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yannic","family":"Maus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,7,9]]},"reference":[{"key":"397_CR1","doi-asserted-by":"crossref","unstructured":"Aboulker, P., Bonamy, M., Bousquet, N., Esperet, L.: Distributed coloring in sparse graphs with fewer colors. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, UK, 23\u201327, 2018, pp. 419\u2013425 (2018)","DOI":"10.1145\/3212734.3212740"},{"issue":"4","key":"397_CR2","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"397_CR3","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: Proceedings of 30th Symposium on Foundations of Computer Science (FOCS 1989), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"issue":"1","key":"397_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.2200\/S00520ED1V01Y201307DCT011","volume":"4","author":"L Barenboim","year":"2013","unstructured":"Barenboim, L., Elkin, M.: Distributed graph coloring: fundamentals and recent developments. Synth. Lect. Distrib. Comput. Theory 4(1), 1\u2013171 (2013)","journal-title":"Synth. Lect. Distrib. Comput. Theory"},{"key":"397_CR5","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Goldenberg, U.: Locally-iterative distributed ($$\\Delta +1$$)-coloring below szegedy-vishwanathan barrier, and applications to self-stabilization and to restricted-bandwidth models. In: Proceedings of 37th ACM Symposium on Principles of Distributed Computing (PODC 2018) (to appear) (2018)","DOI":"10.1145\/3212734.3212769"},{"key":"397_CR6","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. In: Proceedings of 53rd Symposium on Foundations of Computer Science (FOCS 2012), pp. 321\u2013330 (2012)","DOI":"10.1109\/FOCS.2012.60"},{"issue":"3","key":"397_CR7","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1145\/2903137","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 201\u20132045 (2016)","journal-title":"J. ACM"},{"key":"397_CR8","doi-asserted-by":"crossref","unstructured":"Bondy, J.A., Murty, U.: Graph Theory with Applications. Elsevier (1976)","DOI":"10.1007\/978-1-349-03521-2"},{"key":"397_CR9","doi-asserted-by":"crossref","unstructured":"Brandt, S., Fischer, O., Hirvonen, J., Keller, B., Lempi\u00e4inen, T., Rybicki, J., Suomela, J., Uitto, J.: A lower bound for the distributed Lov\u00e1sz local lemma. In: Proceedings of 48th ACM Symposium on Theory of Computing (STOC 2016), pp. 479\u2013488. ACM (2016)","DOI":"10.1145\/2897518.2897570"},{"issue":"2","key":"397_CR10","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1017\/S030500410002168X","volume":"37","author":"RL Brooks","year":"1941","unstructured":"Brooks, R.L.: On colouring the nodes of a network. Math. Proc. Camb. Philos. Soc. 37(2), 194\u2013197 (1941)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"397_CR11","doi-asserted-by":"crossref","unstructured":"Leonard Brooks, R.: On colouring the nodes of a network. In: Classic Papers in Combinatorics, pp. 118\u2013121. Springer (2009)","DOI":"10.1007\/978-0-8176-4842-8_7"},{"key":"397_CR12","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the local model. In: Proceedings of 57th Symposium on Foundations of Computer Science (FOCS 2016), pp. 615\u2013624. IEEE (2016)","DOI":"10.1109\/FOCS.2016.72"},{"key":"397_CR13","doi-asserted-by":"crossref","unstructured":"Chang, Y.-J., Li, W., Pettie, S.: An optimal distributed ($$\\Delta + 1$$)-coloring algorithm? In: Proceedings 50th ACM Symposium on Theory of Computing (STOC 2018) (to appear) (2018)","DOI":"10.1145\/3188745.3188964"},{"key":"397_CR14","doi-asserted-by":"crossref","unstructured":"Chechik, S., Mukhtar, D.: Optimal distributed coloring algorithms for planar graphs in the local model. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA\u201919, pp. 787\u2013804 (2019)","DOI":"10.1137\/1.9781611975482.49"},{"issue":"3","key":"397_CR15","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1002\/jgt.21847","volume":"80","author":"DW Cranston","year":"2015","unstructured":"Cranston, D.W., Rabern, L.: Brooks\u2019 theorem and beyond. J. Graph Theory 80(3), 199\u2013225 (2015)","journal-title":"J. Graph Theory"},{"key":"397_CR16","unstructured":"Erd\u0151s, P., Rubin, A., Taylor, H.: Choosability in graphs. In: Proceedings of West Coast Conference on Combinatorics, Graph Theory and Computing, vol. 26, pp. 125\u2013157. Congressus Numerantium (1979)"},{"key":"397_CR17","unstructured":"Fischer, M., Ghaffari, M.: Sublogarithmic distributed algorithms for Lov\u00e1sz local lemma, and the complexity hierarchy. In: Proceedings of the International Symposium on Distributed Computing (DISC), pp. 18:1\u201318:16 (2017)"},{"key":"397_CR18","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Heinrich, M., Kosowski, A.: Local conflict coloring. In: Proceedings of 57th Symposium on Foundations of Computer Science (FOCS 2016), pp. 625\u2013634 (2016)","DOI":"10.1109\/FOCS.2016.73"},{"key":"397_CR19","doi-asserted-by":"crossref","unstructured":"Gfeller, B., Vicari, E.: A randomized distributed algorithm for the maximal independent set problem in growth-bounded graphs. In: Proceedings of 26th ACM Symposium on Principles of Distributed Computing (PODC 2007), pp. 53\u201360, New York, NY, USA (2007). ACM","DOI":"10.1145\/1281100.1281111"},{"key":"397_CR20","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.: An improved distributed algorithm for maximal independent set. In: Proceedings of 27th ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), pp. 270\u2013277 (2016)","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"397_CR21","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: Proceedings of 49th ACM Symposium on Theory of Computing (STOC 2017), pp. 784\u2013797. ACM (2017)","DOI":"10.1145\/3055399.3055471"},{"key":"397_CR22","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Su, H.-H.: Distributed degree splitting, edge coloring, and orientations. In: Proceedings of 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pp. 2505\u20132523. Society for Industrial and Applied Mathematics (2017)","DOI":"10.1137\/1.9781611974782.166"},{"key":"397_CR23","doi-asserted-by":"crossref","unstructured":"Harris, D.G., Schneider, J., Su, H.-H.: Distributed ($${\\Delta }+ 1$$)-coloring in sublogarithmic rounds. In: Proceedings of 48th ACM Symposium on Theory of Computing (STOC 2016) pp. 465\u2013478. ACM (2016)","DOI":"10.1145\/2897518.2897533"},{"key":"397_CR24","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Faster deterministic distributed coloring through recursive list coloring. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1244\u20131259 (2020)","DOI":"10.1137\/1.9781611975994.76"},{"issue":"1","key":"397_CR25","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"397_CR26","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/0095-8956(75)90089-1","volume":"19","author":"L Lov\u00e1sz","year":"1975","unstructured":"Lov\u00e1sz, L.: Three short proofs in graph theory. J. Combin. Theory Ser. B 19(3), 269\u2013271 (1975)","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"397_CR27","doi-asserted-by":"publisher","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"397_CR28","unstructured":"Maus, Y., Tonoyan, T.: Local conflict coloring revisited: linial for lists. In: Proceedings of the International Symposium on Distributed Computing (DISC), pp. 16:1\u201316:18 (2020)"},{"key":"397_CR29","unstructured":"Molloy, M., Reed, B.: Graph Colouring and the Probabilistic Method, vol. 23. Springer (2013)"},{"key":"397_CR30","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: Proceedings of 24th ACM Symposium on Theory of Computing (STOC 1992), pp. 581\u2013592. ACM (1992)","DOI":"10.1145\/129712.129769"},{"issue":"2","key":"397_CR31","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01200759","volume":"15","author":"A Panconesi","year":"1995","unstructured":"Panconesi, A., Srinivasan, A.: The local nature of $$\\Delta $$-coloring and its algorithmic applications. Combinatorica 15(2), 255\u2013280 (1995)","journal-title":"Combinatorica"},{"key":"397_CR32","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"397_CR33","doi-asserted-by":"crossref","unstructured":"Rozho\u0148, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 350\u2013363 (2020)","DOI":"10.1145\/3357713.3384298"},{"key":"397_CR34","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2012.09.004","volume":"509","author":"J Schneider","year":"2013","unstructured":"Schneider, J., Elkin, M., Wattenhofer, R.: Symmetry breaking depending on the chromatic number or the neighborhood growth. Theoret. Comput. Sci. 509, 40\u201350 (2013)","journal-title":"Theoret. Comput. Sci."},{"key":"397_CR35","first-page":"3","volume":"29","author":"V Vizing","year":"1976","unstructured":"Vizing, V.: Vextex coloring with given colors. Metody Diskretn. Anal. 29, 3\u201310 (1976)","journal-title":"Metody Diskretn. Anal."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00397-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-021-00397-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-021-00397-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T05:05:00Z","timestamp":1626843900000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-021-00397-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,9]]},"references-count":35,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["397"],"URL":"https:\/\/doi.org\/10.1007\/s00446-021-00397-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2021,7,9]]},"assertion":[{"value":"1 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 July 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}