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

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