Publication: On non 3-choosable bipartite graphs
2
0
Issued Date
2013
Resource Type
File Type
application/pdf
ISSN
3029743
Other identifier(s)
2-s2.0-84893108183
Rights Holder(s)
Scopus
Bibliographic Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 8296 LNCS, (2013), p.42-56
Suggested Citation
Charoenpanitseri W., Punnim N., Uiyyasathian C. On non 3-choosable bipartite graphs. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 8296 LNCS, (2013), p.42-56. doi:10.1007/978-3-642-45281-9_4 Retrieved from: https://hdl.handle.net/20.500.14740/6495
Author(s)
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.