Speaker: Abhishek Dhawan (UIUC)
Title: A survey of near-Vizing edge-coloring.
Abstract: Vizing’s Theorem states that every graph of maximum degree \Delta admits a proper edge-coloring using at most \Delta + 1 colors. There has been a flurry of recent works on fast edge coloring algorithms. In this talk, I will discuss classical and more recent approaches toward near-Vizing edge-coloring algorithms, i.e., (1+\epsilon)\Delta-edge-coloring. The focus will be on the so-called augmenting subgraph approach. This talk is partially based on joint work with Anton Bernshteyn.