$(2,t)$-Choosable Graphs

Abstract

A $(k,t)$-list assignment $L$ of a graph $G$ assigns a list of $k$ colors available at each vertex $v$ in $G$ and $|\bigcup _{v\in V(G)}L(v)|=t$. An $L$-coloring is a proper coloring $c$ such that $c(v)\in L(v)$ for each $v\in V(G)$. A graph $G$ is $(k,t)$-choosable if $G$ has an $L$-coloring for every $(k,t)$-list assignment $L$.
Erdős, Rubin, and Taylor proved that a graph is $(2,t)$-choosable for any $t>2$ if and only if a graph does not contain some certain subgraphs. Chareonpanitseri, Punnim, and Uiyyasathian proved that an $n$-vertex graph is $(2,t)$-choosable for $2n–6\le t\le 2n–4$ if and only if it is triangle-free. Furthermore, they proved that a triangle-free graph with $n$ vertices is $(2,2n–7)$-choosable if and only if it does not contain $K_{3,3}–e$ where $e$ is an edge. Nakprasit and Ruksasakchai proved that an $n$-vertex graph $G$ that does not contain $C_5\vee K_{n-2}$ and $K_{4,4}$ for $k\ge 3$ is $(k,kn–k^2–2k)$-choosable. For a non-2-choosable graph $G$, we find the minimum $t_1\ge 2$ and the maximum $t_2$ such that the graph $G$ is not $(2,t_i)$-choosable for $i=1,2$ in terms of certain subgraphs. The results can be applied to characterize $(2,t)$-choosable graphs for any $t$.