کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6424236 | 1632784 | 2014 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Obstructions to locally injective oriented improper colourings
ترجمه فارسی عنوان
مانع از رنگ آمیزی نادرست محلی تزریق گرا
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
Oriented colourings that are injective on in-neighbourhoods, but which need not be proper colourings, are considered. We first find some bounds on the number of colours needed, and determine the complexity of the associated decision problem. We then consider the polynomial cases, and describe efficient algorithms, based on colouring extensions, which produce either a colouring with the given number of colours or a forbidden substructure.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 402-412
Journal: European Journal of Combinatorics - Volume 35, January 2014, Pages 402-412
نویسندگان
Gary MacGillivray, André Raspaud, Jacobus Swarts,