Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring

Yaniv Sadeh, Haim Kaplan

TL;DR

This paper introduces the shift-tree, a novel data structure for maintaining proper edge colorings in dynamic graphs. By exploring a tree of potential color shifts rather than traditional single paths or "fans," the authors achieve the first deterministic tight recourse bounds for large color palettes and significantly reduce the extra colors needed for graphs with low arboricity.

What Problem Does This Paper Address?

Edge coloring is a classic problem: assign colors to edges such that no two edges sharing a vertex have the same color. Vizing’s Theorem tells us that $\Delta + 1$ colors (where $\Delta$ is the maximum degree) are always enough.

In a dynamic graph, edges are constantly being inserted or deleted. To keep the coloring "proper," we often have to change the colors of existing edges. This is called recourse. High recourse is bad—it means more computation and potentially disruptive updates in real-world systems (like re-routing network traffic).

The challenge is a trade-off: if you have a huge palette of extra colors ($C$), recourse is easy. If you have very few (close to $\Delta$), recourse becomes theoretically difficult. This paper specifically targets the "recoloring" complexity in the dynamic setting, aiming for the smallest possible number of recolors per update.

Methods

The authors depart from the standard "Vizing chains" (alternating bicolored paths) and "fans" used for decades. Instead, they propose:

  • The Shift-Tree: When an edge $(u, v)$ is inserted and no free color is available, the algorithm builds a tree rooted at $v$. Each node in the tree represents a vertex, and an edge in the tree represents a potential "color shift"—moving a color from one edge to another to vacate a spot for the new edge.
  • BFS Exploration: The shift-tree is explored in a Breadth-First Search (BFS) manner. This allows the algorithm to track multiple possible recoloring paths simultaneously.
  • Good/Bad Neighbors: To decide when a shift is "safe" and won't cause a conflict elsewhere, the authors define "good" neighbors based on color availability. This helps prune the search space and ensures the algorithm terminates with a valid coloring.
  • Relaxed Path Constraints: Unlike many previous algorithms that require paths to be non-self-intersecting, this method allows the final edge in a shift to be a "revisited" edge, providing more flexibility in finding a solution.

Datasets

As a theoretical computer science paper, no empirical datasets were used. The results are established through rigorous mathematical proofs and worst-case graph constructions used to prove lower bounds (the limits of what any algorithm can achieve).

Key Insights and Ideas

  • Tree vs. Path: The core "aha moment" is that viewing possible recolorings as a tree rather than a single path allows for much tighter analysis. If a vertex appears multiple times in the tree, it means there are many different ways to reach it, increasing the odds that one of those ways is "useful."
  • Settling Large Palettes: For large palettes ($C \ge 0.62\Delta$), the authors prove a tight recourse bound of $O\left( \frac{\log n}{\log \frac{\Delta+C}{\Delta-C}}\right)$. This settles the theoretical complexity for this regime, matching known lower bounds.
  • Arboricity Efficiency: For graphs with low arboricity $\alpha$ (a measure of how "forest-like" a graph is), they show that you only need roughly $2\alpha$ extra colors to get logarithmic recourse, whereas previous state-of-the-art required $4\alpha$.
  • The "Shift-Based" Gap: The authors prove that algorithms that only shift colors along paths (like theirs and most others in literature) are inherently limited. They show a "separation" where more general methods (like the "Nibbling Method") could theoretically achieve even lower recourse.

Key Results

  • Tight Deterministic Bounds: Achieved the first deterministic tight recourse for $C \ge 0.62\Delta$.
  • Improved Arboricity Coloring: Reduced the required extra colors for $O(\log n)$ recourse from $(4+\epsilon)\alpha$ to $(2+\epsilon)\alpha - 1$.
  • Adaptivity: Their arboricity algorithm is $\Delta$-adaptive, meaning it doesn't need to know the global maximum degree $\Delta$ in advance; it adjusts based on the local degree at the time of the update.
  • Lower Bounds: Provided a generalized lower bound for graphs with arboricity, showing their results are nearly optimal.

Limitations and Future Work

  • Palette Size: The shift-tree technique currently requires a relatively large number of extra colors ($C \approx 0.6\Delta$) to guarantee the tightest bounds. A major open question is whether this tree-based approach can be generalized to work with very small palettes (e.g., $C=1$).
  • Running Time: While the recourse (number of recolors) is low, the time to find those recolors is polynomial ($O(m + \Delta^2)$). Future work could focus on bringing this down to poly-logarithmic update times.
  • Amortization: The current results focus on worst-case recourse. Exploring whether the shift-tree can provide better average (amortized) recourse is another promising direction.

Summary updated

Abstract

We study the maintenance of a $(Δ+C)$-edge-coloring ($C\ge 1$) in a fully dynamic graph $G$ with maximum degree $Δ$. We focus on minimizing \emph{recourse} which equals the number of recolored edges per edge updates. We present a new technique based on an object which we call a \emph{shift-tree}. This object tracks multiple possible recolorings of $G$ and enables us to maintain a proper coloring with small recourse in polynomial time. We shift colors over a path of edges, but unlike many other algorithms, we do not use \emph{fans} and \emph{alternating bicolored paths}. We combine the shift-tree with additional techniques to obtain an algorithm with a \emph{tight} recourse of $O\big( \frac{\log n}{\log \frac{Δ+C}{Δ-C}}\big)$ for all $C \ge 0.62Δ$ where $Δ-C = O(n^{1-δ})$. Our algorithm is the first deterministic algorithm to establish tight bounds for large palettes, and the first to do so when $Δ-C=o(Δ)$. This result settles the theoretical complexity of the recourse for large palettes. Furthermore, we believe that viewing the possible shifts as a tree can lead to similar tree-based techniques that extend to lower values of $C$, and to improved update times. A second application is to graphs with low arboricity $α$. Previous works [BCPS24, CRV24] achieve $O(ε^{-1}\log n)$ recourse per update with $C\ge (4+ε)α$, and we improve by achieving the same recourse while only requiring $C \ge (2+ε)α- 1$. This result is $Δ$-adaptive, i.e., it uses $Δ_t+C$ colors where $Δ_t$ is the current maximum degree. Trying to understand the limitations of our technique, and shift-based algorithms in general, we show a separation between the recourse achievable by algorithms that only shift colors along a path, and more general algorithms such as ones using the Nibbling Method [BGW21, BCPS24].
BibTeX
@misc{sadeh2026beyond,
  author = {Yaniv Sadeh and Haim Kaplan},
  title = {{Beyond Vizing Chains: Improved Recourse in Dynamic Edge Coloring}},
  year = {2026},
  eprint = {2602.09497},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.09497},
}
Figure