# Discrete Applied Math Seminar by Michael Pelsmajer: Flexible List Coloring

-

## Locations

Online event

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 $$\epsilon r$$ vertices get their preferred color, for some $$\epsilon>0$$.

We say that an graph $$G$$ is {\it $$(k,\epsilon)$$-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 $$\epsilon 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 $$\epsilon$$. 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

## Event Contact Co-Director, M.S. in Computational Decision Science and Operations Research (CDSOR) Associate Professor of Applied Mathematics
312.567.3128