BIU Theory Seminar - Jan 10 - David Wajc (Technion) - online edge coloring
7 views
Skip to first unread message
Arnold Filtser
Jan 4, 2024, 4:28:10 AMJan 4
to BIU Theory Seminar, david...@gmail.com
Hi all,
Next week (Wed Jan 10) we will meet for our theory seminar.
New location: Building 503 room 226.
See you all there,
Arnold and Talya
Speaker: David Wajc (Technion)
Title: Online edge coloring
Abstract: Vizing's Theorem provides an algorithm that edge colors any graph of maximum degree Δ using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime. In contrast, they conjectured that for graphs of superlogarithmic-in-n maximum degree, much better can be done, and that even (1+o(1))Δ-colors suffice online. In this talk I will outline the history of this conjecture, and its recent resolution, together with extensions of a flavor resembling classic and recent results on *list* edge-coloring and "local" edge-coloring.
Title: Online edge coloring
Abstract: Vizing's Theorem provides an algorithm that edge colors any graph of maximum degree Δ using Δ+1 colors, which is necessary for some graphs, and at most one higher than necessary for any graph. In online settings, the trivial greedy algorithm requires 2Δ-1 colors, and Bar-Noy, Motwani and Naor in the early 90s showed that this is best possible, at least in the low-degree regime. In contrast, they conjectured that for graphs of superlogarithmic-in-n maximum degree, much better can be done, and that even (1+o(1))Δ-colors suffice online. In this talk I will outline the history of this conjecture, and its recent resolution, together with extensions of a flavor resembling classic and recent results on *list* edge-coloring and "local" edge-coloring.
Talk based in part on joint works with many wonderful and colorful collaborators, including Sayan Bhattacharya, Joakim Blikstad, Ilan R. Cohen, Fabrizio Grandoni, Seffi Naor, Binghui Peng, Amin Saberi, Aravind Srinivasan, Ola Svensson and Radu Vintan.
Arnold Filtser
Jan 10, 2024, 4:00:35 AMJan 10
to BIU Theory Seminar, david...@gmail.com
The seminar starts in one hour!
Reminder, our new location is Building 503 room 226.
Reply all
Reply to author
Forward
0 new messages