Graph Theory and Combinatorics Seminar
- Event Type
- Ceremony/Service
- Sponsor
- Department of Mathematics
- Location
- Lincoln 1066
- Date
- Feb 18, 2025 8:30 am
- Speaker
- Abhishek Dhawan (UIUC)
- Contact
- Peter Bradshaw
- pb38@illinois.edu
- Views
- 38
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.