##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics Seminar

## Anton Bernshteyn

#### Carnegie Mellon University

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

Hosts: Jacques Verstraete and Ruth Luo

### November 23, 2021

### 3:00 PM

### APM 6402 (Halkin Room)

****************************