10 citations · 54 across the 49 of their papers we have counts for
Showing 2019 · cs.DSShow all
2 papers · 2 filters
cs.DS2019★ 10 cited
Fully Dynamic -Coloring in Constant Update Time
Sayan Bhattacharya, Fabrizio Grandoni, Janardhan Kulkarni +2
The problem of (vertex) -coloring a graph of maximum degree has been extremely well-studied over the years in various settings and models. Surprisingly, for the dynamic…
cs.DS2019
Improved Dynamic Graph Coloring
Shay Solomon, Nicole Wein
This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within $n^{1-ε…