{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T06:38:53Z","timestamp":1774334333199,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":26,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819571260","type":"print"},{"value":"9789819571277","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-981-95-7127-7_17","type":"book-chapter","created":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T10:07:07Z","timestamp":1770977227000},"page":"247-262","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Generalizing Brooks\u2019 Theorem via\u00a0Partial Coloring Is Hard Classically and\u00a0Locally"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7973-1361","authenticated-orcid":false,"given":"Jan","family":"Bok","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7471-7499","authenticated-orcid":false,"given":"Avinandan","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-9676-5451","authenticated-orcid":false,"given":"Anna","family":"Gujgiczer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9518-6386","authenticated-orcid":false,"given":"Nikola","family":"Jedli\u010dkov\u00e1","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2026,2,14]]},"reference":[{"key":"17_CR1","doi-asserted-by":"crossref","unstructured":"Awerbuch, B., Goldberg, A.V.,\u00a0Luby, M., Plotkin, S.A.: Network decomposition and locality in distributed computation. In: 30th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 364\u2013369 (1989)","DOI":"10.1109\/SFCS.1989.63504"},{"key":"17_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-030-24922-9_3","volume-title":"Structural Information and Communication Complexity","author":"A Balliu","year":"2019","unstructured":"Balliu, A., Hirvonen, J., Lenzen, C., Olivetti, D., Suomela, J.: Locality of not-so-weak coloring. In: Censor-Hillel, K., Flammini, M. (eds.) SIROCCO 2019. LNCS, vol. 11639, pp. 37\u201351. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-24922-9_3"},{"key":"17_CR3","doi-asserted-by":"crossref","unstructured":"Barenboim, L., Elkin, M., Goldenberg, U.: Locally-iterative distributed ($$\\Delta $$ + 1)-coloring and applications. J. ACM 69(1), 5:1\u20135:26 (2022)","DOI":"10.1145\/3486625"},{"key":"17_CR4","doi-asserted-by":"crossref","unstructured":"Bourreau, Y.,\u00a0Brandt, S.,\u00a0Nolin, A.: Faster distributed $$\\Delta $$-coloring via ruling subgraphs. CoRR arxiv:2503.04320 (2025)","DOI":"10.1145\/3717823.3718320"},{"key":"17_CR5","unstructured":"Bousquet, N.,\u00a0Feuilloley, L.,\u00a0Zeitoun,: Local certification of local properties: tight bounds, trade-offs and new parameters. In: 41st International Symposium on Theoretical Aspects of Computer Science (STACS), vol. 289 of LIPIcs, pp. 21:1\u201321:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"17_CR6","doi-asserted-by":"crossref","unstructured":"Brandt, S.: An automatic speedup theorem for distributed problems. In: 38th ACM Symposium on Principles of Distributed Computing (PODC), pp. 379\u2013388 (2019)","DOI":"10.1145\/3293611.3331611"},{"key":"17_CR7","doi-asserted-by":"crossref","unstructured":"Brooks, R.L.: On colouring the nodes of a network. In: Mathematical Proceedings of the Cambridge Philosophical Society, vol. 37, pp. 194\u2013197. Cambridge University Press (1941)","DOI":"10.1017\/S030500410002168X"},{"key":"17_CR8","unstructured":"Das, A.,\u00a0Fraigniaud, P.,\u00a0Ros\u00e9n, A.: Distributed partial coloring via gradual rounding. In: 27th International Conference on Principles of Distributed Systems (OPODIS), vol. 286 of LIPIcs, pp. 30:1\u201330:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2023)"},{"key":"17_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, M., Halld\u00f3rsson, M.M.,\u00a0Maus, Y.: Fast distributed Brooks\u2019 theorem. In:\u00a0Bansal, N.,\u00a0Nagarajan, V. (eds.) Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA 2023, Florence, Italy, 22\u201325 January 2023, pp. 2567\u20132588. SIAM (2023)","DOI":"10.1137\/1.9781611977554.ch98"},{"key":"17_CR10","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P.,\u00a0Heinrich, M.,\u00a0Kosowski, A.: Local conflict coloring. In:\u00a0Dinur, I. (ed.) 57th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 625\u2013634 (2016)","DOI":"10.1109\/FOCS.2016.73"},{"key":"17_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Francisco (1979)"},{"key":"17_CR12","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.,\u00a0Grunau, C.: Faster deterministic distributed MIS and approximate matching. In: 55th ACM Symposium on Theory of Computing (STOC), pp. 1777\u20131790 (2023)","DOI":"10.1145\/3564246.3585243"},{"key":"17_CR13","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.,\u00a0Grunau,: Near-optimal deterministic network decomposition and ruling set, and improved MIS. In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pp. 2148\u20132179 (2024)","DOI":"10.1109\/FOCS61266.2024.00007"},{"key":"17_CR14","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.,\u00a0Hirvonen, J.,\u00a0Kuhn, F.,\u00a0Maus, Y.: Improved distributed Delta-coloring. In:\u00a0Newport, C.,\u00a0Keidar, I. (eds.) Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, 23\u201327 July 2018, pp. 427\u2013436. ACM (2018)","DOI":"10.1145\/3212734.3212764"},{"key":"17_CR15","doi-asserted-by":"crossref","unstructured":"Ghaffari, M.,\u00a0Kuhn, F.: Deterministic distributed vertex coloring: simpler, faster, and without network decomposition. In: 62nd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 1009\u20131020 (2021)","DOI":"10.1109\/FOCS52979.2021.00101"},{"issue":"1","key":"17_CR16","first-page":"1","volume":"12","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1\u201333 (2016)","journal-title":"Theory Comput."},{"key":"17_CR17","doi-asserted-by":"crossref","unstructured":"Kuhn, F.: Weak graph colorings: distributed algorithms and applications. In: 21st ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 138\u2013144 (2009)","DOI":"10.1145\/1583991.1584032"},{"key":"17_CR18","doi-asserted-by":"crossref","unstructured":"Kuhn, F.,\u00a0Moscibroda, T.,\u00a0Wattenhofer, R.: What cannot be computed locally! In: Proceedings of the 23rd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 300\u2013309. ACM (2004)","DOI":"10.1145\/1011767.1011811"},{"issue":"1","key":"17_CR19","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":"17_CR20","unstructured":"Maus, Y.,\u00a0Tonoyan, T.: Local conflict coloring revisited: linial for lists. In: 34th International Symposium on Distributed Computing (DISC), vol. 179 of LIPIcs, pp. 16:1\u201316:18. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2020)"},{"issue":"6","key":"17_CR21","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.J.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"17_CR22","doi-asserted-by":"crossref","unstructured":"Panconesi, A., Srinivasan, A.: The local nature of $$\\Delta $$-coloring and its algorithmic applications. Combinatorica 15(2), 255\u2013280 (1995)","DOI":"10.1007\/BF01200759"},{"issue":"2","key":"17_CR23","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A Panconesi","year":"1996","unstructured":"Panconesi, A., Srinivasan, A.: On the complexity of distributed network decomposition. J. Algor. 20(2), 356\u2013374 (1996)","journal-title":"J. Algor."},{"key":"17_CR24","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (2000)","DOI":"10.1137\/1.9780898719772"},{"key":"17_CR25","doi-asserted-by":"crossref","unstructured":"Rozho\u0148, V.,\u00a0Ghaffari, M.: Polylogarithmic-time deterministic network decomposition and distributed derandomization. In: 52nd ACM Symposium on Theory of Computing (STOC), pp. 350\u2013363 (2020)","DOI":"10.1145\/3357713.3384298"},{"key":"17_CR26","unstructured":"Wattenhofer, R.,\u00a0Uitto, J.: Locality lower bounds (Chapter 8). In: Lecture notes. From the course \u201cPrinciples of Distributed Computing (PODC) All-Stars;; at ETH Z\u00fcrich (2025). Accessed 17 Sept 2025"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-95-7127-7_17","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,24]],"date-time":"2026-03-24T04:16:11Z","timestamp":1774325771000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-95-7127-7_17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9789819571260","9789819571277"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-981-95-7127-7_17","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"14 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WALCOM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference and Workshops on Algorithms and Computation","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Perugia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 March 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"6 March 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"walcom2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/mozart.diei.unipg.it\/walcom2026","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}