On Non 3-Choosable Bipartite Graphs

摘要

In 2003, Fitzpatrick and MacGillivray proved that every complete bipartite graph with fourteen vertices except K_(7,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 K_(7,8) is 3-choosable. We also show all 3-list assignments L such that K_(7,8) is not L-colorable.