A Characterization of $(4,2)$-Choosable Graphs

Abstract

A graph $G$ is \emph{$(a,b)$-choosable} if given any list assignment $L$ with $|L(v)|=a$ for each $v\in V(G)$ there exists a function $\phi$ such that $\phi (v)\in L(v)$ and $|\phi (v)|=b$ for all $v\in V(G)$, and whenever vertices $x$ and $y$ are adjacent $\phi (x)\cap \phi (y)=\varnothing$. Meng, Puleo, and Zhu conjectured a characterization of (4,2)-choosable graphs. We prove their conjecture.

arXiv comment20 pages, 20 figures; version 3 incorporates reviewer feedback: completely rewrote Section 5 to correct an error, omitted many tedious details of showing that certain graphs are not (4,2)-choosable, removed open question and conjecture; to appear in J. Graph Theory