Constant-Time Dynamic (?+1)-Coloring

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