کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
8902910 | 1632396 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
ترجمه فارسی عنوان
ضخامت 2 رنگ از نمودارهای مسطح بدون 4 سیکل و 5 سیکل
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی معیوب نمودار پلانار، چرخه،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
A 2-coloring is a coloring of vertices of a graph with colors 1 and 2. Define Viâ{vâV(G):c(v)=i} for i=1 and 2. We say that G is (d1,d2)-colorable if G has a 2-coloring such that Vi is an empty set or the induced subgraph G[Vi] has the maximum degree at most di for i=1 and 2. Let G be a planar graph without 4-cycles and 5-cycles. We show that the problem to determine whether G is (0,k)-colorable is NP-complete for every positive integer k. Moreover, we construct non-(1,k)-colorable planar graphs without 4-cycles and 5-cycles for every positive integer k. In contrast, we prove that G is (d1,d2)-colorable where (d1,d2)=(4,4),(3,5), and (2,9).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 8, August 2018, Pages 2142-2150
Journal: Discrete Mathematics - Volume 341, Issue 8, August 2018, Pages 2142-2150
نویسندگان
Pongpat Sittitrai, Kittikorn Nakprasit,