Constant-Time Dynamic (Δ+1)-Coloring

Monika Henzinger & Pan Peng
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...
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.