Please note: This seminar will take place in person DC 1304 and online.

Annie Zeng, Undergraduate Student
Siebel School of Computing and Data Science, University of Illinois Urbana-Champaign (UIUC)

The list coloring problem on graphs is where each vertex has a list of colors, and the graph must be properly colored with each vertex only using colors from its list. The paintability game is the on-line version of list-coloring, where for each color an adversary reveals which vertices contain that color in their list, and one needs to make an on-the-spot decision about which vertices to use the color on. Due to the challenging nature of this on-line problem, many graph paintability bounds are significantly weaker than the corresponding off-line bounds for graph coloring. In 2023, Bernshtyen and Lee introduced a graph parameter known as weak degeneracy, based off of standard graph degeneracy, which serves as an upper bound for the list sizes needed in graph paintability and the related parameter of DP-Paintability. In this talk, we will demonstrate how a modified version of weak degeneracy can be utilized on a bipartite graph to obtain an upper bound for paintability and DP-Paintability. This talk is based on joint work with Peter Bradshaw

This seminar will take place in person (DC 1304) and on Zoom.