کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4657209 1343723 2010 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
K4-free graphs with no odd holes
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
K4-free graphs with no odd holes
چکیده انگلیسی

All K4-free graphs with no odd hole and no odd antihole are three-colourable, but what about K4-free graphs with no odd hole? They are not necessarily three-colourable, but we prove a conjecture of Ding that they are all four-colourable. This is a consequence of a decomposition theorem for such graphs; we prove that every such graph either has no odd antihole, or belongs to one of two explicitly-constructed classes, or admits a decomposition.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 100, Issue 3, May 2010, Pages 313-331