کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420108 683895 2011 7 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
First-Fit coloring of bounded tolerance graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
First-Fit coloring of bounded tolerance graphs
چکیده انگلیسی

Let G=(V,E)G=(V,E) be a graph. A tolerance representation of GG is a set I={Iv:v∈V}I={Iv:v∈V} of intervals and a set t={tv:v∈V}t={tv:v∈V} of nonnegative reals such that xy∈Exy∈E iff Ix∩Iy≠0̸Ix∩Iy≠0̸ and ‖Ix∩Iy‖≥min{tx,ty}‖Ix∩Iy‖≥min{tx,ty}; in this case GG is a tolerance graph. We refine this definition by saying that GG is a pp-tolerance graph if tv/|Iv|≤ptv/|Iv|≤p for all v∈Vv∈V.A Grundy coloring gg of GG is a proper coloring of VV with positive integers such that for every positive integer ii, if i

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 159, Issue 7, 6 April 2011, Pages 605–611
نویسندگان
, ,