کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420428 | 683937 | 2010 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
First-Fit coloring of {P5,K4−e}{P5,K4−e}-free graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
We show that given any ordering of the vertices of a {P5,K4−e}{P5,K4−e}-free graph GG, the First-Fit coloring algorithm colors its vertices using at most 2ω(G)−12ω(G)−1 colors (where ω(G)ω(G) is the clique number of GG) via a characterization proved by using the known results. We also construct {P5,K4−e}{P5,K4−e}-free graphs to show that this bound cannot be improved. A similar result is proved for the class of {P5,paw}{P5,paw}-free graphs.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 6, 28 March 2010, Pages 620–626
Journal: Discrete Applied Mathematics - Volume 158, Issue 6, 28 March 2010, Pages 620–626
نویسندگان
S.A. Choudum, T. Karthick,