Proportional choosability: A new list analogue of equitable coloring

In 2003, Kostochka, Pelsmajer, and West introduced a list analogue of equitable coloring called equitable choosability. In this paper, we motivate and define a new list analogue of equitable coloring called proportional choosability. A $k$-assignment $L$ for a graph $G$ specifies a list $L\left(v\right)$ of $k$ available colors for each vertex $v$ of $G$. An $L$-coloring assigns a color to each vertex $v$ from its list $L\left(v\right)$. For each color $c$, let $\eta \left(c\right)$ be the number of vertices $v$ whose list $L\left(v\right)$ contains $c$. A proportional$L$-coloring of $G$ is a proper $L$-coloring in which each color $c\in {?}_{v\in V\left(G\right)}L\left(v\right)$ is used $?\eta \left(c\right)∕k?$ or $?\eta \left(c\right)∕k?$ times. A graph $G$ is proportionally$k$-choosable if a proportional $L$-coloring of $G$ exists whenever $L$ is a $k$-assignment for $G$. We show that if a graph $G$ is proportionally $k$-choosable, then every subgraph of $G$ is also proportionally $k$-choosable and also $G$ is proportionally $(k+1)$-choosable, unlike equitable choosability for which analogous claims would be false. We also show that any graph $G$ is proportionally $k$-choosable whenever $k\ge \Delta \left(G\right)+?\left|V\left(G\right)\right|∕2?$, and we use matching theory to completely characterize the proportional choosability of stars and the disjoint union of cliques.