{
  "annotation_id": "27dca354-4664-4fd2-97e7-f80de1af9069",
  "date_created": "2026-02-17T05:53:11.887000Z",
  "date_modified": "2026-02-17T05:53:11.887000Z",
  "file_hash": "c71853afd4b86465d86ffad0df99fd0d6d4f0c5c2d4cd106442c4e2650b721e7",
  "private": false,
  "record": {
    "abstract": "Several recent results from dynamic and sublinear graph coloring are surveyed. This problem is widely studied and has motivating applications like network topology control, constraint satisfaction, and real-time resource scheduling. Graph coloring algorithms are called colorers. In \\S 1 are defined graph coloring, the dynamic model, and the notion of performance of graph algorithms in the dynamic model. In particular $(\\Delta + 1)$-coloring, sublinear performance, and oblivious and adaptive adversaries are noted and motivated. In \\S 2 the pair of approximately optimal dynamic vertex colorers given in arXiv:1708.09080 are summarized as a warmup for the $(\\Delta + 1)$-colorers. In \\S 3 the state of the art in dynamic $(\\Delta + 1)$-coloring is presented. This section comprises a pair of papers (arXiv:1711.04355 and arXiv:1910.02063) that improve dynamic $(\\Delta + 1)$-coloring from the naive algorithm with $O(\\Delta)$ expected amortized update time to $O(\\log \\Delta)$, then to $O(1)$ with high probability. In \\S 4 the results in arXiv:2411.04418, which gives a sublinear algorithm for $(\\Delta + 1)$-coloring that generalizes oblivious adversaries to adaptive adversaries, are presented.",
    "arxiv_id": "2601.07566",
    "authors": [
      "Noam Benson-Tilsen"
    ],
    "categories": [
      "cs.DS"
    ],
    "license": "http://creativecommons.org/publicdomain/zero/1.0/",
    "title": "Dynamic $(\\Delta + 1)$ Vertex Coloring",
    "url": "https://arxiv.org/abs/2601.07566",
    "version": "v1"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "d06ed47b-7c4d-427b-b0fd-ebfe9c9197ea",
    "id": "arXiv Dataset",
    "type": "Model",
    "variant": "snapshot-2026-01-17",
    "version": "0.1.0"
  },
  "user_id": 1000002
}