在 动态边着色 问题中，需要在图的最大度数 $\Delta$ 下，仅使用至多 $\Delta + c$ 种颜色来维护图的着色，并在每次边的插入或删除后重新着色。关键指标是 recourse，即重新着色的边数。本文聚焦于森林——这一最简图类，却已能体现问题的核心难度。
我们分别考察 增量模型（仅插入边）和 全动态模型（边可插入亦可删除）。在确定性设定下，首先分析最自然的贪心算法。结果表明，在增量模型中，贪心能够实现 $O\bigl(\frac{1}{c + \sqrt{\Delta}}\bigr)$ 的摊销 recourse，并且该上界在仅通过 tie‑breaking 已经是紧的。相反，在全动态森林中，贪心可以被迫产生 $\Omega(\log_{\Delta} n)$ 的摊销 recourse。
为克服贪心在全动态情形下的局限，我们设计了一种非贪心的最优算法。该算法在 根向（即每棵树都有固定根）全动态森林且 $c = \Delta - 2$ 时，仅需 $O(1)$ 的摊销 recourse。
在随机化设定下，我们提出一种保持颜色分布的自然算法。增量模型下，它的期望摊销 recourse 为 $\Theta\bigl(\frac{1}{\Delta}\bigr)$，并且对任意常数 $c$ 此上界是最优的。全动态模型中，同一算法的期望 recourse 为 $\Theta\bigl(\min\{\frac{\Delta}{c}, \log_{\Delta} n\}\bigr)$（当 $c>0$）以及 $\Theta(\log_{\Delta} n)$（当 $c=0$）。我们证明了 $c=0$ 时的下界是紧的，并给出对所有常数 $c$ 的 $\Omega(1)$ 下界。
博主点评：本文在最基础的森林结构上系统地刻画了动态边着色的复杂度，既给出贪心算法的极限，也提供了在特定约束下的最优方案，对后续在更一般图类上的研究具有重要启发。