Trade-offs in dynamic coloring for bipartite and general graphs

Manas Jyoti Kashyop, N. S. Narayanaswamy, Meghana Nasre +1

We present trade-offs in the incremental and fully dynamic settings to maintian a proper coloring. For any fully dynamic $2$-coloring algorithm, the maximum of the update time, num…