On the choice number of complete multipartite graphs with part size four

Abstract

Let $\mathrm{ch}(G)$ denote the choice number of a graph $G$, and let $K_{s\ast k}$ be the complete $k$-partite graph with $s$ vertices in each part. Erdős, Rubin, and Taylor showed that $\mathrm{ch}(K_{2\ast k})=k$, and suggested the problem of determining the choice number of $K_{s\ast k}.$ The first author established $\mathrm{ch}(K_{3\ast k})=\lceil \frac{4k-1}{3}\rceil$. Here we prove $\mathrm{ch}(K_{4\ast k})=\lceil \frac{3k-1}{2}\rceil$.