On choosability of some complete multipartite graphs and Ohba's conjecture
On choosability of some complete multipartite graphs and Ohba's conjecture
复制标题
DOI：
10.1016/j.disc.2007.03.059
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Yufa Shen;Wenjie He;Guoping Zheng;Yanning Wang;Lingmin Zhang
中科院分区：
文献类型：
--
作者：
Yufa Shen;Wenjie He;Guoping Zheng;Yanning Wang;Lingmin Zhang
如果ch（G）=χ（G），则称图G是色可选的. Ohba已经证明了每个顶点数为2χ（G）+1或更少的图G是色可选的.很明显，大场猜想成立当且仅当它对完全多部图成立。但对于完全多部图，证明Ohba猜想成立的图无非是K3，2 *（k-3），1，K3，2*（k-1），和Ks+3，2 *（k-s-1），1 *s.本文证明了Ohba猜想对完全多部图K4，3，2*（k-4），1 * 2和K5，3，2 *（k-5），1 *3成立.同时，对Enomoto等人的一个结果进行了讨论.
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*2and K5,3,2*(k-5),1*3. By the way, we give some discussions about a result of Enomoto et al.