TY - GEN
T1 - Sparsity-parametrised dynamic edge colouring
AU - Rotenberg, Eva
AU - Vlieghe, Juliette
AU - Christiansen, Aleksander Bjørn Grodt
PY - 2023/6/23
Y1 - 2023/6/23
N2 - We study the edge colouring problem on graphs of bounded arboricity, subject to insertions and deletions. We propose a max{deg(u), deg(v)} + O(α) edge colouring algorithm in poly(log n) time, with α the arboricity of the graph, which improves the state of the art for graphs of arboricity α = o(∆).
AB - We study the edge colouring problem on graphs of bounded arboricity, subject to insertions and deletions. We propose a max{deg(u), deg(v)} + O(α) edge colouring algorithm in poly(log n) time, with α the arboricity of the graph, which improves the state of the art for graphs of arboricity α = o(∆).
UR - https://rgdoi.net/10.13140/RG.2.2.18471.52648
U2 - 10.13140/RG.2.2.18471.52648
DO - 10.13140/RG.2.2.18471.52648
M3 - Article in proceedings
SP - 1
EP - 19
BT - SWAT
PB - Technical University of Denmark
ER -