کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418643 | 681703 | 2015 | 14 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Excluding cycles with a fixed number of chords
ترجمه فارسی عنوان
به غیر از چرخه با تعداد ثابت آکورد
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
آکورد، شماره کروماتیک، محدودیت چی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Trotignon and Vušković completely characterized graphs that do not contain cycles with exactly one chord. In particular, they show that such a graph GG has chromatic number at most max(3,ω(G))max(3,ω(G)). We generalize this result to the class of graphs that do not contain cycles with exactly two chords and the class of graphs that do not contain cycles with exactly three chords.More precisely we prove that graphs with no cycle with exactly two chords have chromatic number at most 66. And a graph GG with no cycle with exactly three chords has chromatic number at most max(96,ω(G)+1)max(96,ω(G)+1).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 180, 10 January 2015, Pages 11–24
Journal: Discrete Applied Mathematics - Volume 180, 10 January 2015, Pages 11–24
نویسندگان
Pierre Aboulker, Nicolas Bousquet,