Dynamic Edge Coloring of Forests

Haim Kaplan, David Naori, Yaniv Sadeh

In the \emph{dynamic edge coloring} problem, one has to maintain a graph of maximum degree $\hat{I}”$ with at most $\hat{I}”+c$ colors, under edge updates. A prominent objective is to minimize…