Discrete Applied Math Seminar by Michael Pelsmajer: Flexible List Coloring

Speaker:

Michael Pelsmajer, associate professor of applied mathematics, Illinois Institute of Technology

Title: Flexible List Coloring

Abstract: Graph coloring is a fundamental concept in discrete mathematics, with countless applications of different coloring variants. A {\it proper coloring} of a graph $G$ assigns a color to each vertex such that the endpoints of each edge have distinct colors. One well-known variant is {\it list coloring}, in which each vertex $v$ has a given list $L(v)$ of size $k$ and the color assigned to $v$ must be chosen from $L(v)$. We study a version of list coloring where $r$ of the vertices $v$ have a preferred color $f(v)\in L(v)$. We aim to color so that at least $ϵr$ vertices get their preferred color, for some $ϵ>0$.

We say that an graph $G$ is {\it $(k,ϵ)$-flexible} if for any lists $L(v)$ of size $k$ for all vertices $v$ with a preferred color $f(v)\in L(v)$ for any $r$ of the vertices $v$, there is always a proper coloring from those lists for which at least $ϵr$ vertices $v$ gets the color $f(v)$.

This topic was introduced in 2019 by Dvo\v{r}\'{a}k, Norin, and Postle, and several manuscripts have already appeared since then. We improve earlier results, most often by getting more vertices their preferred color (larger $ϵ$. We explore connections with the Hall Ratio of a graph, list packing, and the Alon-Tarsi Theorem, and pose several questions. Everything will be explained during the talk; no particular background knowledge will be needed.

This is joint work with Rogers Matthew (IIT Hydrabad), Jeff Mudrock (U. South Alabama), and Hemanshu Kaul.

Discrete Applied Math Seminar

Request Zoom Link