On choosability of some complete multipartite graphs and Ohba's conjecture (Q2463475)

A graph \(G\) with chromatic number \(k=\chi(G)\) is called chromatic-choosable if the vertices of \(G\) can always be colored from lists of size \(k\). Ohba conjectured that if \(G\) has at most \(2k+1\) vertices, then it is chromatic-choosable. It suffices to verify this conjecture for complete \(k\)-partite graphs on \(2k+1\) vertices, and those graphs are entirely determined by their ``large'' parts (parts on more than 2 vertices.) So far Ohba's conjecture has been verified in the cases when there is only one large part, or when there are two large parts, both of size 3. In this paper Ohba's conjecture is verified for the case when there are only two large parts, one of size 3 and the other of size 4 or 5.