2019/10/04 by Bhattacharya, Sayan, Grandoni, Fabrizio, Kulkarni, Janardhan +2
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1910.02063
The problem of (vertex) (Δ+1)-coloring a graph of maximum degree Δ has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic setting, almost nothing was known until recently. In SODA'18, Bhattacharya, Chakrabarty, Henzinger and Nanongkai devised a randomized data structure for maintaining a (Δ+1)-coloring with O(log Δ) expected amortized update time. In this paper, we present a (Δ+1)-coloring data structure that achieves a constant amortized update time and show that this time bound holds not only in expectation but also with high probability.