Deterministic Dynamic Edge Colouring

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 + ε)∆-edge-colouring of G without the use of randomisation. More specifically, we show a deterministic dynamic algorithm with an amortised update time of

While there exists randomised algorithms maintaining colourings with the same number of colours [Bhattacharya, Costa, Panski, Solomon SODA'24, Christiansen STOC'23, Duan, He, Zhang SODA'19] in polylogarithmic and even constant update time, this is the first efficient 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.