{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T02:23:00Z","timestamp":1775874180687,"version":"3.50.1"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,12,14]],"date-time":"2023-12-14T00:00:00Z","timestamp":1702512000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"funder":[{"name":"European Union\u2019s Horizon 2020 Research and Innovation Programme","award":["755839"],"award-info":[{"award-number":["755839"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Parallel Comput."],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            In this article, we present a deterministic\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {CONGEST}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            algorithm to compute an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            \u0394)-vertex coloring in\n            <jats:italic>O<\/jats:italic>\n            (\u0394 \/\n            <jats:italic>k<\/jats:italic>\n            )+log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            rounds, where \u0394 is the maximum degree of the network graph and\n            <jats:italic>k<\/jats:italic>\n            \u2265 1 can be freely chosen. The algorithm is extremely simple: each node locally computes a sequence of colors and then it\n            <jats:italic>tries colors<\/jats:italic>\n            from the sequence in batches of size\n            <jats:italic>k<\/jats:italic>\n            . Our algorithm subsumes many important results in the history of distributed graph coloring as special cases, including Linial\u2019s color reduction [Linial, FOCS\u201987], the celebrated locally iterative algorithm from [Barenboim, Elkin, Goldenberg, PODC\u201918], and various algorithms to compute defective and arbdefective colorings. Our algorithm can smoothly scale between several of these previous results and also simplifies the state-of-the-art (\u0394 +1)-coloring algorithm. At the cost of losing some of the algorithm\u2019s simplicity we also provide a\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>k<\/jats:italic>\n            \u0394)-coloring algorithm in\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(\\sqrt {\\Delta \/k})+\\log ^{*} n\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            rounds. We also provide improved deterministic algorithms for ruling sets, and, additionally, we provide a tight characterization for one-round color reduction algorithms.\n          <\/jats:p>","DOI":"10.1145\/3605896","type":"journal-article","created":{"date-parts":[[2023,8,17]],"date-time":"2023-08-17T12:05:34Z","timestamp":1692273934000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Distributed Graph Coloring Made Easy"],"prefix":"10.1145","volume":"10","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4062-6991","authenticated-orcid":false,"given":"Yannic","family":"Maus","sequence":"first","affiliation":[{"name":"TU Graz, Austria"}]}],"member":"320","published-online":{"date-parts":[[2023,12,14]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"364","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201989)","author":"Awerbuch Baruch","year":"1989","unstructured":"Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, and Serge A. Plotkin. 1989. Network decomposition and locality in distributed computation. In Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201989). 364\u2013369. DOI:10.1109\/SFCS.1989.63504"},{"key":"e_1_3_2_3_2","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC\u201920)","author":"Balliu Alkida","year":"2020","unstructured":"Alkida Balliu, Sebastian Brandt, Yuval Efron, Juho Hirvonen, Yannic Maus, Dennis Olivetti, and Jukka Suomela. 2020. Classification of distributed binary labeling problems. In Proceedings of the International Symposium on Distributed Computing (DISC\u201920). DOI:10.4230\/LIPIcs.DISC.2020.17"},{"key":"e_1_3_2_4_2","first-page":"481","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201919)","author":"Balliu Alkida","year":"2019","unstructured":"Alkida Balliu, Sebastian Brandt, Juho Hirvonen, Dennis Olivetti, Mika\u00ebl Rabie, and Jukka Suomela. 2019. Lower bounds for maximal matchings and maximal independent sets. In Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201919). 481\u2013497. DOI:10.1145\/3461458"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520027"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538440"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00042"},{"key":"e_1_3_2_8_2","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1007\/978-3-030-24922-9_3","volume-title":"Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201919)","author":"Balliu Alkida","year":"2019","unstructured":"Alkida Balliu, Juho Hirvonen, Christoph Lenzen, Dennis Olivetti, and Jukka Suomela. 2019. Locality of not-so-weak coloring. In Proceedings of the International Colloquium on Structural Information and Communication Complexity (SIROCCO\u201919). 37\u201351. DOI:10.1007\/978-3-030-24922-9_3"},{"key":"e_1_3_2_9_2","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201920)","author":"Bamberger Philipp","year":"2020","unstructured":"Philipp Bamberger, Fabian Kuhn, and Yannic Maus. 2020. Efficient deterministic distributed coloring with small bandwidth. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201920). DOI:10.1145\/3382734.3404504"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2979675"},{"key":"e_1_3_2_11_2","first-page":"111","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC\u201909)","author":"Barenboim Leonid","year":"2009","unstructured":"Leonid Barenboim and Michael Elkin. 2009. Distributed (Delta+1)-Coloring in linear (in Delta) time. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC\u201909). 111\u2013120. DOI:10.1145\/1536414.1536432"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_3_2_14_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02009-4","volume-title":"Distributed Graph Coloring: Fundamentals and Recent Developments","author":"Barenboim Leonid","year":"2013","unstructured":"Leonid Barenboim and Michael Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers."},{"key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"437","DOI":"10.1145\/3212734.3212769","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201918)","author":"Barenboim Leonid","year":"2018","unstructured":"Leonid Barenboim, Michael Elkin, and Uri 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\u201918). 437\u2013446. DOI:10.1145\/3212734.3212769"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3486625"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1137\/12088848X"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/2903137"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2021.10.004"},{"key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1145\/3293611.3331611","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201919)","author":"Brandt Sebastian","year":"2019","unstructured":"Sebastian Brandt. 2019. An automatic speedup theorem for distributed problems. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201919). 379\u2013388. DOI:10.1145\/3293611.3331611"},{"key":"e_1_3_2_21_2","first-page":"479","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201916)","author":"Brandt Sebastian","year":"2016","unstructured":"Sebastian Brandt, Orr Fischer, Juho Hirvonen, Barbara Keller, Tuomo Lempi\u00e4inen, Joel Rybicki, Jukka Suomela, and Jara Uitto. 2016. A lower bound for the distributed Lov\u00e1sz local lemma. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201916). 479\u2013488. DOI:10.1145\/2897518.2897570"},{"key":"e_1_3_2_22_2","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201920)","author":"Brandt Sebastian","year":"2020","unstructured":"Sebastian Brandt and Dennis Olivetti. 2020. Truly tight-in- \\(\\Delta\\) bounds for bipartite maximal matching and variants. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201920). DOI:10.1145\/3382734.3405745"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1249527"},{"key":"e_1_3_2_25_2","doi-asserted-by":"crossref","first-page":"531","DOI":"10.1145\/3293611.3331635","volume-title":"Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC\u201919)","author":"Elkin Michael","year":"2019","unstructured":"Michael Elkin and Shaked Matar. 2019. Near-additive spanners in low polynomial deterministic CONGEST time. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC\u201919). 531\u2013540. DOI:10.1145\/3293611.3331635"},{"key":"e_1_3_2_26_2","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/BF02772959","article-title":"Families of finite sets in which no set is covered by the union of r others","volume":"51","author":"Erd\u00f6s Paul","year":"1985","unstructured":"Paul Erd\u00f6s, Peter Frankl, and Z\u00f3ltan F\u00fcredi. 1985. Families of finite sets in which no set is covered by the union of r others. Israel Journal of Mathematics 51, 1 (1985), 79\u201389.","journal-title":"Israel Journal of Mathematics"},{"key":"e_1_3_2_27_2","first-page":"4409","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923)","author":"Faour Salwa","year":"2023","unstructured":"Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, and V\u00e1clav Rozhon. 2023. Local distributed rounding: Generalized to MIS, matching, set cover, and beyond. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923). SIAM, 4409\u20134447. DOI:10.1137\/1.9781611977554.ch168"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0344-4"},{"key":"e_1_3_2_29_2","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923)","author":"Fischer Manuela","year":"2023","unstructured":"Manuela Fischer, Magn\u00fas M. Halld\u00f3rsson, and Yannic Maus. 2023. Fast distributed brooks\u2019 theorem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923). SIAM. DOI:10.1137\/1.9781611977554.ch98"},{"key":"e_1_3_2_30_2","first-page":"625","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201916)","author":"Fraigniaud Pierre","year":"2016","unstructured":"Pierre Fraigniaud, Marc Heinrich, and Adrian Kosowski. 2016. Local conflict coloring. In Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201916). 625\u2013634. DOI:10.1109\/FOCS.2016.73"},{"key":"e_1_3_2_31_2","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","author":"Fraigniaud Pierre","year":"2020","unstructured":"Pierre Fraigniaud and Ami Paz. 2020. The topology of local computing in networks. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201920). 128:1\u2013128:18. DOI:10.4230\/LIPIcs.ICALP.2020.128"},{"key":"e_1_3_2_32_2","first-page":"2532","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923)","author":"Ghaffari Mohsen","year":"2023","unstructured":"Mohsen Ghaffari, Christoph Grunau, Bernhard Haeupler, Saeed Ilchi, and V\u00e1clav Rozhon. 2023. Improved distributed network decomposition, hitting sets, and spanners, via derandomization. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201923). SIAM, 2532\u20132566. DOI:10.1137\/1.9781611977554.ch97"},{"key":"e_1_3_2_33_2","first-page":"2904","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921)","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari, Christoph Grunau, and V\u00e1clav Rozhon. 2021. Improved deterministic network decomposition. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201921). SIAM, 2904\u20132923. DOI:10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_34_2","first-page":"662","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari, David G. Harris, and Fabian Kuhn. 2018. On derandomizing local distributed algorithms. In Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201918). 662\u2013673. DOI:10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_35_2","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1145\/3212734.3212764","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201918)","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari, Juho Hirvonen, Fabian Kuhn, and Yannic Maus. 2018. Improved distributed delta-coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201918). 427\u2013436. DOI:10.1145\/3212734.3212764"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00101"},{"key":"e_1_3_2_37_2","first-page":"418","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201918)","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari, Fabian Kuhn, Yannic Maus, and Jara Uitto. 2018. Deterministic distributed edge-coloring with fewer colors. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201918). 418\u2013430. DOI:10.1145\/3188745.3188906"},{"key":"e_1_3_2_38_2","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201921)","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2021","unstructured":"Magn\u00fas M. Halld\u00f3rsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. 2021. Efficient randomized distributed coloring in CONGEST. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201921). DOI:10.1145\/3406325.3451089arXiv:2012.14169"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520023"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2022.26"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538438"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79527-6_5"},{"key":"e_1_3_2_43_2","first-page":"700","volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201919)","author":"Harris David G.","year":"2019","unstructured":"David G. Harris. 2019. Distributed local approximation algorithms for maximum matching in graphs and hypergraphs. In Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201919). 700\u2013724. DOI:10.1137\/19M1279241"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178120"},{"key":"e_1_3_2_45_2","first-page":"99","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC\u201916)","author":"Hefetz Dan","year":"2016","unstructured":"Dan Hefetz, Fabian Kuhn, Yannic Maus, and Angelika Steger. 2016. Polynomial lower bound for distributed graph coloring in a weak LOCAL model. In Proceedings of the International Symposium on Distributed Computing (DISC\u201916). 99\u2013113. DOI:10.1007\/978-3-662-53426-7_8"},{"key":"e_1_3_2_46_2","first-page":"138","volume-title":"Proceedings of the ACM Symposium on Parallelism in Algorithms and Architecture (SPAA\u201909)","author":"Kuhn Fabian","year":"2009","unstructured":"Fabian Kuhn. 2009. Weak graph colorings: Distributed algorithms and applications. In Proceedings of the ACM Symposium on Parallelism in Algorithms and Architecture (SPAA\u201909). 138\u2013144. DOI:10.1145\/1583991.1584032"},{"key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"1244","DOI":"10.1137\/1.9781611975994.76","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920)","author":"Kuhn Fabian","year":"2020","unstructured":"Fabian Kuhn. 2020. Faster deterministic distributed coloring through recursive list coloring. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201920). 1244\u20131259. DOI:10.1137\/1.9781611975994.76"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01325-7_19"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/2742012"},{"key":"e_1_3_2_50_2","first-page":"7","volume-title":"Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201906)","author":"Kuhn Fabian","year":"2006","unstructured":"Fabian Kuhn and Roger Wattenhofer. 2006. On the complexity of distributed graph coloring. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC\u201906). 7\u201315. DOI:10.1145\/1146381.1146387"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2020.16"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405694"},{"key":"e_1_3_2_55_2","first-page":"581","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201992)","author":"Panconesi Alessandro","year":"1992","unstructured":"Alessandro Panconesi and Aravind Srinivasan. 1992. Improved distributed algorithms for coloring and network decomposition problems. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201992). 581\u2013592. DOI:10.1145\/129712.129769"},{"key":"e_1_3_2_56_2","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"Distributed Computing: A Locality-sensitive Approach","author":"Peleg David","year":"2000","unstructured":"David Peleg. 2000. Distributed Computing: A Locality-sensitive Approach. SIAM."},{"key":"e_1_3_2_57_2","first-page":"350","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201920)","author":"Rozhon V\u00e1clav","year":"2020","unstructured":"V\u00e1clav Rozhon and Mohsen Ghaffari. 2020. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201920). 350\u2013363. DOI:10.1145\/3357713.3384298"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.09.004"},{"key":"e_1_3_2_59_2","first-page":"257","volume-title":"Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201910)","author":"Schneider Johannes","year":"2010","unstructured":"Johannes Schneider and Roger Wattenhofer. 2010. A new technique for distributed symmetry breaking. In Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC\u201910). ACM, 257\u2013266. DOI:10.1145\/1835698.1835760"},{"key":"e_1_3_2_60_2","first-page":"355","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Su Hsin-Hao","year":"2019","unstructured":"Hsin-Hao Su and Hoa T. Vu. 2019. Towards the locality of Vizing\u2019s theorem. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919). 355\u2013364. DOI:10.1145\/3313276.3316393"},{"key":"e_1_3_2_61_2","first-page":"201","volume-title":"Proceedings of the ACM Symposium on Theory of Computing (STOC\u201993)","author":"Szegedy Mario","year":"1993","unstructured":"Mario Szegedy and Sundar Vishwanathan. 1993. Locality based graph coloring. In Proceedings of the ACM Symposium on Theory of Computing (STOC\u201993). 201\u2013207. DOI:10.1145\/167088.167156"},{"key":"e_1_3_2_62_2","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.","journal-title":"Diskret analiz"}],"container-title":["ACM Transactions on Parallel Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3605896","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3605896","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:19Z","timestamp":1750178179000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3605896"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,14]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3605896"],"URL":"https:\/\/doi.org\/10.1145\/3605896","relation":{},"ISSN":["2329-4949","2329-4957"],"issn-type":[{"value":"2329-4949","type":"print"},{"value":"2329-4957","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,14]]},"assertion":[{"value":"2021-12-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}