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

Abstract

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