کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653179 1632757 2017 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
On degree anti-Ramsey numbers
ترجمه فارسی عنوان
درباره اعداد ضدرمزی درجه ای
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
چکیده انگلیسی

The degree anti-Ramsey number ARd(H)ARd(H) of a graph HH is the smallest integer kk for which there exists a graph GG with maximum degree at most kk such that any proper edge colouring of GG yields a rainbow copy of HH. In this paper we prove a general upper bound on degree anti-Ramsey numbers, determine the precise value of the degree anti-Ramsey number of any forest, and prove an upper bound on the degree anti-Ramsey numbers of cycles of any length which is best possible up to a multiplicative factor of 22. Our proofs involve a variety of tools, including a classical result of Bollobás concerning cross intersecting families and a topological version of Hall’s Theorem due to Aharoni, Berger and Meshulam.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 60, February 2017, Pages 31–41
نویسندگان
, ,