A fast distributed algorithm for $(\Delta + 1)$-edge-coloring

Abstract: A celebrated theorem of Vizing says that every graph $G$ of maximum degree $\Delta$ is $(\Delta+1)$-edge-colorable. In this talk I will describe a deterministic distributed algorithm in the LOCAL model that finds a $(\Delta+1)$-edge-coloring in the number of rounds that is polynomial in $\Delta$ and $\log n$, where $n = |V(G)|$. This is the first distributed algorithm for $(\Delta + 1)$-edge-coloring with running time better than $O(\mathrm{diameter}(G))$.

combinatoricsprobability

Audience: researchers in the topic

Extremal and probabilistic combinatorics webinar

Series comments: We've added a password: concatenate the 6 first prime numbers (hence obtaining an 8-digit password).