Speaker: Zimu Xiang (UIUC)
Title: Equitable list coloring of sparse graphs.
Abstract: For a list assignment $L$ of $k$ colors to each vertex of an $n$-vertex graph $G$, an equitable $L$-coloring of $G$ is a proper coloring of vertices of $G$ from their lists such that no color is used more than $\lceil n/k\rceil$ times. Call a graph equitably $k$-choosable if it has an equitable $L$-coloring for every $k$-list assignment $L$. A graph $G$ is $(a,b)$-sparse if for every $A\subseteq V(G)$, the number of edges in the subgraph $G[A]$ of $G$ induced by $A$ is at most $a|A|+b$.
We determine the sharp bounds in terms of $(a,b)$ that guarantee a graph with minimum degree at least $2$ to be equitably $k$-choosable for $k=3,4,5$. One of the tools in the proof is the new notion of strongly equitable (SE) list coloring. This notion is both stronger and more natural than equitable list coloring; and our upper bounds are for SE list coloring.
This is joint work with Hal Kierstead and Alexandr Kostochka.