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

Anton Bernshteyn (Carnegie Mellon University)

29-Jun-2020, 13:00-14:00 (4 years ago)

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).

Organizers: Jan Hladky*, Diana Piguet, Jan Volec*, Liana Yepremyan
*contact for this listing

Export talk to