Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLLResearch Paper
Vizing's theorem gives every simple graph of maximum degree a proper edge colouring with colours. Maintaining such a colouring while edges are inserted and deleted is much harder: no dynamic algorithm for colours with subpolynomial update time is known, except for low-degree graphs. With slightly more colours, ,…