Title: Flexible list coloring and maximum average degree
Speaker: Peter Bradshaw (UIUC)
The flexible list coloring problem is a problem whose input is a graph G, a color list assignment L, and a set of coloring preferences at some vertex subset of G. The goal of the problem is to find an L-coloring of G that satisfies as many coloring preferences as possible. Dvorak, Norin, and Postle asked whether a constant proportion of preferences can be satisfied whenever G is d-degenerate graph and assigns lists of size (d+1).
In this talk, we answer a special case of this question. We show that if G has maximum average degree less than 3 and an assignment L of lists of size 3, then there exists c > 0 such that for any set of coloring preferences on G, some L-coloring of G satisfies a c proportion of these preferences. This generalizes a similar theorem of Dvorak, Masarik, Musilek, and Pangrac for planar graphs of girth six. Our main new tool is a reducible subgraph framework which generalizes a previous framework of these four authors. We also discuss progress toward similar results for graphs of larger maximum average degree.
