Improved Dynamic Colouring of Sparse Graphs

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 algorithms that uses O(minα log α, α log log log n) colours in the oblivious adversary model. Our deterministic algorithm has update-and query times polynomial in α and log n, and our randomised algorithm has amortised update-and query time that with high probability is polynomial in log n with no dependency on the arboricity. Thus, we improve the number of colours exponentially compared to the state-of-the art for implicit colouring, namely from O(2 α ) colours, and we approach the theoretical lower bound of Ω(α) for this arboricity-parameterised approach. Simultaneously, our randomised algorithm improves the update-and query time to run in time solely polynomial in log n with no dependency on α. Our algorithms are fully adaptive to the current value of the dynamic arboricity at query or update time.