کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419056 | 681735 | 2014 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
(Circular) backbone colouring: Forest backbones in planar graphs
ترجمه فارسی عنوان
(ستون فقرات) رنگ آمیزی: ستون فقرات جنگل در نمودارهای مسطح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
Consider an undirected graph GG and a subgraph HH of GG, on the same vertex set. The qq-backbone chromatic number BBCq(G,H) is the minimum kk such that GG can be properly coloured with colours from {1,…,k}{1,…,k}, and moreover for each edge of HH, the colours of its ends differ by at least qq. In this paper we focus on the case when GG is planar and HH is a forest. We give a series of NP-hardness results as well as upper bounds for BBCq(G,H), depending on the type of the forest (matching, galaxy, spanning tree). Eventually, we discuss a circular version of the problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 169, 31 May 2014, Pages 119–134
Journal: Discrete Applied Mathematics - Volume 169, 31 May 2014, Pages 119–134
نویسندگان
Frédéric Havet, Andrew D. King, Mathieu Liedloff, Ioan Todinca,