Graphs of maximum average degree less than $\frac{11}{3}$ are flexibly $4$-choosable

Abstract

We consider the flexible list coloring problem, in which we have a graph $G$, a color list assignment $L:V(G)\to 2^{\mathbb{N}}$, and a set $U\subseteq V(G)$ of vertices such that each $u\in U$ has a preferred color $p(u)\in L(u)$. Given a constant $\epsilon >0$, the problem asks for an $L$-coloring of $G$ in which at least $\epsilon |U|$ vertices in $U$ receive their preferred color. We use a method of reducible subgraphs to approach this problem. We develop a vertex-partitioning tool that, when used with a new reducible subgraph framework, allows us to define large reducible subgraphs. Using this new tool, we show that if $G$ has maximum average degree less than $\frac{11}{3}$, a list $L(v)$ of size $4$ at each $v\in V(G)$, and a set $U\subseteq V(G)$ of vertices with preferred colors, then there exists an $L$-coloring of $G$ for which at least $2^{-145}|U|$ vertices of $U$ receive their preferred color.

34 pages + appendix