Discrete Applied Math Seminar By Anton Bernshteyn: Weak Degeneracy of Graphs

Speaker:

Anton Bernshteyn, Georgia Institute of Technology

Title:

 Weak Degeneracy of Graphs

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).

 

The Discrete Applied Math seminar will be held most Fridays from 3:30 p.m. - 4:30 p.m. on Zoom during the Spring 2022 semester.

 

Discrete Applied Math seminar