کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334286 | 690361 | 2005 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Equitable colorings of bounded treewidth graphs
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Equitable colorings of bounded treewidth graphs Equitable colorings of bounded treewidth graphs](/preview/png/10334286.png)
چکیده انگلیسی
A proper coloring of a graph G is equitable if the sizes of any two color classes differ by at most one. A proper coloring is â-bounded, when each color class has size at most â. We consider the problems to determine for a given graph G (and a given integer â) whether G has an equitable (â-bounded) k-coloring. We prove that both problems can be solved in polynomial time on graphs of bounded treewidth, and show that a precolored version remains NP-complete on trees.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 22-30
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 22-30
نویسندگان
Hans L. Bodlaender, Fedor V. Fomin,