Speaker: Peter Bradshaw (UIUC)
Title: A sharp threshold for flexible DP 3-coloring
Abstract: A request on a graph assigns a preferred color to a subset of the vertices. A graph G is ε-flexibly k-choosable if for every k-list assignment L and every request r on G, there is an L-coloring such that an \epsilon-fraction of the requests are satisfied. The notion of flexibility was introduced in 2019 by Dvořák, Norin, and Postle, who also proved important properties of flexible colorings and posed several natural problems. However, the weighted version of this problem is a special case of the much older problem of fractional hypergraph matchings, introduced by Lovász in 1975.
We consider the flexibility problem for DP-colorings of multigraphs. We prove that every loopless multigraph with maximum average degree less than 3 is 1/5-flexibly DP 3-colorable, except for an infinite family of multigraphs that we completely characterize. This maximum average degree bound is best possible, and our constant ε = 1/5 is best possible in the weighted setting. We also provide a family a graphs that gives a negative answer to a question by Dvořák, Norin, and Postle regarding flexibility for list coloring in the setting of DP-coloring.
This talk is based on joint work with Ilkyoo Choi and Alexandr Kostochka.