کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10334292 | 690361 | 2005 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
On equitable Î-coloring of graphs with low average degree
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: On equitable Î-coloring of graphs with low average degree On equitable Î-coloring of graphs with low average degree](/preview/png/10334292.png)
چکیده انگلیسی
An equitable coloring of a graph is a proper vertex coloring such that the sizes of any two color classes differ by at most 1. Hajnal and Szemerédi proved that every graph with maximum degree Î is equitably k-colorable for every k⩾Î+1. Chen, Lih, and Wu conjectured that every connected graph with maximum degree Î⩾3 distinct from KÎ+1 and KÎ,Î is equitably Î-colorable. This conjecture has been proved for graphs in some classes such as bipartite graphs, outerplanar graphs, graphs with maximum degree 3, interval graphs. We prove that this conjecture holds for graphs with average degree at most Î/5.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 82-91
Journal: Theoretical Computer Science - Volume 349, Issue 1, 12 December 2005, Pages 82-91
نویسندگان
A.V. Kostochka, K. Nakprasit,