PIMS- SFU Discrete Math Seminar:Peter Bradshaw

  • Date: 01/20/2021
  • Time: 10:30
Peter Bradshaw, SFU



Flexible list colorings in graphs of bounded degree


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.

Other Information: 

Zoom details: Please contact the organizer for login details.