2026-07-25T12:38:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23456 2025-10-02T12:55:40Z ddc:004 open_access

Faster Dynamic (Δ+1)-Coloring Against Adaptive Adversaries Flin, Maxime Halldórsson, Magnús M. Dynamic Graph Algorithms Coloring We consider the problem of maintaining a proper (Δ + 1)-vertex coloring in a graph on n-vertices and maximum degree Δ undergoing edge insertions and deletions. We give a randomized algorithm with amortized update time Õ(n^{2/3}) against adaptive adversaries, meaning that updates may depend on past decisions by the algorithm. This improves on the very recent Õ(n^{8/9})-update-time algorithm by Behnezhad, Rajaraman, and Wasim (SODA 2025) and matches a natural barrier for dynamic (Δ+1)-coloring algorithms. The main improvements are on the densest regions of the graph, where we use structural hints from the study of distributed graph algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maxime Flin and Magnús M. Halldórsson 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.79 urn:nbn:de:0030-drops-234560 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.79 eng https://creativecommons.org/licenses/by/4.0/legalcode