Back to Search Start Over

On Non 3-Choosable Bipartite Graphs

Authors :
Narong Punnim
Wongsakorn Charoenpanitseri
Chariya Uiyyasathian
Source :
Computational Geometry and Graphs ISBN: 9783642452802, TJJCCGG
Publication Year :
2013
Publisher :
Springer Berlin Heidelberg, 2013.

Abstract

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.

Details

ISBN :
978-3-642-45280-2
ISBNs :
9783642452802
Database :
OpenAIRE
Journal :
Computational Geometry and Graphs ISBN: 9783642452802, TJJCCGG
Accession number :
edsair.doi...........030f78c1947001ce237b60758382a99e
Full Text :
https://doi.org/10.1007/978-3-642-45281-9_4