Discrete Applied Math Seminar by Peter Bradshaw: Flexible List Coloring and Maximum Average Degree

Speaker: 

Peter Bradshaw, University of Illinois Urbana-Champaign

Title: Flexible List Coloring and Maximum Average Degree

Abstract: 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.

This talk contains joint work with Richard Bi.

 

Discrete Applied Math Seminar

Request Zoom Link