کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4650104 1342474 2008 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On choosability of some complete multipartite graphs and Ohba's conjecture
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
On choosability of some complete multipartite graphs and Ohba's conjecture
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 1, 6 January 2008, Pages 136–143
نویسندگان
, , , , ,