{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:27Z","timestamp":1750694787534,"version":"3.37.3"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T00:00:00Z","timestamp":1652745600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T00:00:00Z","timestamp":1652745600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008332","name":"Graz University of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008332","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2022,12]]},"abstract":"Abstract<\/jats:title>Linial\u2019s famous color reduction algorithm reduces a given m<\/jats:italic>-coloring of a graph with maximum degree $$\\varDelta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to an $$O(\\varDelta ^2\\log m)$$<\/jats:tex-math>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u0394<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n log<\/mml:mo>\n m<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-coloring, in a single round in the LOCAL model. We give a similar result when nodes are restricted to choose their color from a list of allowed colors: given an m<\/jats:italic>-coloring in a directed graph of maximum outdegree $$\\beta $$<\/jats:tex-math>\n \u03b2<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, if every node has a list of size $$\\varOmega (\\beta ^2 (\\log \\beta +\\log \\log m + \\log \\log |{\\mathcal {C}}|))$$<\/jats:tex-math>\n \n \n \u03a9<\/mml:mi>\n (<\/mml:mo>\n <\/mml:mrow>\n \n \u03b2<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n (<\/mml:mo>\n log<\/mml:mo>\n \u03b2<\/mml:mi>\n +<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n m<\/mml:mi>\n +<\/mml:mo>\n log<\/mml:mo>\n log<\/mml:mo>\n |<\/mml:mo>\n C<\/mml:mi>\n |<\/mml:mo>\n )<\/mml:mo>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> from a color space $${\\mathcal {C}}$$<\/jats:tex-math>\n C<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> then they can select a color in two rounds in the LOCAL model. Moreover, the communication of a node essentially consists of sending its list to the neighbors. This is obtained as part of a framework that also contains Linial\u2019s color reduction (with an alternative proof) as a special case. Our result also leads to a defective list coloring<\/jats:italic> algorithm. As a corollary, we improve the state-of-the-art truly local<\/jats:italic>$$({\\text {deg}}+1)$$<\/jats:tex-math>\n \n (<\/mml:mo>\n deg<\/mml:mtext>\n +<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-list coloring algorithm from Barenboim et al. (PODC, pp 437\u2013446, 2018) by slightly reducing the runtime to $$O(\\sqrt{\\varDelta \\log \\varDelta })+\\log ^* n$$<\/jats:tex-math>\n \n O<\/mml:mi>\n \n (<\/mml:mo>\n \n \n \u0394<\/mml:mi>\n log<\/mml:mo>\n \u0394<\/mml:mi>\n <\/mml:mrow>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n log<\/mml:mo>\n \u2217<\/mml:mo>\n <\/mml:msup>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and significantly reducing the message size (from $$\\varDelta ^{O(\\log ^* \\varDelta )}$$<\/jats:tex-math>\n \n \u0394<\/mml:mi>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n log<\/mml:mo>\n \u2217<\/mml:mo>\n <\/mml:msup>\n \u0394<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> to roughly $$\\varDelta $$<\/jats:tex-math>\n \u0394<\/mml:mi>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>). Our techniques are inspired by the local conflict coloring<\/jats:italic> framework of Fraigniaud et al. (in: FOCS, pp 625\u2013634, 2016).<\/jats:p>","DOI":"10.1007\/s00446-022-00424-y","type":"journal-article","created":{"date-parts":[[2022,5,17]],"date-time":"2022-05-17T09:10:00Z","timestamp":1652778600000},"page":"533-546","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Linial for lists"],"prefix":"10.1007","volume":"35","author":[{"given":"Yannic","family":"Maus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2062-9896","authenticated-orcid":false,"given":"Tigran","family":"Tonoyan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,5,17]]},"reference":[{"key":"424_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V., Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: FOCS, pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"424_CR2","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Efron, Y., Hirvonen, J., Maus, Y., Olivetti, D., Suomela, J.: Classification of distributed binary labeling problems. In: DISC, pp. 17:1\u201317:17 (2020)","DOI":"10.1145\/3382734.3405703"},{"key":"424_CR3","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Hirvonen, J., Olivetti, D., Rabie, M., Suomela, J.: Lower bounds for maximal matchings and maximal independent sets. In: FOCS, pp. 481\u2013497 (2019)","DOI":"10.1109\/FOCS.2019.00037"},{"key":"424_CR4","doi-asserted-by":"crossref","unstructured":"Balliu, A., Brandt, S., Olivetti, D.: Distributed lower bounds for ruling sets. In: FOCS, pp. 365\u2013376 (2020)","DOI":"10.1109\/FOCS46700.2020.00042"},{"key":"424_CR5","doi-asserted-by":"crossref","unstructured":"Balliu, A., Hirvonen, J., Lenzen, C., Olivetti, D., Suomela, J.: Locality of not-so-weak coloring. In: SIROCCO, pp. 37\u201351 (2019)","DOI":"10.1007\/978-3-030-24922-9_3"},{"key":"424_CR6","doi-asserted-by":"crossref","unstructured":"Balliu, A., Kuhn, F., Olivetti, D.: Distributed edge coloring in time quasi-polylogarithmic in delta. In: PODC, pp. 289\u2013298 (2020)","DOI":"10.1145\/3382734.3405710"},{"key":"424_CR7","doi-asserted-by":"crossref","unstructured":"Bamberger, P., Kuhn, F., Maus, Y.: Efficient deterministic distributed coloring with small bandwidth. In: Y.\u00a0Emek, C.\u00a0Cachin (eds.) PODC, pp. 243\u2013252. ACM (2020)","DOI":"10.1145\/3382734.3404504"},{"issue":"5","key":"424_CR8","doi-asserted-by":"publisher","first-page":"47:1","DOI":"10.1145\/2979675","volume":"63","author":"L Barenboim","year":"2016","unstructured":"Barenboim, L.: Deterministic ($$Delta $$ + 1)-coloring in sublinear (in $$Delta $$) time in static, dynamic, and faulty networks. J. ACM 63(5), 47:1-47:22 (2016)","journal-title":"J. ACM"},{"issue":"5\u20136","key":"424_CR9","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1007\/s00446-009-0088-2","volume":"22","author":"L Barenboim","year":"2010","unstructured":"Barenboim, L., Elkin, M.: Sublogarithmic distributed MIS algorithm for sparse graphs using Nash-Williams decomposition. Distribut. Comput. 22(5\u20136), 363\u2013379 (2010)","journal-title":"Distribut. Comput."},{"issue":"5","key":"424_CR10","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2027216.2027221","volume":"58","author":"L Barenboim","year":"2011","unstructured":"Barenboim, L., Elkin, M.: Deterministic distributed vertex coloring in polylogarithmic time. J. ACM 58(5), 23:1-23:25 (2011)","journal-title":"J. ACM"},{"key":"424_CR11","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M.: Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers (2013)","DOI":"10.1007\/978-3-031-02009-4"},{"key":"424_CR12","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: PODC, pp. 437\u2013446 (2018)","DOI":"10.1145\/3212734.3212769"},{"issue":"1","key":"424_CR13","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1137\/12088848X","volume":"43","author":"L Barenboim","year":"2014","unstructured":"Barenboim, L., Elkin, M., Kuhn, F.: Distributed (Delta+1)-coloring in linear (in delta) time. SIAM J. Comput. 43(1), 72\u201395 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"424_CR14","doi-asserted-by":"publisher","first-page":"20:1","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), 20:1-20:45 (2016)","journal-title":"J. ACM"},{"key":"424_CR15","unstructured":"Bernshteyn, A.: A fast distributed algorithm for ($$Delta $$+1)-edge-coloring. CoRR abs\/2006.15703 (2020). arXiv:2006.15703"},{"key":"424_CR16","doi-asserted-by":"crossref","unstructured":"Brandt, S.: An automatic speedup theorem for distributed problems. In: PODC, pp. 379\u2013388 (2019)","DOI":"10.1145\/3293611.3331611"},{"key":"424_CR17","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: STOC, pp. 479\u2013488 (2016)","DOI":"10.1145\/2897518.2897570"},{"key":"424_CR18","doi-asserted-by":"crossref","unstructured":"Brandt, S., Olivetti, D.: Truly tight-in-$$\\Delta $$ bounds for bipartite maximal matching and variants. In: PODC, pp. 69\u201378. ACM (2020)","DOI":"10.1145\/3382734.3405745"},{"issue":"1","key":"424_CR19","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/17M1117537","volume":"48","author":"Y Chang","year":"2019","unstructured":"Chang, Y., Kopelowitz, T., Pettie, S.: An exponential separation between randomized and deterministic complexity in the LOCAL model. SIAM J. Comput. 48(1), 122\u2013143 (2019)","journal-title":"SIAM J. Comput."},{"key":"424_CR20","doi-asserted-by":"crossref","unstructured":"Chang, Y., Li, W., Pettie, S.: An optimal distributed ($$\\Delta $$+1)-coloring algorithm? In: STOC, pp. 445\u2013456 (2018)","DOI":"10.1145\/3188745.3188964"},{"key":"424_CR21","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/BF02772959","volume":"51","author":"P Erd\u00f6s","year":"1985","unstructured":"Erd\u00f6s, P., Frankl, P., F\u00fcredi, Z.: Families of finite sets in which no set is covered by the union of r others. Israel J. Math. 51, 79\u201389 (1985)","journal-title":"Israel J. Math."},{"key":"424_CR22","doi-asserted-by":"crossref","unstructured":"Fischer, M., Ghaffari, M., Kuhn, F.: Deterministic distributed edge-coloring via hypergraph maximal matching. In: FOCS, pp. 180\u2013191 (2017)","DOI":"10.1109\/FOCS.2017.25"},{"key":"424_CR23","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Heinrich, M., Kosowski, A.: Local conflict coloring. In: FOCS, pp. 625\u2013634 (2016)","DOI":"10.1109\/FOCS.2016.73"},{"key":"424_CR24","unstructured":"Fraigniaud, P., Paz, A.: The topology of local computing in networks. In: ICALP, pp. 128:1\u2013128:18 (2020)"},{"issue":"1","key":"424_CR25","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1002\/net.20293","volume":"54","author":"C Gavoille","year":"2009","unstructured":"Gavoille, C., Klasing, R., Kosowski, A., Kuszner, L., Navarra, A.: On the complexity of distributed graph coloring with local minimality constraints. Networks 54(1), 12\u201319 (2009)","journal-title":"Networks"},{"key":"424_CR26","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Harris, D.G., Kuhn, F.: On derandomizing local distributed algorithms. In: FOCS, pp. 662\u2013673 (2018)","DOI":"10.1109\/FOCS.2018.00069"},{"key":"424_CR27","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Hirvonen, J., Kuhn, F., Maus, Y.: Improved distributed delta-coloring. In: PODC, pp. 427\u2013436 (2018)","DOI":"10.1145\/3212734.3212764"},{"key":"424_CR28","unstructured":"Ghaffari, M., Hirvonen, J., Kuhn, F., Maus, Y., Suomela, J., Uitto, J.: Improved distributed degree splitting and edge coloring. In: DISC, pp. 19:1\u201319:15 (2017)"},{"key":"424_CR29","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y.: On the complexity of local distributed graph problems. In: STOC, pp. 784\u2013797 (2017)","DOI":"10.1145\/3055399.3055471"},{"key":"424_CR30","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Kuhn, F., Maus, Y., Uitto, J.: Deterministic distributed edge-coloring with fewer colors. In: STOC, pp. 418\u2013430 (2018)","DOI":"10.1145\/3188745.3188906"},{"key":"424_CR31","doi-asserted-by":"crossref","unstructured":"Ghaffari, M., Su, H.: Distributed degree splitting, edge coloring, and orientations. In: SODA, pp. 2505\u20132523 (2017)","DOI":"10.1137\/1.9781611974782.166"},{"key":"424_CR32","doi-asserted-by":"crossref","unstructured":"Harris, D.G.: Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In: FOCS, pp. 700\u2013724 (2019)","DOI":"10.1109\/FOCS.2019.00048"},{"issue":"4","key":"424_CR33","doi-asserted-by":"publisher","first-page":"19:1","DOI":"10.1145\/3178120","volume":"65","author":"DG Harris","year":"2018","unstructured":"Harris, D.G., Schneider, J., Su, H.: Distributed ($$Delta $$ +1)-coloring in sublogarithmic rounds. J. ACM 65(4), 19:1-19:21 (2018)","journal-title":"J. ACM"},{"key":"424_CR34","doi-asserted-by":"crossref","unstructured":"Hefetz, D., Kuhn, F., Maus, Y., Steger, A.: Polynomial lower bound for distributed graph coloring in a weak LOCAL model. In: DISC, pp. 99\u2013113 (2016)","DOI":"10.1007\/978-3-662-53426-7_8"},{"key":"424_CR35","first-page":"257","volume":"22","author":"FK Hwang","year":"1987","unstructured":"Hwang, F.K., S\u00f3s, V.T.: Non-adaptive hypergeometric group testing. Studia Scient. Math. Hungaria 22, 257\u2013263 (1987)","journal-title":"Studia Scient. Math. Hungaria"},{"key":"424_CR36","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: SPAA, pp. 138\u2013144 (2009)","DOI":"10.1145\/1583991.1584032"},{"key":"424_CR37","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Faster deterministic distributed coloring through recursive list coloring. In: SODA, pp. 1244\u20131259 (2020)","DOI":"10.1137\/1.9781611975994.76"},{"key":"424_CR38","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Local computation: Lower and upper bounds. Journal of the ACM 63(2),(2016)","DOI":"10.1145\/2742012"},{"key":"424_CR39","doi-asserted-by":"crossref","unstructured":"Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: PODC, pp. 7\u201315 (2006)","DOI":"10.1145\/1146381.1146387"},{"key":"424_CR40","doi-asserted-by":"crossref","unstructured":"Laurinharju, J., Suomela, J.: Brief announcement: Linial\u2019s lower bound made easy. In: PODC, pp. 377\u2013378 (2014)","DOI":"10.1145\/2611462.2611505"},{"issue":"1","key":"424_CR41","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."},{"key":"424_CR42","doi-asserted-by":"crossref","unstructured":"Maus, Y.: Distributed graph coloring made easy. In: SPAA, pp. 362\u2013372 (2021)","DOI":"10.1145\/3409964.3461804"},{"issue":"3","key":"424_CR43","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1137\/0404036","volume":"4","author":"M Naor","year":"1991","unstructured":"Naor, M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discret. Math. 4(3), 409\u2013412 (1991)","journal-title":"SIAM J. Discret. Math."},{"issue":"2","key":"424_CR44","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distribut. Comput. 14(2), 97\u2013100 (2001)","journal-title":"Distribut. Comput."},{"key":"424_CR45","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: STOC, pp. 581\u2013592 (1992)","DOI":"10.1145\/129712.129769"},{"key":"424_CR46","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-Sensitive Approach","author":"D Peleg","year":"2000","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia (2000)"},{"key":"424_CR47","doi-asserted-by":"crossref","unstructured":"Rozhon, V., Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: STOC, pp. 350\u2013363. ACM (2020)","DOI":"10.1145\/3357713.3384298"},{"key":"424_CR48","doi-asserted-by":"crossref","unstructured":"Su, H., Vu, H.T.: Towards the locality of vizing\u2019s theorem. In: STOC, pp. 355\u2013364 (2019)","DOI":"10.1145\/3313276.3316393"},{"key":"424_CR49","doi-asserted-by":"crossref","unstructured":"Szegedy, M., Vishwanathan, S.: Locality based graph coloring. In: STOC, pp. 201\u2013207 (1993)","DOI":"10.1145\/167088.167156"},{"key":"424_CR50","first-page":"25","volume":"3","author":"V Vizing","year":"1964","unstructured":"Vizing, V.: On an estimate of the chromatic class of a p-graph. Diskret. Analiz 3, 25\u201330 (1964)","journal-title":"Diskret. Analiz"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00424-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-022-00424-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-022-00424-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,30]],"date-time":"2022-10-30T08:11:49Z","timestamp":1667117509000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-022-00424-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,17]]},"references-count":50,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["424"],"URL":"https:\/\/doi.org\/10.1007\/s00446-022-00424-y","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2022,5,17]]},"assertion":[{"value":"15 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 May 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}