Improved Dynamic Colouring of Sparse Graphs
Aleksander B. G. Christiansen, Krzysztof Nowicki, Eva Rotenberg · 2023
Given a dynamic graph subject to edge insertions and deletions, we show how to update an implicit representation of a proper vertex colouring, such that colours of vertices are computable upon query time. We give a deterministic algorithm that uses O(α 2) colours for a dynamic graph of arboricity α, and a randomised algorithm that uses O(min{α logα, α logloglogn}) colours in the oblivious adversary model. Our deterministic algorithm has update- and query times polynomial in α and logn, and our randomised algorithm has amortised update- and query time that with high probability is polynomial in logn with no dependency on the arboricity.