کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5777139 | 1632570 | 2017 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Distance colouring without one cycle length
ترجمه فارسی عنوان
فاصله رنگی بدون یک طول چرخه
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
رنگ آمیزی نمودار، رنگ آمیزی فاصله چرخه های انحصاری، قدرت گراف،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات گسسته و ترکیبات
چکیده انگلیسی
We consider distance colourings in graphs of maximum degree at most d and how excluding one fixed cycle length â affects the number of colours required as dââ. For vertex-colouring and tâ¥1, if any two distinct vertices connected by a path of at most t edges are required to be coloured differently, then a reduction by a logarithmic (in d) factor against the trivial bound O(dt) can be obtained by excluding an odd cycle length ââ¥3t if t is odd or by excluding an even cycle length ââ¥2t+2. For edge-colouring and tâ¥2, if any two distinct edges connected by a path of fewer than t edges are required to be coloured differently, then excluding an even cycle length ââ¥2t is sufficient for a logarithmic factor reduction. For tâ¥2, neither of the above statements are possible for other parity combinations of â and t. These results can be considered extensions of results due to Johansson (1996) and Mahdian (2000), and are related to open problems of Alon and Mohar (2002) and Kaiser and Kang (2014).
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 695-701
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 695-701
نویسندگان
Ross J. Kang, François Pirot,