MATH Seminar

Title: Weak degeneracy of graphs
Seminar: Discrete Math
Speaker: Anton Bernshteyn of Georgia Tech
Contact: Liana Yepremyan, liana.yepremyan@EMORY.EDU
Date: 2022-03-16 at 4:00PM
Venue: MSC E406
Download Flyer
Abstract: Motivated by the study of greedy algorithms for graph coloring, we introduce a new graph parameter, which we call weak degeneracy. This notion formalizes a particularly simple way of "saving" colors while coloring a graph greedily. It turns out that many upper bounds on chromatic numbers follow from corresponding bounds on weak degeneracy. In this talk I will survey some of these bounds as well as state a number of open problems. This is joint work with Eugene Lee (Carnegie Mellon University).