Dynamic -Coloring with Polylogarithmic Worst-Case Update TimeResearch Paper
A graph of maximum degree always has a proper coloring with colors, and the static greedy algorithm finds one in linear time. In the fully dynamic setting the graph undergoes edge insertions and deletions, its maximum degree stays at most , and a proper -coloring must be kept after every update. The recourse of an update is…