arxiv: 2605.09711 · v1 · submitted 2026-05-10 · 💻 cs.DS

Recognition: no theorem link

Dynamic Edge Coloring of Forests

Haim Kaplan , David Naori , Yaniv Sadeh

Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:53 UTC · model grok-4.3

classification 💻 cs.DS

keywords dynamic edge coloringforestsrecourseamortized analysisincremental algorithmsfully dynamic algorithmsgreedy algorithmsrandomized algorithms

0 comments

The pith

The natural greedy algorithm maintains (Delta + c)-edge colorings of forests with O(1/(c + sqrt(Delta))) amortized recourse under insertions alone.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that when edges are added one by one to a forest of maximum degree Delta, the ordinary greedy method of assigning the smallest available color and recoloring conflicts as needed keeps the total number of recolors per insertion down to O(1 over c plus square root of Delta). This bound is tight up to how ties are broken. When edges can also be deleted, the same greedy rule can be forced into Omega(log base Delta of n) amortized recolors on some sequences, but a different deterministic algorithm achieves constant recourse on rooted forests when two spare colors are allowed. Randomized methods that maintain a distribution over valid colorings recover Theta(1/Delta) expected recourse in the insertion-only case and Theta of the minimum of Delta over c or log base Delta of n in the fully dynamic case; both randomized bounds are optimal when no extra colors are present.

Core claim

In the deterministic setting the natural greedy algorithm achieves O(1/(c + sqrt(Delta))) amortized recourse in the incremental model on forests and this is tight up to tie-breaking; in contrast, in a fully dynamic forest greedy can be forced to Omega(log_Delta n) amortized recourse. An optimal non-greedy algorithm achieves O(1) amortized recourse for rooted fully dynamic forests when c equals Delta minus 2. In the randomized setting a distribution-maintaining algorithm achieves Theta(1/Delta) expected amortized recourse incrementally and Theta(min(Delta/c, log_Delta n)) expected recourse in the dynamic model, and these randomized results are optimal for c equals 0.

What carries the argument

Recourse, the number of edges whose colors must change on each update, when maintaining a proper edge coloring with at most Delta + c colors on a forest under insertions and deletions.

If this is right

Deterministic greedy coloring of incremental forests uses O(1/(c + sqrt(Delta))) amortized recourse.
The same greedy rule on fully dynamic forests can require Omega(log_Delta n) amortized recourse in the worst case.
A non-greedy deterministic method achieves O(1) amortized recourse on rooted fully dynamic forests when c = Delta - 2.
Randomized distribution maintenance yields Theta(1/Delta) expected incremental recourse and Theta(min(Delta/c, log_Delta n)) expected dynamic recourse.
Both randomized bounds are tight when c = 0.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Acyclicity lets color conflicts propagate only along paths rather than through dense subgraphs, which explains why the recourse bounds improve over general graphs.
Deletions create the main difficulty because they can force long recoloring chains that insertions alone do not trigger.
Maintaining a random valid coloring distribution appears to break the adversarial chains that deterministic greedy encounters after deletions.
The rooted case suggests that a global orientation or hierarchy can replace randomization when two spare colors are available.

Load-bearing premise

The graph stays a forest of maximum degree Delta under every sequence of updates.

What would settle it

A concrete sequence of edge insertions on a forest of maximum degree Delta where the greedy algorithm recolors more than a constant times 1 over (c plus square root of Delta) edges on average per insertion.

Figures

Figures reproduced from arXiv: 2605.09711 by David Naori, Haim Kaplan, Yaniv Sadeh.

**Figure 1.** Figure 1: An example for Definition 2.5 of a layered tree, for ∆ = 3, and κ = 4 with sub-palettes P = {blue, red}, and P = {yellow, green}. In layered coloring, the palette used by a vertex on edges towards its children uniquely determine the palette used by its children towards their children (the complement) and vice versa (unless it is a leaf). even depth has |P| children, and every non-leaf vertex at an odd dept… view at source ↗

