Abstract
Vizing's theorem states that every graph with maximum degree Delta admits a proper (Delta+1) edge coloring. The state-of-the-art algorithms for finding such a coloring on n-vertex m-edge graphs take O(m\sqrt(n)) time and date back to the 80's.
In this talk, we present a very recent randomized algorithm for finding a Delta+O(log n) coloring in O(m*log(Delta)) time, namely, a near-linear time algorithm for a "near"-Vizing's theorem. This algorithm is inspired by several tools developed in the study of sublinear algorithms.
As a corollary of this result and Vizing's original approach, we also obtain an O(n^2 log(n)) expected time algorithm for the (Delta+1) edge coloring problem. This is nearly optimal for dense graphs and improves upon the longstanding O(n^{2.5}) bounds of prior work for Vizing's theorem in almost four decades.
Based on https://arxiv.org/abs/2405.13371
(see also https://arxiv.org/abs/2405.15449 for an independent and concurrent work that obtains an ~O(m*n^{1/3}) time randomized algorithm for Vizing's theorem)