Department of Mathematics - Master Calendar

Speaker: Peter Bradshaw (UIUC)

Title. Weak degeneracy in r-chromatic graphs

Abstract. This talk considers the following weak degeneracy problem. We have a graph G, and every vertex v has a list of colors. However, we cannot distinguish between different colors; rather, all available colors are represented by identical tokens. Our task is to find a vertex ordering of G that guarantees a proper list-coloring by deleting vertices one at a time, according to the following rules. When we delete a vertex v, we must remove a token from each neighbor of v, with one exception. If some set W = {w_1, ..., w_k} of neighbors of v altogether has fewer tokens than v, then we can choose to "save" the set W, so that no vertex in W loses a token when v is deleted. The goal is to delete all vertices of G so that each vertex has at least one token remaining when it is deleted. This weak degeneracy problem has immediate applications in list coloring and correspondence coloring, as well as the online versions of these problems. (This problem is a slight variation of Bernshteyn and Lee's weak degeneracy problem and was called strict type-3 degeneracy by Zhou, Zhu, and Zhu.)

In this talk, we show an upper bound on the weak degeneracy of r-chromatic graphs in terms of their maximum degree. We also show that this upper bound is of optimal order. Using a similar idea, we also obtain a new upper bound on the Alon-Tarsi number of an r-chromatic graph in terms of its maximum degree.

This talk is based on joint work with Jinghan Zeng.