کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4647408 1632420 2014 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Improper colorability of planar graphs without prescribed short cycles
ترجمه فارسی عنوان
رنگ پذیری نامناسب گرافهای مسطح بدون چرخه کوتاه مدت تجویز شده
کلمات کلیدی
نمودار پلانار، چرخه، رنگ نامناسب
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

Let d1,d2,…,dkd1,d2,…,dk be kk non-negative integers. A graph GG is (d1,d2,…,dk)(d1,d2,…,dk)-colorable, if the vertex set of GG can be partitioned into subsets V1,V2,…,VkV1,V2,…,Vk such that the subgraph G[Vi]G[Vi] induced by ViVi has maximum degree at most didi for i=1,2,…,ki=1,2,…,k. It is known that planar graphs without cycles of length 4 or ll for any l∈{5,6}l∈{5,6} are (1,1,0)(1,1,0)-colorable. In this paper, we prove that planar graphs without cycles of length 4 or ll for any l∈{7,8}l∈{7,8} are also (1,1,0)(1,1,0)-colorable. Some conjectures and problems for further study are presented.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 322, 6 May 2014, Pages 5–14
نویسندگان
, ,