Key points are not available for this paper at this time.
Given a dynamic graph G with n vertices and m edges subject to insertion an deletions of edges, we show how to maintain a (1+) -edge-colouring of G without the use of randomisation. More specifically, we show a deterministic dynamic algorithm with an amortised update time of 2^O ^{-₁ (n) } using (1+) colours. If ^-1 2^O (^{0. 49 n) }, then our update time is sub-polynomial in n. While there exists randomised algorithms maintaining colourings with the same number of colours Christiansen STOC'23, Duan, He, Zhang SODA'19, Bhattacarya, Costa, Panski, Solomon SODA'24 in polylogarithmic and even constant update time, this is the first deterministic algorithm to go below the greedy threshold of 2-1 colours for all input graphs. On the way to our main result, we show how to dynamically maintain a shallow hierarchy of degree-splitters with both recourse and update time in n^o (1). We believe that this algorithm might be of independent interest.
Aleksander B. G. Christiansen (Tue,) studied this question.