کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4646850 1342315 2015 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On choosability with separation of planar graphs with lists of different sizes
ترجمه فارسی عنوان
در انتخابی با جداسازی نمودارهای مسطح با لیست های اندازه های مختلف
کلمات کلیدی
رنگ آمیزی نمودار، نمودارهای پلانار، انتخاب با جدایی، فهرست رنگ آمیزی
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

A (k,d)(k,d)-list assignment  LL of a graph GG is a mapping that assigns to each vertex vv a list L(v)L(v) of at least kk colors and for any adjacent pair xyxy, the lists L(x)L(x) and L(y)L(y) share at most dd colors. A graph GG is (k,d)(k,d)-choosable if there exists an LL-coloring of GG for every (k,d)(k,d)-list assignment LL. This concept is also known as choosability with separation.It is known that planar graphs are (4, 1)-choosable but it is not known if planar graphs are (3, 1)-choosable. We strengthen the result that planar graphs are (4, 1)-choosable by allowing an independent set of vertices to have lists of size 3 instead of 4.Our strengthening is motivated by the observation that in (4, 1)-list assignment, vertices of an edge have together at least 7 colors, while in (3, 1)-list assignment, they have only at least 5. Our setting gives at least 6 colors.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 338, Issue 10, 6 October 2015, Pages 1779–1783
نویسندگان
, ,