کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
435192 689879 2016 12 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Proper orientation of cacti
ترجمه فارسی عنوان
جهت گیری مناسب کاکتوس ها
کلمات کلیدی
جهت گیری مناسب؛ رنگ آمیزی نمودار؛ نمودار کاکتوس؛ نمودار بدون چنگال؛ نمودار مسطح؛ نمودار بلوک
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی

An orientation of a graph G is proper if two adjacent vertices have different in-degrees. The proper-orientation number  χ→(G) of a graph G is the minimum maximum in-degree of a proper orientation of G.In [1], the authors ask whether the proper orientation number of a planar graph is bounded.We prove that every cactus admits a proper orientation with maximum in-degree at most 7. We also prove that the bound 7 is tight by showing a cactus having no proper orientation with maximum in-degree less than 7. We also prove that any planar claw-free graph has a proper orientation with maximum in-degree at most 6 and that this bound can also be attained.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 639, 1 August 2016, Pages 14–25
نویسندگان
, , , ,