کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902910 1632396 2018 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Defective 2-colorings of planar graphs without 4-cycles and 5-cycles
ترجمه فارسی عنوان
ضخامت 2 رنگ از نمودارهای مسطح بدون 4 سیکل و 5 سیکل
کلمات کلیدی
رنگ آمیزی معیوب نمودار پلانار، چرخه،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی
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
نویسندگان
, ,