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

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