Sparsity-Parameterised Dynamic Edge Colouring

Abstract

We study the edge-colouring problem, and give efficient algorithms where the number of colours is parameterised by the graph's arboricity, $\hat{I}\pm$. In a dynamic graph, subject to insertions and deletions, we give a deterministic algorithm that updates a proper $\hat{I}”+O(\hat{I}\pm )$ edge~colouring in $\mathrm{poly}(\log n)$ amortized time. Our algorithm is fully adaptive to the current value of the maximum degree and arboricity. In this fully-dynamic setting, the state-of-the-art edge-colouring algorithms are either a randomised algorithm using $(1+\epsilon )\hat{I}”$ colours in $\mathrm{poly}(\log n,\hat{I}{\mu }^{-1})$ time per update, or the naive greedy algorithm which is a deterministic $2\hat{I}”-1$ edge colouring with $\log (\hat{I}”)$ update time. Compared to the $(1+\epsilon )\hat{I}”$ algorithm, our algorithm is deterministic and asymptotically faster, and when $\hat{I}\pm$ is sufficiently small compared to $\hat{I}”$, it even uses fewer colours. In particular, ours is the first $\hat{I}”+O(1)$ edge-colouring algorithm for dynamic forests, and dynamic planar graphs, with polylogarithmic update time. Additionally, in the static setting, we show that we can find a proper edge colouring with $\hat{I}”+2\hat{I}\pm$ colours in $O(m\log n)$ time. Moreover, the colouring returned by our algorithm has the following local property: every edge $uv$ is coloured with a colour in $\{1,\max \{deg(u),deg(v)\}+2\hat{I}\pm \}$. The time bound matches that of the greedy algorithm that computes a $2\hat{I}”-1$ colouring of the graph's edges, and improves the number of colours when $\hat{I}\pm$ is sufficiently small compared to $\hat{I}”$.

Related version (June 2023): http://dx.doi.org/10.13140/RG.2.2.18471.52648