In the dynamic edge coloring problem one must maintain a graph of maximum degree $\Delta$ using at most $\Delta + c$ colors, while handling edge insertions and deletions. The main performance measure is the recourse, i.e., the number of edges that need to be recolored after an update. This work studies the problem on forests—the simplest graph class that already captures much of its difficulty.
We consider both the incremental model (only edge insertions) and the fully dynamic model (edges may also be deleted). In the deterministic setting we first analyze the natural greedy algorithm. In the incremental model greedy achieves an amortized recourse of $O\bigl(\frac{1}{c + \sqrt{\Delta}}\bigr)$, and this bound is tight up to tie‑breaking. By contrast, in a fully dynamic forest greedy can be forced to incur $\Omega(\log_{\Delta} n)$ amortized recourse.
To partially overcome this limitation, we present an optimal non‑greedy algorithm. For rooted fully dynamic forests with $c = \Delta - 2$, the algorithm attains $O(1)$ amortized recourse.
In the randomized setting we propose a natural distribution‑maintaining algorithm. In the incremental model it achieves expected amortized recourse $\Theta\bigl(\frac{1}{\Delta}\bigr)$, which we prove optimal for every constant $c$. In the fully dynamic model the same algorithm yields expected recourse $\Theta\bigl(\min\{\frac{\Delta}{c}, \log_{\Delta} n\}\bigr)$ for $c>0$ and $\Theta(\log_{\Delta} n)$ for $c=0$. We show the $c=0$ bound is tight and establish an $\Omega(1)$ lower bound for any constant $c$.
Blogger's Review: The paper offers a thorough complexity landscape for dynamic edge coloring on forests, highlighting both the limits of greedy strategies and the potential of tailored algorithms, which should inspire further advances on richer graph families.