کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648163 1342395 2011 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Ohba’s conjecture for graphs with independence number five
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Ohba’s conjecture for graphs with independence number five
چکیده انگلیسی

Ohba has conjectured that if GG is a kk-chromatic graph with at most 2k+12k+1 vertices, then the list chromatic number or choosability ch(G) of GG is equal to its chromatic number χ(G)χ(G), which is kk. It is known that this holds if GG has independence number at most three. It is proved here that it holds if GG has independence number at most five. In particular, and equivalently, it holds if GG is a complete kk-partite graph and each part has at most five vertices.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 311, Issue 12, 28 June 2011, Pages 996–1005
نویسندگان
, , ,