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 等数据库收录! |
|