کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648453 | 1342412 | 2012 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Colouring vertices of triangle-free graphs without forests
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
The vertex colouring problem is known to be NP-complete in the class of triangle-free graphs. Moreover, it is NP-complete in any subclass of triangle-free graphs defined by a finite collection of forbidden induced subgraphs, each of which contains a cycle. In this paper, we study the vertex colouring problem in subclasses of triangle-free graphs obtained by forbidding graphs without cycles, i.e., forests, and prove polynomial-time solvability of the problem in many classes of this type. In particular, our paper, combined with some previously known results, provides a complete description of the complexity status of the problem in subclasses of triangle-free graphs obtained by forbidding a forest with at most 6 vertices.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 312, Issue 7, 6 April 2012, Pages 1372–1385
Journal: Discrete Mathematics - Volume 312, Issue 7, 6 April 2012, Pages 1372–1385
نویسندگان
Konrad K. Dabrowski, Vadim Lozin, Rajiv Raman, Bernard Ries,