On non 3-choosable bipartite graphs

Abstract

In 2003, Fitzpatrick and MacGillivray proved that every complete bipartite graph with fourteen vertices except K7,7 is 3-choosable and there is the unique 3-list assignment L up to renaming the colors such that K 7,7 is not L-colorable. We present our strategies which can be applied to obtain another proof of their result. These strategies are invented to claim a stronger result that every complete bipartite graph with fifteen vertices except K7,8 is 3-choosable. We also show all 3-list assignments L such that K7,8 is not L-colorable. © 2013 Springer-Verlag.