کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4650104 | 1342474 | 2008 | 8 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: On choosability of some complete multipartite graphs and Ohba's conjecture On choosability of some complete multipartite graphs and Ohba's conjecture](/preview/png/4650104.png)
A graph G is said to be chromatic-choosable if ch(G)=χ(G)ch(G)=χ(G). Ohba has conjectured that every graph G with 2χ(G)+12χ(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),1K3*2,2*(k-3),1, K3,2*(k-1)K3,2*(k-1), and Ks+3,2*(k-s-1),1*sKs+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*2K4,3,2*(k-4),1*2 and K5,3,2*(k-5),1*3K5,3,2*(k-5),1*3. By the way, we give some discussions about a result of Enomoto et al.
Journal: Discrete Mathematics - Volume 308, Issue 1, 6 January 2008, Pages 136–143