\((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 \leq t \leq 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 \geq 3\) is \((k, kn – k^2 – 2k)\)-choosable. For a non-2-choosable graph \(G\), we find the minimum \(t_1 \geq 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\).