**Figure 2.** Figure 2: Visualization for the proof of Theorem 2.4, with sub-palettes P = {blue, red}, and P = {yellow, green}. Bicolored squares abstract layered subtrees where the two colors are used in the next layer. Note that the depth of these subtrees is not illustrated in this figure. The actual depths are as follows: In the initial state we have two perfect layered trees where each leaf is of depth d for d = Θ(log∆ n). T… view at source ↗

**Figure 3.** Figure 3: Illustration of the recoloring process of [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗

**Figure 4.** Figure 4: When merging two layered trees of complementing palettes, recoloring must reach a leaf. In this figure, the right tree is not layered, thus recoloring can be done without reaching a leaf. Recoloring multiple edges that share a vertex is known as a fan in the literature, here a fan over u suffices. 3.2.1 Greedy Logarithmic Amortized Recourse In this sub-section we prove that Greedy has amortized recourse th… view at source ↗

**Figure 5.** Figure 5: Visualization for Lemma 3.5, for ∆ = 3, and κ = 4 with sub-palettes P = {blue, red}, and P = {yellow, green}. A square colored by palette Q ∈ {P, P} is an abstract representation of a Q-layered subtree. We begin by merging two layered trees rooted in v0 and v1 (top). In the end of recoloring the path from v1 to u (bottom), ignoring the edge (p, u), the combined tree rooted at p is Q-layered, where Q ∈ {P, … view at source ↗

**Figure 6.** Figure 6: An example where we fix the coloring of an edge by choosing a color unavailable at both ends. This choice converts a single problem into two, but may be useful in the long-run. In this example, let ∆ = 4 and use only 4 colors. Assume that we need to apply a bicolored flip on the red-blue right spine of the initial coloring (left), and that we choose to truncate the flip using green. We can choose to stop t… view at source ↗

read the original abstract

In the \emph{dynamic edge coloring} problem, one has to maintain a graph of maximum degree $\Delta$ with at most $\Delta+c$ colors, given updates to the edges of the graph. An important objective is to minimize the \emph{recourse}, which is the number of edges being recolored. We study this problem on forests, which is a natural yet nontrivial restriction of the problem. We consider the problem in both \emph{incremental} (edges are only inserted) and \emph{fully dynamic} (edges may be deleted) models. In the deterministic setting, we show that the natural greedy algorithm achieves $O(\frac{1}{c + \sqrt{\Delta}})$ amortized recourse in the incremental model, and this is tight up to tie-breaking. In contrast, in a fully dynamic forest, greedy can be forced to have $\Omega(\log_\Delta n)$ amortized recourse. To partially alleviate this limitation of greedy, we show an optimal non-greedy algorithm with $O(1)$ amortized recourse for \emph{rooted} fully dynamic forests and $c = \Delta - 2$. In the randomized setting, we give a natural distribution-maintaining algorithm that achieves $\Theta(\frac{1}{\Delta})$ expected amortized recourse in the incremental model and $\Theta(\min \{ \frac{\Delta}{c}, \log_{\Delta} n \})$ expected recourse in the dynamic model. These randomized results are optimal for $c=0$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper pins down tight amortized recourse bounds for dynamic edge coloring on forests in incremental and fully dynamic models.

read the letter

The key point is that this paper pins down amortized recourse for dynamic edge coloring when the graph is always a forest. They separate incremental insertions from full updates with deletions, and they give both deterministic and randomized guarantees with some matching lower bounds. The new parts are the analysis showing that greedy gets O(1 over c plus square root of Delta) amortized recourse in the incremental model and that this is tight up to how ties are broken. They also prove that in the fully dynamic case, greedy can be made to recolor Omega(log base Delta of n) amortized. For a workaround, they have a non-greedy algorithm that keeps recourse at O(1) for rooted forests when c equals Delta minus 2. The randomized distribution-maintaining algorithm achieves Theta(1 over Delta) expected recourse for incremental and Theta of the minimum of Delta over c and log base Delta of n for fully dynamic, and these are optimal when c is zero. This is useful because it gives concrete numbers for a setting where general graphs are harder. The lower bounds help explain why certain approaches fail, and the distinction between models is clear. The work seems to build directly on prior dynamic coloring papers without circularity. A minor limitation is that the constant recourse result requires allowing almost twice as many colors as the maximum degree, which reduces its appeal if the goal is to use close to Delta colors. The results also only apply when the graph stays acyclic, so they do not extend immediately to denser graphs. The log n factor in the dynamic randomized bound might still be noticeable in practice for very large n. Overall this is a focused contribution that fits the dynamic algorithms area. A reader interested in recourse minimization or online coloring on trees and forests would get value from the specific bounds and the tightness claims. It has enough substance and formal grounding to warrant a serious referee, even though the scope is narrow. I would send this to peer review.

Referee Report

0 major / 3 minor

Summary. The manuscript studies the dynamic edge coloring problem restricted to forests of maximum degree Delta, where the goal is to maintain a proper edge coloring using at most Delta + c colors while minimizing amortized recourse (number of recolorings) under edge insertions and deletions. It analyzes the natural greedy algorithm, showing an O(1/(c + sqrt(Delta))) amortized recourse bound in the incremental model that is tight up to tie-breaking, an Omega(log_Delta n) lower bound in the fully dynamic model, and an O(1) amortized recourse non-greedy algorithm for rooted forests when c = Delta - 2. It also presents a randomized distribution-maintaining algorithm achieving Theta(1/Delta) expected amortized recourse in the incremental model and Theta(min(Delta/c, log_Delta n)) in the fully dynamic model, with the randomized bounds optimal for c = 0.

Significance. If the supporting analyses hold, the results deliver tight, model-specific characterizations of recourse for dynamic edge coloring on forests. The clean separation between incremental and fully dynamic settings, the matching upper/lower bounds (including optimality for c=0 in the randomized case), and the positive O(1) result for rooted forests with c = Delta - 2 constitute a substantive contribution. The forest restriction enables these precise statements, which may serve as a useful benchmark for the general-graph case.

minor comments (3)

The abstract is information-dense; consider splitting the randomized results into a separate sentence and explicitly cross-referencing the sections containing the matching lower bounds for the tightness claims.
Define 'amortized recourse' with a short formal definition or example in the introduction (before the abstract claims are repeated) to ensure readers unfamiliar with dynamic algorithms can follow the bounds without ambiguity.
Add a brief comparison paragraph in the introduction or related-work section to prior dynamic edge-coloring results on general graphs or other sparse graph classes, to better situate the forest restriction.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of our work. We appreciate the recommendation for minor revision. No specific major comments were provided in the report, so we have no points to address or revisions to make based on the feedback.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes algorithmic upper and lower bounds on amortized recourse for maintaining proper edge colorings with Delta + c colors on forests under incremental and fully dynamic updates. These results are proven via direct analysis of the greedy algorithm's recoloring behavior, a non-greedy algorithm for rooted forests, and a randomized distribution-maintaining procedure, with matching lower bounds shown by explicit constructions. No step reduces a claimed bound to a fitted parameter, self-definition, or load-bearing self-citation by construction; the proofs rely on standard combinatorial arguments about forests and color availability that are independent of the target bounds themselves.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The results rest on the assumption that the graph is always a forest and on standard definitions from graph theory and dynamic algorithms; no free parameters or invented entities are introduced.

axioms (2)

domain assumption The maintained graph is always a forest (no cycles).
Stated as the problem restriction in the abstract.
standard math Standard definitions of proper edge coloring, maximum degree Delta, and amortized recourse.
Used to state all bounds and models.

pith-pipeline@v0.9.0 · 5567 in / 1177 out tokens · 51882 ms · 2026-05-12T03:53:52.948859+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

54 extracted references · 54 canonical work pages

[1]

2026 , eprint=

Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring , author=. 2026 , eprint=

work page 2026
[2]

IEEE INFOCOM , year=

Hanauer, Kathrin and Henzinger, Monika and Schmid, Stefan and Trummer, Jonathan , title=. IEEE INFOCOM , year=

work page
[3]

Algorithmic Foundations of Dynamic Networks , pages =

El-Hayek, Antoine and Hanauer, Kathrin and Henzinger, Monika , title =. Algorithmic Foundations of Dynamic Networks , pages =. 2025 , volume =

work page 2025
[4]

SIAM Journal on Computing , volume =

Linial, Nathan , title =. SIAM Journal on Computing , volume =

work page
[5]

SODA , year =

Joakim Blikstad and Ola Svensson and Radu Vintan and David Wajc , title =. SODA , year =

work page
[6]

2001 , author =

Very fast parallel algorithms for approximate edge coloring , journal =. 2001 , author =

work page 2001
[7]

1961 , author =

Edge-Disjoint Spanning Trees of Finite Graphs , journal =. 1961 , author =

work page 1961
[8]

SODA , year =

Peter Davies , title =. SODA , year =

work page
[9]

SODA , pages =

Sayan Bhattacharya and Martín Costa and Shay Solomon and Tianyi Zhang , title =. SODA , pages =

work page
[10]

Advances in Mathematics , volume =

Measurable versions of. Advances in Mathematics , volume =. 2020 , author =

work page 2020
[11]

ICALP , year =

Chechik, Shiri and Chen, Hongyi and Zhang, Tianyi , title =. ICALP , year =

work page
[12]

ICALP , year =

Chechik, Shiri and Mukhtar, Doron and Zhang, Tianyi , title =. ICALP , year =

work page
[13]

ICALP , year =

Ghosh, Prantar and Stoeckl, Manuel , title =. ICALP , year =

work page
[14]

A linear-time algorithm for

Anton Bernshteyn and Abhishek Dhawan , year=. A linear-time algorithm for. 2407.04887 , archivePrefix=

work page arXiv
[15]

2013 , publisher =

Leonid Barenboim , Michael Elkin , title =. 2013 , publisher =

work page 2013
[16]

Cranston , title =

Daniel W. Cranston , title =. 2024 , publisher =

work page 2024
[17]

2012 , publisher =

Michael Stiebitz , title =. 2012 , publisher =

work page 2012
[18]

STOC , year =

Bhattacharya, Sayan and Henzinger, Monika and Nanongkai, Danupon and Tsourakakis, Charalampos , title =. STOC , year =

work page
[19]

Journal of Combinatorial Theory, Series B , volume =

Planar Graphs of Maximum Degree Seven are Class. Journal of Combinatorial Theory, Series B , volume =. 2001 , author =

work page 2001
[20]

Theoretical Computer Science , volume =

An efficient algorithm for edge coloring planar graphs with. Theoretical Computer Science , volume =. 1990 , author =

work page 1990
[21]

1990 , author =

Improved edge-coloring algorithms for planar graphs , journal =. 1990 , author =

work page 1990
[22]

1989 , author =

Fast algorithms for edge-coloring planar graphs , journal =. 1989 , author =

work page 1989
[23]

2008 , author =

New Linear-Time Algorithms for Edge-Coloring Planar Graphs , journal =. 2008 , author =

work page 2008
[24]

2011 , author =

On edge colorings of 1 -planar graphs , journal =. 2011 , author =

work page 2011
[25]

Christiansen, Aleksander B. G. and Rotenberg, Eva and Vlieghe, Juliette , title =. SWAT , year =

work page
[26]

Arboricity-Dependent Algorithms for Edge Coloring , booktitle =

Bhattacharya, Sayan and Costa, Mart. Arboricity-Dependent Algorithms for Edge Coloring , booktitle =. 2024 , pages =

work page 2024
[27]

A fast distributed algorithm for (

Anton Bernshteyn , journal =. A fast distributed algorithm for (

work page
[28]

SODA , year =

Dynamic Edge Coloring with Improved Approximation , author =. SODA , year =

work page
[29]

SODA , pages =

Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time , author=. SODA , pages =

work page
[30]

The Power of Multi-step

Christiansen, Aleksander Bj. The Power of Multi-step. STOC , year =

work page
[31]

1965 , journal =

The chromatic class of a multigraph , author=. 1965 , journal =

work page 1965
[32]

1965 , journal =

Critical graphs with a given chromatic class , author=. 1965 , journal =

work page 1965
[33]

1964 , journal =

On an estimate of the chromatic class of a p-graph , author=. 1964 , journal =

work page 1964
[34]

, title =

Su, Hsin-Hao and Vu, Hoa T. , title =. 2019 , pages =

work page 2019
[35]

SODA , year =

Sayan Bhattacharya and Fabrizio Grandoni and David Wajc , title =. SODA , year =

work page
[36]

SODA , year=

Yi-Jun Chang and Qizheng He and Wenzheng Li and Seth Pettie and Jara Uitto , title =. SODA , year=

work page
[37]

2024 , booktitle =

Sadeh, Yaniv and Kaplan, Haim , title =. 2024 , booktitle =

work page 2024
[38]

and Solomon, Shay , title =

Bhattacharya, Sayan and Grandoni, Fabrizio and Kulkarni, Janardhan and Liu, Quanquan C. and Solomon, Shay , title =. 2022 , volume =

work page 2022
[39]

ACM Trans

Solomon, Shay and Wein, Nicole , title =. ACM Trans. Algorithms , pages =. 2020 , volume =

work page 2020
[40]

SODA , pages=

Dynamic algorithms for graph coloring , author=. SODA , pages=

work page
[41]

Kashyop, Manas Jyoti and Narayanaswamy, N. S. and Nasre, Meghana and Potluri, Sai Mohith , title =. Algorithmica , year =

work page
[42]

Fully Dynamic Graph Algorithms Inspired by Distributed Computing: Deterministic Maximal Matching and Edge Coloring in Sublinear Update-Time , author =. ACM J. Exp. Algorithmics , pages =. 2019 , volume =

work page 2019
[43]

Algorithmica , year =

Azar, Yossi and Machluf, Chay and Patt-Shamir, Boaz and Touitou, Noam , title =. Algorithmica , year =

work page
[44]

ACM Trans

Monika Henzinger and Pan Peng , title =. ACM Trans. Algorithms , year =

work page
[45]

Dynamic Graph Coloring , year =

Barba, Luis and Cardinal, Jean and Korman, Matias and Langerman, Stefan and Renssen, Andr\'. Dynamic Graph Coloring , year =. Algorithmica , volume =

work page
[46]

2020 , eprint=

Explicit and Implicit Dynamic Coloring of Graphs with Bounded Arboricity , author=. 2020 , eprint=

work page 2020
[47]

Christiansen, Aleksander B. G. and Rotenberg, Eva , title =. ICALP , pages =

work page
[48]

Vizing's Theorem in Near-Linear Time , booktitle =

Assadi, Sepehr and Behnezhad, Soheil and Bhattacharya, Sayan and Costa, Mart\'. Vizing's Theorem in Near-Linear Time , booktitle =. 2025 , pages =

work page 2025
[49]

SODA , year =

Sepehr Assadi , title =. SODA , year =

work page
[50]

2024 , booktitle =

Online Edge Coloring Is (Nearly) as Easy as Offline , author =. 2024 , booktitle =

work page 2024
[51]

STOC , year =

Joakim Blikstad and Ola Svensson and Radu Vintan and David Wajc , title =. STOC , year =

work page
[52]

STOC , pages=

Dynamic sampling from graphical models , author=. STOC , pages=

work page
[53]

1992 , author =

The greedy algorithm is optimal for on-line edge coloring , journal =. 1992 , author =

work page 1992
[54]

Mathematische Annalen , volume=

K. Mathematische Annalen , volume=. 1916 , publisher=

work page 1916