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 \(\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

Request Zoom Link