{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,11]],"date-time":"2025-11-11T13:46:17Z","timestamp":1762868777983,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T00:00:00Z","timestamp":1646352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/S03353X\/1"],"award-info":[{"award-number":["EP\/S03353X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"SNSF Excellence","award":["200020B_182865\/1"],"award-info":[{"award-number":["200020B_182865\/1"]}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1991\/1"],"award-info":[{"award-number":["1991\/1"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"United States-Israel Binational Science Foundation (BSF), Israel"},{"name":"United States National Science Foundation"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2022,4,30]]},"abstract":"<jats:p>\n            The problem of (\u0394 +1)-vertex coloring a graph of maximum degree \u0394 has been extremely well studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA\u201918, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized algorithm for maintaining a (\u0394 +1)-coloring with\n            <jats:italic>O<\/jats:italic>\n            (log \u0394) expected amortized update time. In this article, we present an improved randomized algorithm for (\u0394 +1)-coloring that achieves\n            <jats:italic>O<\/jats:italic>\n            (1) amortized update time and show that this bound holds not only in expectation but also with high probability.\n          <\/jats:p>\n          <jats:p>\n            Our starting point is the state-of-the-art randomized algorithm for maintaining a maximal matching (Solomon, FOCS\u201916). We carefully build on the approach of Solomon, but, due to inherent differences between the maximal matching and (\u0394 +1)-coloring problems, we need to deviate significantly from it in several crucial and highly nontrivial points.\n            <jats:xref ref-type=\"fn\">\n              <jats:sup>1<\/jats:sup>\n            <\/jats:xref>\n          <\/jats:p>","DOI":"10.1145\/3494539","type":"journal-article","created":{"date-parts":[[2022,3,4]],"date-time":"2022-03-04T11:32:35Z","timestamp":1646393555000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Fully Dynamic (\u0394 +1)-Coloring in\n            <i>O<\/i>\n            (1) Update Time"],"prefix":"10.1145","volume":"18","author":[{"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"IDSIA, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Janardhan","family":"Kulkarni","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Quanquan C.","family":"Liu","sequence":"additional","affiliation":[{"name":"MIT CSAIL, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shay","family":"Solomon","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,3,4]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027221"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/130914140"},{"key":"e_1_3_3_6_2","series-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201920)","first-page":"11:1\u201311:21","volume":"168","author":"Bera Suman K.","year":"2020","unstructured":"Suman K. Bera, Amit Chakrabarti, and Prantar Ghosh. 2020. Graph coloring via degeneracy in streaming and other space-conscious models. In Proceedings of the International Colloquium on Automata, Languages, and Programming (ICALP\u201920), Leibniz International Proceedings in Informatics, Vol. 168. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 11:1\u201311:21."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-59250-3_8"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.1"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.54"},{"key":"e_1_3_3_10_2","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Bhattacharya Sayan","year":"2019","unstructured":"Sayan Bhattacharya and Janardhan Kulkarni. 2019. Deterministically maintaining a \\( (2 + \\epsilon) \\) -approximate minimum vertex cover in O \\( (1\/\\epsilon ^2) \\) amortized update time. In ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)."},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.37236\/9931"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22459"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1587"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.10.043"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.90"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/800119.803884"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2019.142"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055493"},{"key":"e_1_3_3_19_2","article-title":"Explicit and implicit dynamic coloring of graphs with bounded arboricity","volume":"2002","author":"Henzinger Monika","year":"2020","unstructured":"Monika Henzinger, Stefan Neumann, and Andreas Wiese. 2020. Explicit and implicit dynamic coloring of graphs with bounded arboricity. CoRR abs\/2002.10142. https:\/\/arxiv.org\/abs\/2002.10142.","journal-title":"CoRR"},{"key":"e_1_3_3_20_2","unstructured":"Monika Henzinger and Pan Peng. 2019. Constant-time dynamic ( \\( \\Delta \\) +1)-coloring and weight approximation for minimum spanning forest: Dynamic algorithms meet property testing. arxiv:1907.04745. Retrieved from http:\/\/arxiv.org\/abs\/1907.04745."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00085-6"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3001582"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/11786986_21"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00198-1"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993812"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2019.14"},{"key":"e_1_3_3_28_2","unstructured":"Lecture Notes in Computer Science (CIAC\u201921) B. Martin D. Paulusma S. Smith Colouring graphs of bounded diameter in the absence of small cycles 2021"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_3_30_2","article-title":"Hypergraph two-coloring in the streaming model","volume":"1512","author":"Radhakrishnan Jaikumar","year":"2015","unstructured":"Jaikumar Radhakrishnan, Saswata Shannigrahi, and Rakesh Venkat. 2015. Hypergraph two-coloring in the streaming model. CoRR abs\/1512.04188. http:\/\/arxiv.org\/abs\/1512.04188.","journal-title":"CoRR"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.43"},{"issue":"3","key":"e_1_3_3_32_2","first-page":"41:1\u201341:24","article-title":"Improved dynamic graph coloring","volume":"16","author":"Solomon Shay","year":"2020","unstructured":"Shay Solomon and Nicole Wein. 2020. Improved dynamic graph coloring. ACM Trans. Algor. 16, 3 (2020), 41:1\u201341:24.","journal-title":"ACM Trans. Algor."},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a006"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494539","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494539","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:43Z","timestamp":1750193323000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494539"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,4]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,4,30]]}},"alternative-id":["10.1145\/3494539"],"URL":"https:\/\/doi.org\/10.1145\/3494539","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2022,3,4]]},"assertion":[{"value":"2020-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-03-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}