Abstract

A $(k,t)$-list assignment $L$ of a graph $G$ is a mapping which assigns a set of size $k$ to each vertex $v$ of $G$ and $|\bigcup_{v\in V(G)}L(v)|=t$. A graph $G$ is $(k,t)$-choosable if $G$ has a proper coloring $f$ such that $f(v)\in L(v)$ for each $(k,t)$-list assignment $L$.

In 2011, Charoenpanitseri, Punnim and Uiyyasathian proved that every $n$-vertex graph is $(2,t)$-choosable for $t\geq 2n-3$ and every $n$-vertex graph containing a triangle is not $(2,t)$-choosability for $t\leq 2n-4$. Then a complete result on $(2,t)$-choosability of an $n$-vertex graph containing a triangle is revealed. Moreover, they showed that an $n$-vertex triangle-free graph is $(2,t)$-choosable for $t\geq 2n-6$.

In this paper, we first prove that an $n$-vertex graph containing $K_{3,3}-e$ is not $(2,t)$-choosable for $t\leq 2n-7$. Then we deeply investigates $(2,t)$-choosablity of an $n$-vertex graph containing neither a triangle nor $K_{3,3}-e$.

This work is licensed under a Creative Commons Attribution 4.0 License.