Dynamic 3-Coloring of Bipartite Graphs with Optimal Locality

Yann Bourreau, Filippo Casagrande, Tim Göttlicher +1

We give a dynamic graph algorithm which maintains a 3-coloring in bipartite graphs under edge insertions such that the coloring only changes within a radius of $O(\log n)$ around a…