On a Conjecture About $(k,t)$-Choosability

Abstract

A $(k,t)$-list assignment $L$ of a graph $G$ is a list of $k$ colors available at each vertex $v$ in $G$ such that $|\bigcup _{v\in V(G)}L(v)|=t$. A proper coloring $c$ such that $c(v)\in L(v)$ for each $v\in V(G)$ is said to be an $L$-coloring. We say that a graph $G$ is $L$-colorable if $G$ has an $L$-coloring. A graph $G$ is $(k,t)$-choosable if $G$ is $L$-colorable for every $(k,t)$-list assignment $L$.
Let $G$ be a graph with $n$ vertices and $G$ does not contain $C_5$ or $K_{k-2}$ and $K_{k+1}$. We prove that $G$ is $(k,kn–k^2–2k)$-choosable for $k\ge 3$.$G$ is not $(k,kn–k^2–2k)$-choosable for $k=2$.This result solves a conjecture posed by Chareonpanitseri, Punnim, and Uiyyasathian [W. Chareonpan-itseri, N. Punnim, C. Uiyyasathian, On $(k,t)$-choosability of Graphs: Ars Combinatoria., $99,(2011)321-333]$.