PIMS- SFU Discrete Math Seminar:Peter Bradshaw

For a given $\epsilon > 0$, we say that a graph $G$ is $\epsilon$-flexibly $k$-choosable if the following holds: for any assignment $L$ of lists of size $k$ on $V(G)$, if a preferred color is requested at any set $R$ of vertices, then at least $\epsilon |R|$ of these requests are satisfied by some $L$-coloring. We characterize the graphs of maximum degree $\Delta$ that are $\epsilon$-flexibly $\Delta$-choosable for some $\epsilon = \epsilon(\Delta) > 0$, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. In particular, we show that for any $\Delta\geq 3$, any graph of maximum degree $\Delta$ that is not isomorphic to $K_{\Delta+1}$ is $\frac{1}{2 \Delta^3}$-flexibly $\Delta$-choosable.

This is joint work with Ladislav Stacho and Tomáš Masařík.