Choice Number of Complete Multipartite Graphs with Part Size at Most Three

Abstract

We denote by $K(l\ast r)$ the complete $r$-partite graph with $l$ vertices in each part, and denote $K(l\ast v)+K(m\ast s)+K(n\ast t)+\cdots$ by $K(l\ast r,m\ast s,n\ast t,\dots )$. Kierstead showed that the choice number of $K(3\ast r)$ is exactly $\lceil \frac{4r-1}{3}\rceil$. In this paper, we shall determine the choice number of $K(3\ast r,1\ast t)$, and consider the choice number of $K(3\ast r,2\ast s,1\ast t)$.