首页 | 本学科首页   官方微博 | 高级检索  
     检索      


On choosability of some complete multipartite graphs and Ohba's conjecture
Authors:Yufa Shen  Wenjie He  Yanning Wang
Institution:a Department of Mathematics and Physics, Hebei Normal University of Science and Technology, Qinhuangdao 066004, PR China
b Applied Mathematics Institute, Hebei University of Technology, Tianjin 300130, PR China
c School of Science, Yanshan University, Qinhuangdao 066004, PR China
Abstract:A graph G is said to be chromatic-choosable if ch(G)=χ(G). Ohba has conjectured that every graph G with 2χ(G)+1 or fewer vertices is chromatic-choosable. It is clear that Ohba's conjecture is true if and only if it is true for complete multipartite graphs. But for complete multipartite graphs, the graphs for which Ohba's conjecture has been verified are nothing more than K3*2,2*(k-3),1, K3,2*(k-1), and Ks+3,2*(k-s-1),1*s. These results have been obtained indirectly from the investigation about complete multipartite graphs by Gravier and Maffray and by Enomoto et al. In this paper we show that Ohba's conjecture is true for complete multipartite graphs K4,3,2*(k-4),1*2 and K5,3,2*(k-5),1*3. By the way, we give some discussions about a result of Enomoto et al.
Keywords:05C15
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号