کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
438058 | 690225 | 2008 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Equitable list colorings of planar graphs without short cycles
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
A graph G is equitably k-choosable if, for any k-uniform list assignment L, G is L-colorable and each color appears on at most vertices. A graph G is equitably k-colorable if G has a proper k-vertex coloring such that the sizes of any two color classes differ by at most 1. In this paper, we prove that every planar graph G is equitably k-choosable and equitably k-colorable if one of the following conditions holds: (1) G is triangle-free and k≥max{Δ(G),8}; (2) G has no 4- and 5-cycles and k≥max{Δ(G),7}.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 407, Issues 1–3, 6 November 2008, Pages 21-28
Journal: Theoretical Computer Science - Volume 407, Issues 1–3, 6 November 2008, Pages 21-28