Proportional 2-Choosability with a Bounded Palette

Proportional choosability is a list coloring analogue of equitable coloring. Specifically, a $k$-assignment $L$ for a graph $G$ specifies a list $L(v)$ of $k$ available colors to each $v\in V(G)$. An $L$-coloring assigns a color to each vertex $v$ from its list $L(v)$. A proportional $L$-coloring of $G$ is a proper $L$-coloring in which each color $c\in {\bigcup }_{v\in V(G)}L(v)$ is used $\lfloor \eta (c)\mathrm{/}k\rfloor$ or $\lceil \eta (c)\mathrm{/}k\rceil$ times where $\eta (c)=\mid \{v\in V(G):c\in L(v)\}\mid$. A graph $G$ is proportionally $k$-choosable if a proportional $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. Motivated by earlier work, we initiate the study of proportional choosability with a bounded palette by studying proportional 2-choosability with a bounded palette. In particular, when $\mathrm{\ell }\ge 2$, a graph $G$ is said to be proportionally $(2, \ell)$-choosableifaproportional$L$-coloringof$G$existswhenever$L$isa$2$-assignmentfor$G$satisfying$|\bigcup_{v \in V(G)} L(v)| \leq \ell$. We observe that a graph is proportionally $(2,2)$-choosable if and only if it is equitably 2-colorable. As $\mathrm{\ell }$ gets larger, the set of proportionally $(2, \ell)$-choosablegraphsgetssmaller\mathrm{.}Weshowthatwhenever$\ell \geq 5$ a graph is proportionally $(2,\mathrm{\ell })$-choosable if and only if it is proportionally 2-choosable. We also completely characterize the connected proportionally $(2,\mathrm{\ell })$-choosable graphs when $\mathrm{\ell }=3,4$.