{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T08:50:42Z","timestamp":1781686242208,"version":"3.54.5"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2011,10,1]],"date-time":"2011-10-01T00:00:00Z","timestamp":1317427200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["20008390"],"award-info":[{"award-number":["20008390"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003973","name":"Israel Academy of Sciences and Humanities","doi-asserted-by":"publisher","award":["483\/06"],"award-info":[{"award-number":["483\/06"]}],"id":[{"id":"10.13039\/501100003973","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,10]]},"abstract":"<jats:p>\n            Consider an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph\n            <jats:italic>G<\/jats:italic>\n            = (\n            <jats:italic>V<\/jats:italic>\n            ,\n            <jats:italic>E<\/jats:italic>\n            ) of maximum degree\n            <jats:italic>\u0394<\/jats:italic>\n            , and suppose that each vertex\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            hosts a processor. The processors are allowed to communicate only with their neighbors in\n            <jats:italic>G<\/jats:italic>\n            . The communication is synchronous, that is, it proceeds in discrete rounds.\n          <\/jats:p>\n          <jats:p>\n            In the distributed vertex coloring problem, the objective is to color\n            <jats:italic>G<\/jats:italic>\n            with\n            <jats:italic>\u0394<\/jats:italic>\n            + 1, or slightly more than\n            <jats:italic>\u0394<\/jats:italic>\n            + 1, colors using as few rounds of communication as possible. (The number of rounds of communication will be henceforth referred to as\n            <jats:italic>running time<\/jats:italic>\n            .) Efficient\n            <jats:italic>randomized<\/jats:italic>\n            algorithms for this problem are known for more than twenty years [Alon et al. 1986; Luby 1986]. Specifically, these algorithms produce a (\n            <jats:italic>\u0394<\/jats:italic>\n            + 1)-coloring within\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ) time, with high probability. On the other hand, the best known\n            <jats:italic>deterministic<\/jats:italic>\n            algorithm that requires polylogarithmic time employs\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0394<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) colors. This algorithm was devised in a seminal FOCS\u201987 paper by Linial [1987]. Its running time is\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>*<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ). In the same article, Linial asked whether one can color with significantly less than\n            <jats:italic>\u0394<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            colors in deterministic polylogarithmic time. By now, this question of Linial became one of the most central long-standing open questions in this area.\n          <\/jats:p>\n          <jats:p>\n            In this article, we answer this question in the affirmative, and devise a deterministic algorithm that employs\n            <jats:italic>\u0394<\/jats:italic>\n            1+\n            <jats:italic>o<\/jats:italic>\n            (1) colors, and runs in\n            <jats:italic>polylogarithmic<\/jats:italic>\n            time. Specifically, the running time of our algorithm is\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>\u0394<\/jats:italic>\n            )log\n            <jats:italic>\u0394<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ), for an arbitrarily slow-growing function\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>\u0394<\/jats:italic>\n            ) =\n            <jats:italic>\u03c9<\/jats:italic>\n            (1). We can also produce an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0394<\/jats:italic>\n            1+\n            <jats:italic>\u03b7<\/jats:italic>\n            )-coloring in\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>\u0394<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            )-time, for an arbitrarily small constant\n            <jats:italic>\u03b7<\/jats:italic>\n            &gt; 0, and an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0394<\/jats:italic>\n            )-coloring in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>\u0394\u03f5<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) time, for an arbitrarily small constant\n            <jats:italic>\u03f5<\/jats:italic>\n            &gt; 0. Our results are, in fact, far more general than this. In particular, for a graph of arboricity\n            <jats:italic>a<\/jats:italic>\n            , our algorithm produces an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>a<\/jats:italic>\n            1+\n            <jats:italic>\u03b7<\/jats:italic>\n            )-coloring, for an arbitrarily small constant\n            <jats:italic>\u03b7<\/jats:italic>\n            &gt; 0, in time\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>a<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/2027216.2027221","type":"journal-article","created":{"date-parts":[[2011,10,27]],"date-time":"2011-10-27T13:17:37Z","timestamp":1319721457000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":56,"title":["Deterministic Distributed Vertex Coloring in Polylogarithmic Time"],"prefix":"10.1145","volume":"58","author":[{"given":"Leonid","family":"Barenboim","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Elkin","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90019-2"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"e_1_2_1_3_1","unstructured":"Barenboim L. and Elkin M. 2008a. Distributed (\u0394&thinsp;+&thinsp;1)-coloring in linear (in \u0394) time. http:\/\/arXiv.org\/abs\/0812.1379v2. Barenboim L. and Elkin M. 2008a. Distributed ( \u0394 &thinsp;+&thinsp;1)-coloring in linear (in \u0394 ) time. http:\/\/arXiv.org\/abs\/0812.1379v2."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400757"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536432"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80023-7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190100207"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)90121-X"},{"key":"e_1_2_1_9_1","unstructured":"Gallai T. 1968. On directed paths and circuits. Theory of Graphs Academic Press 115--118. Gallai T. 1968. On directed paths and circuits. Theory of Graphs Academic Press 115--118."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28429"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/0401044"},{"key":"e_1_2_1_12_1","first-page":"205","article-title":"Conditional colorability ii: Bipartite variations","volume":"50","author":"Harary F.","year":"1985","journal-title":"Congressus Numer"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 20th International Parallel and Distributed Processing Symposium.","author":"Kothapalli K."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1583991.1584032"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146387"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.20"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0017"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_2_1_22_1","first-page":"127","article-title":"Nombre chromatique et plus longs chemins d\u2019un graphe","volume":"1","author":"Roy B.","year":"1967","journal-title":"Rev. Francaise Automat. Informat. Recherche Operationelle Ser. Rouge"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835698.1835760"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167156"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027221","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2027216.2027221","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:15Z","timestamp":1750278375000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027221"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":24,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1145\/2027216.2027221"],"URL":"https:\/\/doi.org\/10.1145\/2027216.2027221","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10]]},"assertion":[{"value":"2010-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}