3 papers
cs.DS2023
Nibbling at Long Cycles: Dynamic (and Static) Edge Coloring in Optimal Time
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
We consider the problem of maintaining a -edge coloring in a dynamic graph with nodes and maximum degree at most . The state-of-the-art update time is $O_ε(\text…
cs.DS2023
Arboricity-Dependent Algorithms for Edge Coloring
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
The problem of edge coloring has been extensively studied over the years. Recently, this problem has received significant attention in the dynamic setting, where we are given a dyn…
cs.DS2023
Density-Sensitive Algorithms for -Edge Coloring
Sayan Bhattacharya, Martín Costa, Nadav Panski +1
Vizing's theorem asserts the existence of a -edge coloring for any graph , where denotes the maximum degree of . Several polynomial time -edge colorin…