Back to Search
Start Over
A Characterization of $(4,2)$-Choosable Graphs
- Source :
- Journal of Graph Theory. Vol. 92(4), December 2019, pp. 460-487
- Publication Year :
- 2017
-
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 $\varphi$ such that $\varphi(v)\in L(v)$ and $|\varphi(v)|=b$ for all $v\in V(G)$, and whenever vertices $x$ and $y$ are adjacent $\varphi(x)\cap \varphi(y)=\emptyset$. Meng, Puleo, and Zhu conjectured a characterization of (4,2)-choosable graphs. We prove their conjecture.<br />Comment: 20 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
- Subjects :
- Mathematics - Combinatorics
05C15
Subjects
Details
- Database :
- arXiv
- Journal :
- Journal of Graph Theory. Vol. 92(4), December 2019, pp. 460-487
- Publication Type :
- Report
- Accession number :
- edsarx.1708.05488
- Document Type :
- Working Paper