کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
418643 681703 2015 14 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Excluding cycles with a fixed number of chords
ترجمه فارسی عنوان
به غیر از چرخه با تعداد ثابت آکورد
کلمات کلیدی
آکورد، شماره کروماتیک، محدودیت چی
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

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
نویسندگان
, ,