کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6872035 | 681717 | 2016 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On quasi-monotonous graphs
ترجمه فارسی عنوان
بر روی نمودارهای شبه یکنواخت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
A dominating coloring by k colors is a proper k coloring where every color i has a representative vertex xi adjacent to at least one vertex in each of the other classes. The b-chromatic number, b(G), of a graph G is the largest integer k such that G admits a dominating coloring by k colors. A graph G=(V,E) is said b-monotonous if b(H1)â¥b(H2) for every induced subgraph H1 of G and every subgraph H2 of H1. Here we say that a graph G is quasi b-monotonous, or simply quasi-monotonous, if for every vertex vâV, b(Gâv)â¤b(G)+1. We shall study the quasi-monotonicity of several classes. We show in particular that chordal graphs are not quasi-monotonous in general, whereas chordal graphs with large b-chromatic number, and (P,coP,chair,diamond)-free graphs are quasi-monotonous. The (P5,P,dart)-free graphs are monotonous. Finally we give new bounds for the b-chromatic number of any vertex deleted subgraph of a chordal graph.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 155-163
Journal: Discrete Applied Mathematics - Volume 198, 10 January 2016, Pages 155-163
نویسندگان
Mekkia Kouider,