@inproceedings{11825,
  abstract     = {We give a fully dynamic (Las-Vegas style) algorithm with constant expected amortized time per update that maintains a proper (Δ+1)-vertex coloring of a graph with maximum degree at most Δ. This improves upon the previous O(log Δ)-time algorithm by Bhattacharya et al. (SODA 2018). Our algorithm uses an approach based on assigning random ranks to vertices and does not need to maintain a hierarchical graph decomposition. We show that our result does not only have optimal running time, but is also optimal in the sense that already deciding whether a Δ-coloring exists in a dynamically changing graph with maximum degree at most Δ takes Ω(log n) time per operation.},
  author       = {Henzinger, Monika H and Peng, Pan},
  booktitle    = {37th International Symposium on Theoretical Aspects of Computer Science},
  isbn         = {9783959771405},
  issn         = {1868-8969},
  location     = {Montpellier, France},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Constant-time dynamic (Δ+1)-coloring}},
  doi          = {10.4230/LIPIcs.STACS.2020.53},
  volume       = {154},
  year         = {2020},
}