On $(2,t)$-Choosability of Triangle-Free Graphs

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$.

Récupéré en direct depuis OpenAlex et désinversé. Les résumés ne sont pas conservés dans cette base de données : les index inversés représentent 8,6 Go des 9,3 Go de texte de la base, et le serveur dispose de 13 Go libres.