کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
420473 | 683945 | 2009 | 12 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On minimally b-imperfect graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbour in all other color classes. The b-chromatic number of a graph GG is the largest integer kk such that GG admits a b-coloring with kk colors. A graph is b-perfect if the b-chromatic number is equal to the chromatic number for every induced subgraph HH of GG. A graph is minimally b-imperfect if it is not b-perfect and every proper induced subgraph is b-perfect. We give a list FF of minimally b-imperfect graphs, conjecture that a graph is b-perfect if and only if it does not contain a graph from this list as an induced subgraph, and prove this conjecture for diamond-free graphs, and graphs with chromatic number at most three.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 17, 28 October 2009, Pages 3519–3530
Journal: Discrete Applied Mathematics - Volume 157, Issue 17, 28 October 2009, Pages 3519–3530
نویسندگان
Chính T. Hoàng, Cláudia Linhares Sales, Frédéric Maffray,