Deterministic Dynamic Edge Colouring
Abstract
Given a dynamic graph \(G\) with \(n\) vertices and \(m\) edges subject to insertions and deletions of edges, we show how to maintain a \((1+\varepsilon)\Delta\)-edge-colouring of \(G\) without the use of randomisation. More specifically, we show a deterministic dynamic algorithm with an amortised update time of \(2^{\tilde{O}_{\log \varepsilon^{-1}}(\sqrt{\log n})}\) using \((1+\varepsilon)\Delta\) colours. If \(\varepsilon^{-1} \in 2^{O(\log^{0.49} n)}\), then our update time is sub-polynomial in \(n\).
Fields of Study & Subjects
Limits and Structures in Graph Theory
Advanced Graph Theory Research
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 1047–1096
- Publication date
- 1 January 2026
- Language
- EN